Boson Sampling from Gaussian States
arXiv:1305.4346 · doi:10.1103/PhysRevLett.113.100502
Abstract
We pose a generalized Boson Sampling problem. Strong evidence exists that such a problem becomes intractable on a classical computer as a function of the number of Bosons. We describe a quantum optical processor that can solve this problem efficiently based on Gaussian input states, a linear optical network and non-adaptive photon counting measurements. All the elements required to build such a processor currently exist. The demonstration of such a device would provide the first empirical evidence that quantum computers can indeed outperform classical computers and could lead to applications.
References in corpus (4)
Cited by in corpus (195)
- Quantum Chemistry in the Age of Quantum Computing
- Quantum information processing with superconducting circuits: a review
- Photonic quantum information processing: a review
- Photonic quantum information processing: a concise review
- Experimental ten-photon entanglement
- Quantum circuits with many photons on a programmable nanophotonic chip
- Gaussian Boson Sampling
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion
- Continuous-variable quantum neural networks
- Boson Sampling for Molecular Vibronic Spectra
- Strawberry Fields: A Software Platform for Photonic Quantum Computing
- Experimental Scattershot Boson Sampling
- Generation and sampling of quantum states of light in a silicon chip
- On the experimental verification of quantum complexity in linear optics
- Two-photon interference: the Hong-Ou-Mandel effect
- BosonSampling with single-photon Fock states from a bright solid-state source
- Near-ideal spontaneous photon sources in silicon quantum photonics
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- A detailed study of Gaussian Boson Sampling
- Scalable boson sampling with a single-photon device
- Molecular Docking with Gaussian Boson Sampling
- Computational advantage of quantum random sampling
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Using Gaussian Boson Sampling to Find Dense Subgraphs
- Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
- Toward Scalable Boson Sampling with Photon Loss
- Noisy intermediate-scale quantum computers
- Gaussian Boson Sampling using threshold detectors
- A chip-based array of near-identical, pure, heralded single photon sources
- An integrated source of spectrally filtered correlated photons for large scale quantum photonic systems
- Efficient algorithm for boson sampling with partially distinguishable photons
- Partial indistinguishability theory for multi-photon experiments in multiport devices
- Simulating boson sampling in lossy architectures
- Gaussian Boson Sampling for perfect matchings of arbitrary graphs
- Interference of Identical Particles from Entanglement to Boson-Sampling
- Quantum Indistinguishability by Path Identity: The awakening of a sleeping beauty
- A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
- What can quantum optics say about computational complexity theory?
- The Boundary for Quantum Advantage in Gaussian Boson Sampling
- Operational resource theory of continuous-variable nonclassicality
- Regimes of classical simulability for noisy Gaussian boson sampling
- Classical simulation of photonic linear optics with lost particles
- Multiboson Correlation Interferometry with arbitrary single-photon pure states
- Quantum simulation of molecular spectroscopy in trapped-ion device
- Experimental Gaussian Boson Sampling
- Sufficient bound on the mode mismatch of single photons for scalability of the boson sampling computer
- Vibronic Boson Sampling: Generalized Gaussian Boson Sampling for Molecular Vibronic Spectra at Finite Temperature
- Universality of Generalized Bunching and Efficient Assessment of Boson Sampling
- Resources for bosonic quantum computational advantage
- Verified measurement-based quantum computing with hypergraph states
- Continuous-Variable Instantaneous Quantum Computing is hard to sample
- Production of photonic universal quantum gates enhanced by machine learning
- Quantum Experiments and Graphs II: Quantum Interference, Computation and State Generation
- Quantum approximate optimization with Gaussian boson sampling
- Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
- A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
- Microwave Boson Sampling
- Reframing SU(1,1) interferometry
- Boson sampling with Gaussian measurements
- Suppression laws for multi-particle interference in Sylvester interferometers
- A universal programmable Gaussian Boson Sampler for drug discovery
- Reconfigurable continuously-coupled 3D photonic circuit for Boson Sampling experiments
- Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling
- Pattern recognition techniques for Boson Sampling validation
- From the Physics to the Computational Complexity of Multiboson Correlation Interference
- Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
- The Complexity of Bipartite Gaussian Boson Sampling
- Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
- Experimental generalized quantum suppression law in Sylvester interferometers
- Quantum Entropy and Central Limit Theorem
- Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states---The quantum-classical divide and computational-complexity transitions in linear optics
- Quantum computation and simulation with vibrational modes of trapped ions
- Efficient representation of Gaussian states for multi-mode non-Gaussian quantum state engineering via subtraction of arbitrary number of photons
- Conditional non-Gaussian quantum state preparation
- Benchmarking of Gaussian boson sampling using two-point correlators
- Quantum Experiments and Hypergraphs: Multi-Photon Sources for Quantum Interference, Quantum Computation and Quantum Entanglement
- Quantum simulation of thermodynamics in an integrated quantum photonic processor
- An atomic boson sampler
- Simulating complex networks in phase space: Gaussian boson sampling
- Tight bound on trace distance between a realistic device with partially indistinguishable bosons and the ideal Boson Sampling
- Creating large Fock states and massively squeezed states in optics using systems with nonlinear bound states in the continuum
- Efficient verification of Boson Sampling
- Multi-Boson Correlation Sampling with Multi-mode Thermal Sources
- Multiparameter estimation with single photons
- Simulability of Imperfect Gaussian and Superposition Boson Sampling
- A simple scheme for universal linear optics quantum computing with constant experimental complexity using fiber-loops
- Noise in BosonSampling and the threshold of efficient classical simulatability
- Heralded-Multiplexed High-Efficiency Cascaded Source of Dual-Rail Polarization-Entangled Photon Pairs using Spontaneous Parametric Down Conversion
- Towards Quantum Supremacy with Lossy Scattershot Boson Sampling
- Driven Boson Sampling
- Quantum Correlations in Nonlocal BosonSampling
- Sampling generalized cat states with linear optics is probably hard
- Accurate and precise characterization of linear optical interferometers
- Exact Boson Sampling using Gaussian continuous variable measurements
- Understanding high gain twin beam sources using cascaded stimulated emission
- Generalized concurrence in boson sampling
- Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
- Matrix Product States for Quantum Stochastic Modelling
- Simulating lossy Gaussian boson sampling with matrix product operators
- All-optical quantum computing using cubic phase gates
- Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
- Holomorphic representation of quantum computations
- Testing multi-photon interference on a silicon chip
- Information processing at the speed of light
- Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer
- Sampling of bosonic qubits
- Decision and function problems based on boson sampling
- High Dimensional Unitary Transformations and Boson Sampling on Temporal Modes using Dispersive Optics
- Implementing quantum algorithms on temporal photonic cluster states
- Distinguishing noisy boson sampling from classical simulations
- Boson sampling with non-identical single photons
- Implementing Scalable Boson Sampling with Time-Bin Encoding: Analysis of Loss, Mode Mismatch, and Time Jitter
- Accelerating quantum optics experiments with statistical learning
- Threshold detection statistics of bosonic states
- Signatures of Many-Particle Interference
- Measurement-Based Linear Optics
- Digital quantum simulation of linear and nonlinear optical elements
- The scaling of boson sampling experiments
- Quantum-inspired permanent identities
- Page curves and typical entanglement in linear optics
- A certification scheme for the boson sampler
- Deterministic generation of arbitrary n-photon states in an integrated photonic system
- Deep thermalization in Gaussian continuous-variable quantum systems
- Certification of Gaussian Boson Sampling via graph theory
- Phase-space negativity as a computational resource for quantum kernel methods
- Scattershot multiboson correlation sampling with random photonic inner-mode multiplexing
- Simulating arbitrary Gaussian circuits with linear optics
- Quantum supremacy of the many-body fluctuations in the occupations of the excited particle states in a Bose-Einstein-condensed gas
- Determining the squeezing in multimode fields using nonlocal quantum probes
- Simulating the Photon Statistics of Multimode Gaussian States by Automatic Differentiation of Generating Functions
- Semi-device independent characterization of multiphoton indistinguishability
- Classical simulation of boson sampling with sparse output
- Optimal entanglement enhancing via conditional measurements
- Efficient validation of Boson Sampling from binned photon-number distributions
- Distinguishability in quantum interference with the squeezed states
- Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy
- Multi-photon interference in the spectral domain by direct heralding of superposition states
- Quantum error cancellation in photonic systems -- undoing photon losses
- In situ characterization of linear-optical networks in randomized boson sampling
- Sample caching Markov chain Monte Carlo approach to boson sampling simulation
- Boson Sampling for Generalized Bosons
- Quantum Path Computing: Computing Architecture with Propagation Paths in Multiple Plane Diffraction of Classical Sources of Fermion and Boson Particles
- Partial distinguishability and photon counting probabilities in linear multiport devices
- Experimental linear optical computing of the matrix permanent
- Linear multiport photonic interferometers: loss analysis of temporally-encoded architectures
- Partial Distinguishability as a Coherence Resource in Boson Sampling
- Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
- Multimode Metrology via Scattershot Sampling
- Multi-channel quantum noise suppression and phase-sensitive modulation in a hybrid optical resonant cavity system
- High performance Boson Sampling simulation via data-flow engines
- Transition of Anticoncentration in Gaussian Boson Sampling
- Boson sampling with random numbers of photons
- The Second Moment of Hafnians in Gaussian Boson Sampling
- Quantum Computing for Molecular Vibronic Spectra and Gaussian Boson Sampling
- Quantum De Moivre-Laplace theorem for noninteracting indistinguishable particles
- Sampling Problems on a Quantum Computer
- A duality at the heart of Gaussian boson sampling
- Validation of a noisy Gaussian boson sampler via graph theory
- Absorption to Fluctuating Bunching States in Non-Unitary Boson Dynamics
- Continuous Variable Quantum Advantages and Applications in Quantum Optics
- Isoenergetic model for optical downconversion and error-specific limits of the parametric approximation
- Boson sampling with ultracold atoms in a programmable optical lattice
- Improving Continuous-variable Quantum Channels with Unitary Averaging
- Quantum estimation bound of Gaussian matrix permanent
- Interferometrically estimating a quadratic form for any immanant of a matrix and its permutations
- Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
- QOptCraft: A Python package for the design and study of linear optical quantum systems
- Speedup in Classical Simulation of Gaussian Boson Sampling
- Average Rényi Entanglement Entropy in Gaussian Boson Sampling
- On computational complexity and average-case hardness of shallow-depth boson sampling
- Photonic Simulation of Localization Phenomena Using Boson Sampling
- Observation of Lie algebraic invariants in Quantum Linear Optics
- Noise-reduction of multimode Gaussian Boson Sampling circuits via Unitary Averaging
- Resource-efficient universal photonic processor based on time-multiplexed hybrid architectures
- Unified boson sampling
- Nonlinear-linear duality for multipath quantum interference
- Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
- Distribution of Gaussian Entanglement in Linear Optical Systems
- Sampling and the complexity of nature
- Controllable Quantum Interference from Two-Photon Scattershot Sources
- Power of photonic states: from quantum computation to cosmology
- Physical Unclonable Functions with Boson Sampling
- Generalized Interference of Fermions and Bosons
- Free Quantum Computing
- Maximum heralding probabilities of nonclassical-state generation from a two-mode Gaussian state via photon-counting measurements
- Simplified scheme for continuous-variable entanglement distillation: multicopy distillation of Gaussian entanglement without heralding Gaussian measurements
- Optical Quantum Computing
- Sample space filling analysis for boson sampling validation
- Resourcefulness of non-classical continuous-variable quantum gates
- Variational Tensor Network Simulation of Gaussian Boson Sampling and Beyond
- Hardness of efficiently generating ground states in postselected quantum computation
- The Computational Power of Non-interacting Particles
- Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
- Classical modelling of a bosonic sampler with photon collisions