Demonstration of quantum advantage for NP verification

The Sampling Matching (SM) scheme
Spread the love

Researchers at CNRS, Paris and University of Edinburg have showed the first experimental demonstration of a computational quantum advantage (also referred to as quantum supremacy) with linear optics, by studying the computational task of the verification of an NP-complete problem by a verifier who only gets limited information about the proof.

They provided a simple linear optical implementation that can perform this task efficiently (within a few seconds), while they also provided strong evidence that a classical computer would take time greater than the age of the universe (assuming only that classically it takes exponential time to solve an NP-complete problem).

The verification of NP-complete problems with limited information brings a step closer to real-world useful applications, such as server-client quantum computing.

The paper can be read there.