Questions tagged [quantum-advantage]
"Quantum advantage" or "quantum supremacy" is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.
24
questions
8
votes
3
answers
1k
views
What exactly makes quantum computers faster than classical computers?
What feature of a quantum algorithm makes it better than its classical counterpart? Are quantum computers faster than classical ones in all respects?
- 601
12
votes
2
answers
810
views
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 1): choice of gate set
I was recently going through the paper titled "Quantum supremacy using a programmable superconducting processor" by NASA Ames Research Centre and the Google Quantum AI team (note that the paper was ...
- 16.3k
39
votes
1
answer
1k
views
Quantum machine learning after Ewin Tang
Recently, a series of research papers have been released (this, this and this, also this) that provide classical algorithms with the same runtime as quantum machine learning algorithms for the same ...
- 503
34
votes
5
answers
2k
views
Are there problems in which quantum computers are known to provide an exponential advantage?
It is generally believed and claimed that quantum computers can outperform classical devices in at least some tasks.
One of the most commonly cited examples of a problem in which quantum computers ...
glS♦
- 19k
6
votes
1
answer
672
views
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 3): sampling
In Google's 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:
...
- 16.3k
29
votes
2
answers
1k
views
When will we know that quantum supremacy has been reached?
The term "quantum supremacy" - to my understanding - means that one can create and run algorithms to solve problems on quantum computers that can't be solved in realistic times on binary computers. ...
- 1,132
8
votes
4
answers
2k
views
Grover algorithm for a database search: where is the quantum advantage?
I have been trying to understand what could be the advantage of using Grover algorithm for searching in an arbitrary unordered database D(key, value) with N values instead of a classical search.
I ...
- 183
8
votes
1
answer
883
views
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 2): simplifiable and intractable tilings
In Google's 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:
...
- 16.3k
4
votes
2
answers
339
views
Do quantum supremacy experiments repeatedly apply the same random unitary?
It is my understanding that, given a quantum computer with $n$ qubits and a way to apply $m$ single- and 2-qubit gates, quantum supremacy experiments
Initialize the $n$ qubits into the all-zero's ket ...
- 7,414
9
votes
2
answers
719
views
What is the advantage of quantum machine learning over traditional machine learning?
Why exactly is machine learning on quantum computers different than classical machine learning? Is there a specific difference that allows quantum machine learning to outperform classical machine ...
- 345
17
votes
1
answer
5k
views
What exactly is "Random Circuit Sampling"?
Many people have suggested using "Random Circuit Sampling" to demonstrate quantum supremacy. But what is the precise definition of the "Random Circuit Sampling" problem? I've seen statements like "the ...
- 271
21
votes
2
answers
4k
views
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 ?...
- 655
10
votes
2
answers
1k
views
What are the real advantages of superdense coding?
In superdense coding, two qubits are prepared by Eve in an entangled state; one of them is sent to Alice and the other is sent to Bob. Alice is the one who wants to send (to Bob) two classical bits of ...
user72
7
votes
1
answer
448
views
How to benchmark a quantum computer?
Using a simple puzzle game to benchmark quantum computers is the most clever approach I have seen so far.
The author of the aforementioned article, James, makes a nice analogy to buying a laptop ("...
- 3,202
5
votes
2
answers
856
views
Are there quantum algorithms showing a double exponential advantage?
I would like to know if there are known quantum algorithms that provide a double exponential advantage compared to the best known classical algorithms.
More precisely, if the characteristics of the ...
2
votes
1
answer
122
views
How does successfully sampling from a random quantum circuit invalidate the Extended Church-Turing Thesis?
According to these lecture notes from Berkeley, the Extended Church-Turing Thesis (ECT) asserts that:
...any "reasonable" model of computation can be efficiently simulated on a standard model such ...
- 7,414
11
votes
1
answer
438
views
Why exactly are variational algorithms considered promising?
There is obviously a great deal of work happening at the moment on variational quantum algorithms. However, I'm struggling to understand why exactly are they considered promising? Looking through some ...
- 1,243
3
votes
1
answer
334
views
Confusion about the output distribution of Haar random quantum states
Consider a Haar random quantum state $|\psi \rangle$. I was confused between two facts about $|\psi \rangle$, which appear related:
Consider the output distribution of a particular $n$-qubit $|\psi \...
- 933
9
votes
3
answers
181
views
Is there quantum advantage to be had with a D-Wave computer in 2020?
I've seen a lot of excitement in the popular press about the computers made by D-Wave Systems, but when I dig deep the only practical things that I can figure out that one can do with the computer are ...
- 591
8
votes
1
answer
190
views
List of practical quantum computing algorithms that have speed-up higher than quadratic speed-up?
From this link (provided by @KAJ226's comment in this question), it appears as though current error correction methods are not enough to get practical speedup out of algorithms that have quadratic ...
- 1,059
4
votes
2
answers
205
views
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
Note: This has been cross-posted to CS Theory SE.
If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the ...
- 16.3k
3
votes
2
answers
505
views
Question regarding integration of Haar random state
I am trying to understand the integration on page 4 of this paper. Consider a Haar random circuit $C$ and a fixed basis $z$. Each output probability of a Haar random circuit (given by $|\langle z | C |...
- 933
2
votes
2
answers
126
views
Generally speaking, are quantum speedups always due to parallelization of a given problem?
We know that quantum computers use the wave-like nature of quantum mechanics to perform interference. Sometimes we can use this interference to perform specific algorithms that will cause enough ...
- 1,059
1
vote
1
answer
234
views
What is the difference between classical and quantum computers as well as computing (permuting) itself?
Theoretically and for sure physically (I know the quantum physics behind it) I know something about it. But not that much. That's why I ask the question here. I'm very interested. The only answer to ...
