Quantum superiority for verifying NP-complete problems with linear optics
arXiv:1711.02200 · doi:10.1038/s41534-018-0103-1
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.
arXiv comment10 pages, 6 figures, minor corrections, results unchanged
References in corpus (22)
- Advances in Quantum Metrology
- Review article: Linear optical quantum computing
- Quantum metrology
- Optical Quantum Computing
- Quantum fingerprinting
- Universal Linear Optics
- Boson Sampling on a Photonic Chip
- Quantum metrology from a quantum information science perspective
- Resource-efficient linear optical quantum computation
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- The SWAP test and the Hong-Ou-Mandel effect are equivalent
- No imminent quantum supremacy by boson sampling
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Experimental Quantum Fingerprinting
- Quantum Fingerprinting with Coherent States and a Constant Mean Number of Photons
- Observation of quantum fingerprinting beating the classical limit
- Quantum Communication with Coherent States and Linear Optics
- Efficient quantum communications with multiplexed coherent state fingerprints
Cited by in corpus (6)
- Experimental quantum advantage with quantum coupon collector
- Experimental demonstration of quantum advantage for one-way communication complexity
- Experimental demonstration of quantum advantage for NP verification with limited information
- Practically feasible robust quantum money with classical verification
- Quantum verification of NP problems with single photons and linear optics
- Evaluating NISQ Devices with Quadratic Nonresidues