Friday, October 28, 2016

In search of Quantum Supremacy

Computer complexity theorist had 5 minutes to explain quantum computers, and said:
But what quantum supremacy means to me, is demonstrating a quantum speedup for some task as confidently as possible.  Notice that I didn’t say a useful task!  I like to say that for me, the #1 application of quantum computing — more than codebreaking, machine learning, or even quantum simulation — is just disproving the people who say quantum computing is impossible!  So, quantum supremacy targets that application.

What is important for quantum supremacy is that we solve a clearly defined problem, with some relationship between inputs and outputs that’s independent of whatever hardware we’re using to solve the problem.  That’s part of why it doesn’t cut it to point to some complicated, hard-to-simulate molecule and say “aha!  quantum supremacy!”
I accept this, but the important points is that quantum supremacy has never been demonstrated. Yes, there are regular press releases and news stories about advances in new and better quantum computers, but no one has ever shown a quantum speedup over regular Turing computers.

Charles H. Bennett responds:
An experimental demonstration of what is infelicitously called quantum supremacy (I prefer “classical retardation”) would be way less earthshaking than the Higgs boson. It would be much more like the experimental demonstrations of Bell and CHSH violations: a validation of what we have every right to expect, based on the unblemished success of quantum theory so far.
I do not agree. Quantum theory is unblemished in confirming Bell violations, yes, but the computational speedups are speculative and have not been shown. I doubt that they will ever be shown.

1 comment:

  1. But WHY in the first instance? What critical problem can't be approached by FPGAs? It's a SCAM and not a debate.