Update: A slightly different version of this question has been answered here.

As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results. If the quantum computer would be powerful enough to solve problems in NP (like factoring, using Shor's algorithm), it would be easy to verify the results, however, this computational power is not available yet. As an intermediate step,

what could be a problem within reach of today's quantum computers whose output can be verified efficiently with a witness?

Here efficiently need not stand for the problem itself being in NP, but rather it would be sufficient that the correctness of the solution is in NP. For example, consider a satisfiability task whose literals are $x_i$'s and $y_j$'s. If the quantum computer can produce all the $x_i$ that are part of a solution, then a witness for its correctness would be finding the $y_j$'s that make $(x,y)$ into a solution. The corresponding $y$ can be found with a classical algorithm, or set as a challenge, like in case of Bitcoin, to mint some quantum coin, with the computational power of all the miners looking for the witness. In fact, miners can be also rewarded for finding another $(x',y')$ solution of the original problem, which would determine whether $x$ is useful or not.

So what could be such a problem? Can Shor's algorithm or some other similar problem be broken into finding some $x$ with a quantum computer that can be extended into a witness with some (smaller) $y$?

  • $\begingroup$ If a quantum computer output is verifiable in asymptotic polynomial time with classical computers, it is in NP (unless the verification algorithm is randomized, in which case it is in MA). But that's not what you should be asking. All we care about is the finite case, not the asymptotic one. $\endgroup$ – Peter Shor Dec 29 '19 at 15:13
  • $\begingroup$ To expand on my previous comment, the asymptotic case is taken care of by factoring, as well as a number of other asymptotic quantum supremacy results. And it's quite possible there are problems in P which quantum computers can solve, but for which witnesses are too difficult to compute classically on today’s digital computers (although I have to admit I don't know any). $\endgroup$ – Peter Shor Dec 30 '19 at 18:22
  • $\begingroup$ @Peter My question meant exactly to be about the state-of-the-art quantum computers (around 53 qubits). Is there a verifiable problem whose solution they can enhance? For example, if I want to find a hidden 100-digit factor, could a 53-qubit quantum algorithm tell me fast that the 42nd digit is 3 with >20% probability? I would consider this to be a verifiable (through a further exponential amount of computation) quantum advantage. $\endgroup$ – domotorp Dec 30 '19 at 19:58
  • 4
    $\begingroup$ As I was trying to explain in my previous comments, "exponential" has no real meaning when you're talking about a 53-qubit machine. Everything is a constant-time computation. The question is whether it's a constant that is practical on our current computers or not. $\endgroup$ – Peter Shor Jan 2 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.