Experimental demonstration of quantum advantage for NP verification with limited information
arXiv:2007.15876 · doi:10.1038/s41467-021-21119-1
Abstract
In recent years, many computational tasks have been proposed as candidates for showing a quantum computational advantage, that is an advantage in the time needed to perform the task using a quantum instead of a classical machine. Nevertheless, practical demonstrations of such an advantage remain particularly challenging because of the difficulty in bringing together all necessary theoretical and experimental ingredients. Here, we show an experimental demonstration of a quantum computational advantage in a prover-verifier interactive setting, where the computational task consists in the verification of an NP-complete problem by a verifier who only gets limited information about the proof sent by an untrusted prover in the form of a series of unentangled quantum states. We provide a simple linear optical implementation that can perform this verification task efficiently (within a few seconds), while we also provide strong evidence that, fixing the size of the proof, a classical computer would take much longer time (assuming only that it takes exponential time to solve an NP-complete problem). While our computational advantage concerns a specific task in a scenario of mostly theoretical interest, it brings us a step closer to potential useful applications, such as server-client quantum computing.
References in corpus (24)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Characterizing Quantum Supremacy in Near-Term Devices
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Quantum advantage with shallow circuits
- Experimental Scattershot Boson Sampling
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Quantum Supremacy through the Quantum Approximate Optimization Algorithm
- No imminent quantum supremacy by boson sampling
- Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
- Architectures for quantum simulation showing a quantum speedup
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Experimental Quantum Fingerprinting
- Experimental Gaussian Boson Sampling
- Quantum Fingerprinting with Coherent States and a Constant Mean Number of Photons
- Quantum Randomness and Nondeterminism
- Observation of quantum fingerprinting beating the classical limit
- Quantum Communication with Coherent States and Linear Optics
- Quantum money with nearly optimal error tolerance
- Efficient quantum communications with multiplexed coherent state fingerprints
- Experimental demonstration of quantum advantage for one-way communication complexity
- Practically feasible robust quantum money with classical verification
- Quantum superiority for verifying NP-complete problems with linear optics
Cited by in corpus (10)
- Demonstration of algorithmic quantum speedup
- Experimental quantum advantage with quantum coupon collector
- symQV: Automated Symbolic Verification of Quantum Programs
- Variational Quantum Cloning: Improving Practicality for Quantum Cryptanalysis
- Quantum verification of NP problems with single photons and linear optics
- Robust excitation of C-band quantum dots for quantum communication
- Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
- Dynamics of single-mode nonclassicalities and quantum correlations in the Jaynes-Cummings model
- Efficient Light Propagation Algorithm using Quantum Computers
- Evaluating NISQ Devices with Quadratic Nonresidues