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.
