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.
arXiv comment15+21 pages, 4 figures. Comments welcome!
References in corpus (56)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum cryptography: Public key distribution and coin tossing
- Quantum information with continuous variables
- Gaussian Quantum Information
- Quantum algorithm for solving linear systems of equations
- Quantum computational advantage using photons
- Characterizing Quantum Supremacy in Near-Term Devices
- Quantum Computational Supremacy
- Continuous variable quantum information: Gaussian states and beyond
- Photonic quantum information processing: a review
- Defining and detecting quantum speedup
- Ultra-Large-Scale Continuous-Variable Cluster States Multiplexed in the Time Domain
- Boson sampling with 20 input photons in 60-mode interferometers at state spaces
- Gaussian Boson Sampling
- Universal blind quantum computation
- Efficient Classical Simulation of Continuous Variable Quantum Information Processes
- A de Finetti representation theorem for infinite dimensional quantum systems and applications to quantum cryptography
- Quantum certification and benchmarking
- Symmetry implies independence
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Boson Sampling from Gaussian States
- 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
- A detailed study of Gaussian Boson Sampling
- No imminent quantum supremacy by boson sampling
- Gaussian states in continuous variable quantum information
- Instantaneous Quantum Computation
- Verification of quantum computation: An overview of existing approaches
- Reliable quantum certification for photonic quantum technologies
- Stellar representation of non-Gaussian quantum states
- Simulating boson sampling in lossy architectures
- Classical Simulation of Quantum Supremacy Circuits
- Verification of Many-Qubit States
- How many qubits are needed for quantum computational supremacy?
- Direct certification of a class of quantum simulations
- Certification of non-Gaussian states with operational measurements
- Boson sampling with Gaussian measurements
- Pattern recognition techniques for Boson Sampling validation
- 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
- Sample complexity of device-independently certified "quantum supremacy"
- Quantum state measurement by realistic heterodyne detection
- Accrediting outputs of noisy intermediate-scale quantum computing devices
- 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
- Quantum software for linear photonic simulations
- Simulating and assessing boson sampling experiments with phase-space representations
- Signatures of Many-Particle Interference
- Homomorphic encryption of linear optics quantum computation on almost arbitrary states of light with asymptotically perfect security
- Nonadaptive fault-tolerant verification of quantum supremacy with noise
- Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
- Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
- Forging quantum data: classically defeating an IQP-based quantum test
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