(PhysicsWorld) One of the main goals in quantum computing is to experimentally demonstrate that a quantum machine can perform some computational task faster than a classical one. A team of researchers based in France and the UK has now done just that using a simple quantum photonics experimental set-up. Their work shows that it is possible for a quantum computer to verify solutions to problems classified as NP-complete using a so-called interactive proof protocol and only minimal, unverified information about the solution.
By showing that a quantum algorithm can verify solutions to NP-complete problems efficiently, the result could allow for new applications in secure remote quantum computing. A client with a rudimentary quantum machine could, for example, verify information they receive from a powerful quantum server without ever having access to the full solution. Such proof systems could then contribute to protocols like secure identification, authentication or even blockchain in a future quantum Internet. “In the current era of increasing focus on data privacy and secure computing, our demonstration provides yet another compelling piece of evidence that quantum computers can outperform their classical counterparts in achieving secure solutions,” adds Niraj Kumar, an Edinburgh researcher and a co-author on the paper.
Although NP-complete problems are hard to solve efficiently, once solutions are found, they can be verified trivially. The challenge that the team at CNRS (the French National Centre for Scientific Research) and the University of Edinburgh focused on occupies a middle ground between the two: verifying the solution to an NP-complete problem when provided with only a part of that solution.
Quantum Computer Has the Edge for NP Verification
