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.
12
questions
4
votes
1answer
445 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:
...
22
votes
2answers
880 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. ...
9
votes
2answers
572 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 ...
8
votes
4answers
724 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 ...
3
votes
2answers
275 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 ...
19
votes
2answers
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 ?...
6
votes
1answer
500 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:
...
6
votes
1answer
402 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 ("...
2
votes
1answer
92 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 ...
12
votes
1answer
3k 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 ...
3
votes
2answers
150 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 ...
1
vote
1answer
52 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 ...
