Please use this identifier to cite or link to this item:
Title: Quantum superiority for verifying NP-complete problems with linear optics
Authors: Arrazola, J.M. 
Diamanti, E.
Kerenidis, I.
Issue Date: 2018
Publisher: Nature Partner Journals
Citation: Arrazola, J.M., Diamanti, E., Kerenidis, I. (2018). Quantum superiority for verifying NP-complete problems with linear optics. npj Quantum Information 4 (1) : 56. ScholarBank@NUS Repository.
Rights: Attribution 4.0 International
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. © 2018, The Author(s).
Source Title: npj Quantum Information
ISSN: 2056-6387
DOI: 10.1038/s41534-018-0103-1
Rights: Attribution 4.0 International
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
10_1038_s41534-018-0103-1.pdf957.02 kBAdobe PDF




checked on Sep 30, 2022

Page view(s)

checked on Sep 29, 2022

Google ScholarTM



This item is licensed under a Creative Commons License Creative Commons