Efficient verification of Boson Sampling
arXiv:2006.03520 · doi:10.22331/q-2021-11-15-578
Abstract
The demonstration of quantum speedup, also known as quantum computational supremacy, that is the ability of quantum computers to outperform dramatically their classical counterparts, is an important milestone in the field of quantum computing. While quantum speedup experiments are gradually escaping the regime of classical simulation, they still lack efficient verification protocols and rely on partial validation. Here we derive an efficient protocol for verifying with single-mode Gaussian measurements the output states of a large class of continuous-variable quantum circuits demonstrating quantum speedup, including Boson Sampling experiments, thus enabling a convincing demonstration of quantum speedup with photonic computing. Beyond the quantum speedup milestone, our results also enable the efficient and reliable certification of a large class of intractable continuous-variable multimode quantum states.
15+21 pages, 4 figures. Comments welcome!
References in corpus (18)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum cryptography: Public key distribution and coin tossing
- Quantum algorithm for solving linear systems of equations
- Quantum computational advantage using photons
- Boson sampling with 20 input photons in 60-mode interferometers at state spaces
- A de Finetti representation theorem for infinite dimensional quantum systems and applications to quantum cryptography
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Security of continuous-variable quantum key distribution against general attacks
- Generation of one-million-mode continuous-variable cluster state by unlimited time-domain multiplexing
- Gaussian states in continuous variable quantum information
- Classical Simulation of Quantum Supremacy Circuits
- Certification of non-Gaussian states with operational measurements
- Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling
- Franck-Condon factors by counting perfect matchings of graphs with loops
- Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
- Simulating complex networks in phase space: Gaussian boson sampling
- Classical simulation of Gaussian quantum circuits with non-Gaussian input states
- Exact Boson Sampling using Gaussian continuous variable measurements
Cited by in corpus (10)
- Non-Gaussian Quantum States and Where to Find Them
- Computational advantage of quantum random sampling
- Certification of non-Gaussian states with operational measurements
- Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
- Efficient verification of entangled continuous-variable quantum states with local measurements
- Efficient validation of Boson Sampling from binned photon-number distributions
- Boson Sampling for Generalized Bosons
- On the optimal certification of von Neumann measurements
- Passive verification protocol for thermal graph states
- Continuous Variable Quantum Advantages and Applications in Quantum Optics