30
votes
Accepted
Oracle Construction for Grover's Algorithm
The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to.
For example, suppose you have a 3-sat problem:
...
- 1,518
21
votes
Accepted
Entropy and computational complexity
Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there ...
- 37.8k
9
votes
Accepted
Where can I find examples of error correcting codes of the following types?
If you just need any code $E : \{0,1\}^n \to \{0,1\}^m$ where $m=O(n)$ and where the distance is linear in $m$, then what you are looking for is called an "asymptotically good code". There are many ...
- 5,645
8
votes
Accepted
Quantum Money where not even the Bank can counterfeit
There are proposals for quantum money where it appears that not even the bank can produce two copies of a quantum money state with the same serial number. See
Farhi et al's paper Quantum Money from ...
- 24.9k
8
votes
Accepted
Fast classical simulation of quantum algorithms
Your question was inspired by the recent quantum-inspired classical advance in recommendation algorithm. Note that it is not the firs time such a thing happens. In 2015, similar developments happened ...
6
votes
When is a non-unitary quantum system only theoretical?
Look at John Preskill's Lecture Notes; particularly Section 3.2.
As you noted, you can do a NAND gate by using a Toffoli gate and throwing away some of the output qubits. This results in decoherence, ...
- 24.9k
6
votes
Accepted
Why is it impossible to work with polylog length encoding schemes for quantum circuits?
Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time.
But in ...
- 1,518
6
votes
Accepted
Simulating quantum measurements by unitaries
The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae.
Any circuit with an intermediate measurement can be converted ...
- 1,518
6
votes
How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?
It's not unitary, so it's impossible because all quantum transformations have to be unitary.
Consider the states
$$
\frac{3}{5} |0\rangle + \frac{4}{5} |1\rangle \quad \mathrm{and} \quad \frac{3}{5} |...
- 24.9k
5
votes
Is it proved that error rate of quantum computation is bounded by constant rather than a function dependent on time and environment by quantum theory
As far as I know, nobody has come up with a convincing physics reason that fault-tolerant quantum computing is fundamentally impossible. However, it is a formidable engineering task, which is why we ...
- 24.9k
5
votes
Accepted
When is a non-unitary quantum system only theoretical?
I complete here Peter’s answer with a characterization of physical maps as CPTP maps.
As you know, if the system is isolated, the only operations you can implement are the unitary operations. But, ...
4
votes
Accepted
Noisy channel coding theorem in quantum information
You have two questions here.
Why can't Shannon's Noisy Coding Theorem be used for a quantum channel?
What gaps are there to proving a quantum noisy channel coding theorem?
I will concentrate on the ...
- 24.9k
4
votes
Is there any connection between the diamond norm and the distance of the associated states?
Following up on the line of thinking presented by Alex Monras, there is actually a quite generic argument for this kind of bound that goes beyond diamond norm and applies to many other channel ...
- 141
4
votes
Accepted
From CHSH inequality to CHSH game
I think your history is entirely right. Computer scientists are used to thinking about protocols as games, while physicists are not, and this is probably why these results weren't formulated as games ...
- 24.9k
3
votes
Accepted
Quantum circuit simulation divergence in results
Peter Shor nailed the reason. This is because OpenQASM and Quirk have different conventions for how the order of wires maps into the order of bits shown in the kets. The simplest way to check this is ...
- 1,518
2
votes
Is there any connection between the diamond norm and the distance of the associated states?
If it should prove useful, this is a derivation of the inequality
$$
\frac{1}{n} \| \Phi_0 - \Phi_1 \|_{\Diamond} \leq
\| J(\Phi_0) - J(\Phi_1) \|_1
$$
in John Watrous' answer. We will make use of ...
- 41
2
votes
Accepted
Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?
I think your focus on the rigid case of GI limits you too much. Instead phrase (non-rigid) GI as an HSP in the same way, but now the goal is to determine the size of the hidden subgroup, or a ...
- 37.8k
2
votes
How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?
I wouldn't think so. I'm assuming your $a_n$'s are normalized, i.e. that $||\sum_n a_n |n\rangle|| =1$. But then your wish output is not normalized since $$||\sum_n e^{ia_n} |n\rangle|| = \sqrt{\sum_n ...
- 1,010
2
votes
Accepted
Computing 'Robustness of Magic' of $n$-bit W states
Here is a proof that $R(W_n) \in \Omega(\sqrt[4]{n})$.
Given a $W_n$ state, it is possible to create $\lg n$ T states with Clifford operations and a single additional T gate. Basically:
Xor together ...
- 1,518
2
votes
QPIP minimal client quantum capabilities
According to this paper:
https://arxiv.org/pdf/1509.09180.pdf
The client only needs the ability to prepare random single-qubit pure states.
You may also look at this paper for more information:
...
2
votes
Survey on Quantum error correction
Try these:
Quantum Error Correction by Todd Brun
Quantum Error Correction: An Introductory Guide by Joschka Roffe
For surface codes, Dan Browne's lecture notes might help.
- 203
1
vote
Accepted
Impact HHL caveat relaxation on quantum advantage
Your link 404's, but certainly HHL, like most quantum (and classical!) algorithms include a number of caveats for their applicability. The runtime of HHL depends on a number of factors in addition to ...
- 1,145
1
vote
Can a collection of quantum circuits be calculated in superposition state?
In short, yes.
The circuit $Q$ you describe is unitary: let $|\phi\rangle=\sum_x a_x|x\rangle$ and $|\psi\rangle=\sum_x b_x|x\rangle$ be normalized states, then
$$\langle 0|\langle \psi|Q^*Q|\phi\...
- 1,010
1
vote
What are some "must-read" papers for someone getting into Quantum Cryptography?
What constitutes "the most important papers" is highly subjective, so I will mention some of the papers that I think are influencial and that I have enjoyed reading.
I would start with this ...
- 1,010
1
vote
What are some "must-read" papers for someone getting into Quantum Cryptography?
" I've also done a graduate-level course in (classical) cryptography. I'm interested in Quantum Cryptography and would like to know what people would consider the most important papers for me to ...
- 541
1
vote
Complement for joint POVMs?
I've come to the conclusion that the definition of the complement as I've written doesn't make sense for POVMs. It assumes that the product of two elements is a simultaneous event which is false.
...
1
vote
Oracle Construction for Grover's Algorithm
You can also get a solution which uses only one ancillary qubit (but relies on NOT gates with multiple controls), by getting your input to algebraic normal form (e.g. with Mathematicas ...
- 11
1
vote
Accepted
Addition on a quantum computer
The algorithm from that paper runs inline with no extra ancilla bits. If the input number and the affected number use up $t$ bits altogether, then it runs in $t$ bits.
3n qubits are required to add ...
- 1,518
1
vote
Accepted
Quantum GCD circuit: On reversibility and clearing ancillae
It looks like they just directly translated the algorithm into a circuit, so it's not too hard to reproduce.
Write out the binary gcd algorithm as a loop:
...
- 1,518
1
vote
Universities for Quantum Computing / Information?
MIT has three graduate classes in the field I know about. Two of them, 8.370 ( Quantum Computation) and 8.371 (Quantum Information Science ll) form a series and are theoretical classes. The other one, ...
- 11
Only top scored, non community-wiki answers of a minimum length are eligible