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.
The work is among several recent milestones in demonstrating quantum advantage. In 2019, Google claimed to be the first to the finish line with their 53 programmable superconducting qubit (quantum bit) set-up. More recently, a team in China announced that they had successfully performed “boson sampling”, a task known to be hard for a classical computer. Unlike these previous results, however, the new research, which is published in Nature Communications, not only demonstrates quantum advantage but also promises to be useful in applications like secure quantum cloud computing.
NP verification
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.
When the size of the message containing the partial solution, or proof, is fixed, it can be shown that a classical protocol for verifying the solution will take an amount of time that scales exponentially with the size of the message. For the quantum protocol, in contrast, the scaling is polynomial. This means that for large message sizes, a quantum computer would take minutes to verify the solution while a classical one could take years.
D-Wave demonstrates performance advantage in quantum simulation
The algorithm the researchers use to demonstrate this is known as an interactive proof protocol. Here, one component of the experimental set-up acts as a “prover”, using coherent light pulses to send partial solutions to the NP-complete problem in the form of a quantum state. The second component fills the role of the “verifier”, deciding with high accuracy whether the solution is correct based on the limited information given. When certain bounds are placed on the expected accuracy of the verifier, as well as the protocol’s speed and efficiency in terms of the amount of information that can be communicated throughout the interactions, it is possible to demonstrate that the quantum algorithm far outperforms any classical attempts at doing the same.
Quantum cloud computing
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.
