Quantum Computers

[John Clark]

Back in 2018 Raz and Tal proved something important, they did not prove that a quantum computer could solve all nondeterministic polynomial time problems in polynomial time, but they did prove that even if P=NP, and even if we had a algorithm that could solve NP problems on a conventional computer in polynomial time, there would STILL be a class of problems a conventional computer couldn’t solve efficiently, but a quantum computer could.  A conventional computer couldn't even efficiently verify that a solution was correct, much less find it. This newly discovered class of very exotic problems (they involve the distribution of random numbers) may be of fundamental interest in themselves or they may be interesting for no reason other than that a conventional computer can’t solve them but a quantum computer can. Even if the problems turn out to be useless I think this discovery is important because this is the first time anybody has proven that there is at least one thing that a quantum computer is fundamentally better at than can a conventional computer. 

The following is a quote from the Raz and Tal paper:

"Can polynomial-time quantum algorithms be simulated by classical algorithms in the polynomial-time hierarchy? In this paper, we show that in the black-box model (also known as query-complexity or decision-tree complexity), the answer is negative"

Oracle Separation of BQP and PH ContactAdd CommentRSS-Feed

John K Clark    See what's on my new list at  Extropolis

cuq