The Meaning of ‘Quantum Supremacy’
What Does Quantum Supremacy Mean?
Selected notes ~
+ Quantum supremacy is the experimental demonstration that quantum computers are superior to classical computers. That is, demonstrating quantum supremacy requires doing a calculation on a quantum computer that no classical computer could replicate in a reasonable amount of time.
Will this really demonstrate quantum supremacy? It’s not clear.
+ How would one do this? One possible way to do this would be by factoring a 1024-bit number, but quantum computers that have the ability to do this are decades in the future. The first demonstration of quantum supremacy is much more likely to be of the form: given this input to a quantum computer, give a representative sample of the output distribution.
+ Right now, people think that 100 qubits will be more than enough to demonstrate quantum supremacy. But the state of the art of theoretical computer science is not sufficient to show that classical computers cannot perform a certain finite computation—all our results are asymptotic, saying that the time grows exponentially as the number of bits goes to infinity. We really don’t know how long it will take a classical computer to simulate an 100-qubit quantum computers. So there is no guarantee that somebody won’t come up with an algorithm tomorrow that simulates the output of a 100-qubit quantum computer, in which case the demonstration of quantum supremacy will be delayed for several years.
Source: Forbes. Quora, What Does Quantum Supremacy Mean?
Content may have been edited for style and clarity.
