Quantum superiority for verifying NP-complete problems with linear optics. (December 2018)

• Record Type: Journal Article
• Authors: Arrazola, Juan; Diamanti, Eleni; Kerenidis, Iordanis
• Is Part Of: Npj quantum information. Volume 4(2018)
• Page Start: 1
• Page End: 8
• Publication Date: 2018-12
• Subjects: Quantum computers -- Periodicals; Quantum communication -- Periodicals; Information theory -- Periodicals; Quantum theory -- Periodicals; Quantum theory; Information theory; Quantum communication; Quantum computers; Periodicals; 006.3843
• DOI: 10.1038/s41534-018-0103-1
• Languages: English
• ISSNs: 2056-6387

Abstract

Abstract Demonstrating quantum superiority for some computational task will be a milestone for quantum technologies and would show that computational advantages are possible not only with a universal quantum computer but with simpler physical devices. Linear optics is such a simpler but powerful platform where classically-hard information processing tasks, such as Boson Sampling, can be in principle implemented. In this work, we study a fundamentally different type of computational task to achieve quantum superiority using linear optics, namely the task of verifying NP-complete problems. We focus on a protocol by Aaronson et al. (2008) that uses quantum proofs for verification. We show that the proof states can be implemented in terms of a single photon in an equal superposition over many optical modes. Similarly, the tests can be performed using linear-optical transformations consisting of a few operations: a global permutation of all modes, simple interferometers acting on at most four modes, and measurement using single-photon detectors. We also show that the protocol can tolerate experimental imperfections. Optical circuits: Demonstrating quantum superiority with linear optics A proposal for achieving quantum superiority using linear optics shows that a class of verification problems is a promising test platform. An important milestone for quantum technologies is to demonstrate a clear advantage of using quantum rather than classical systems to perform a computational task. This point is known as quantum superiority but identifying suitable tasks for demonstrating quantum superiority remains a key challenge. A team of researchers led by Iordanis Kerenidis from Universite Paris Diderot and National University of Singapore now show that the running time for a particular verification algorithm is drastically reduced when using a quantum protocol, rather than a classical one. The protocol can be implemented using optical circuits, which will likely be less resource-intensive than trying to do the same type of verification using conventional computers, but should be quite tolerant to imperfections, and so should be within experimental reach.