Most Popular
1500 questions
25
votes
4 answers
Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
It is a well known result that the Discrete Fourier Transform (DFT) of $N=2^n$ numbers has complexity $\mathcal O(n2^n)$ with the best known algorithm, while performing the Fourier transform of the amplitudes of a quantum state, with the classical…
glS
- 27,510
- 7
- 37
- 125
25
votes
2 answers
Significance of The Church of the Higher Hilbert space
The term "Church of the Higher Hilbert Space" is used in quantum information frequently when analysing quantum channels and quantum states.
What does this term mean (or, alternately, what does the term "Going to To the Church of the Higher Hilbert…
user3483902
- 825
- 8
- 15
25
votes
1 answer
What is the purpose of a quantum RAM in quantum algorithms?
I see many papers (e.g. Quantum principal component analysis) in which the existence of qRAM is necessary. What's the actual purpose of qRAM in quantum algorithms?
Anton Karazeev
- 353
- 3
- 8
25
votes
3 answers
What makes quantum computers so good at computing prime factors?
One of the common claims about quantum computers is their ability to "break" conventional cryptography. This is because conventional cryptography is based on prime factors, something which is computationally expensive for conventional computers to…
Paul Turner
- 353
- 3
- 8
25
votes
3 answers
Why do optical quantum computers not have to be kept near absolute zero while superconducting quantum computers do?
This is a follow-up question to @heather's answer to the question : Why must quantum computers be kept near absolute zero?
What I know:
Superconducting quantum computing: It is an implementation of a quantum computer in a superconducting electronic…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
24
votes
4 answers
Can we combine the square roots inside the definition of the fidelity?
The (Uhlmann-Jozsa) fidelity of quantum states $\rho$ and $\sigma$ is defined to be
$$F(\rho, \sigma) := \left(\mathrm{tr} \left[\sqrt{\sqrt{\rho} \sigma \sqrt{\rho}} \right]\right)^2.$$
However, as discussed here, the cyclical property of the trace…
tparker
- 2,939
- 13
- 26
24
votes
2 answers
What is a "barrier" in Qiskit circuits?
I just started studying IBM Qiskit, and cannot find details about the barrier method on the QuantumCircuit class. It is shown in the circuit drawing, but I never heard about it after reading quantum computing text books. Is it a unitary gate? If so,…
czwang
- 949
- 1
- 6
- 17
24
votes
3 answers
Which quantum error correction code has the highest threshold (as proven at the time of writing this)?
Which quantum error correction code currently holds the record in terms of the highest threshold for fault-tolerance? I know that the surface code is pretty good ($\approx10^{-2}$?), but finding exact numbers is difficult. I also read about some…
M. Stern
- 2,457
- 17
- 40
24
votes
3 answers
What level of "confidence" of the result from a quantum computer is possible?
At a very basic level, reading or measuring a qubit forces it to be in one state or the other, so the operation of a quantum computer to gain a result collapses the state into one of many possibilities.
But as the state of each qubit is…
Rory Alsop
- 461
- 6
- 16
24
votes
3 answers
Is quantum cryptography safer than classical cryptography?
Quantum computing allows us to encrypt information in a different way compared to what we use today, but quantum computers are much more powerful than today's computers. So if we manage to build quantum computers (hence use quantum cryptography),…
PiMan
- 2,235
- 1
- 21
- 32
24
votes
3 answers
Is entanglement transitive?
Is entanglement transitive, in a mathematical sense?
More concretely, my question is this:
Consider 3 qubits $q_1, q_2$ and $q_3$. Assume that
$q_1$ and $q_2$ are entangled, and that
$q_2$ and $q_3$ are entangled
Then, are $q_1$ and $q_3$…
Peter
- 529
- 2
- 8
24
votes
2 answers
How does the Grover diffusion operator work and why is it optimal?
In this answer, Grover's algorithm is explained. The explanation indicates that the algorithm relies heavily on the Grover Diffusion Operator, but does not give details on the inner workings of this operator.
Briefly, the Grover Diffusion Operator…
Discrete lizard
- 3,154
- 2
- 20
- 42
23
votes
3 answers
What does Google's claim of "Quantum Supremacy" mean for the question of BQP vs BPP vs NP?
Google recently announced that they have achieved "Quantum Supremacy": "that would be practically impossible for a classical machine."
Does this mean that they have definitely proved that BQP ≠ BPP ? And if that is the case, what are the…
Alex Kinman
- 695
- 5
- 10
23
votes
1 answer
Twirling Quantum Channels: Pauli and Clifford Twirling
I am currently working through some papers related with approximations of more general quantum channels such as amplitude and phase damping channels to Pauli channels. The reason to do so is so that the Gottesman-Knill theorem is fulfilled and…
Josu Etxezarreta Martinez
- 4,136
- 15
- 42
23
votes
1 answer
Is there a list of accessible open problems in quantum computing from a theoretical computer science perspective?
(Classical) theoretical computer science (TCS) has a number of outstanding open problems that can easily be instantiated in a manner that is accessible to a wider general public.
For example, questions about $\mathrm{P}$ vs. $\mathrm{NP}$ can…
Mark Spinelli
- 15,378
- 3
- 26
- 83