The Complexity of Bipartite Gaussian Boson Sampling

Abstract

Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of reach for classical devices. There is therefore significant interest, from the perspective of computational complexity theory, in solidifying the mathematical foundation for the hardness of simulating these devices. We show that, under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from ideal Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof. Crucial to the proof is a new method for programming a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. This technique is a generalization of Scattershot BosonSampling that we call BipartiteGBS. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., the high-collision regime) by showing that the ability to approximate permanents of matrices with repeated rows/columns confers the ability to approximate permanents of matrices with no repetitions. The reduction suffices to prove that GBS is hard in the constant-collision regime.

arXiv comment44 pages; v3 - journal version

References in corpus (37)

• Gaussian Quantum Information
• Quantum computational advantage using photons
• Integrated Photonic Quantum Technologies
• Boson Sampling on a Photonic Chip
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Photonic Boson Sampling in a Tunable Circuit
• Quantum circuits with many photons on a programmable nanophotonic chip
• Gaussian Boson Sampling
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Boson Sampling for Molecular Vibronic Spectra
• Boson Sampling from Gaussian States
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Experimental Scattershot Boson Sampling
• A detailed study of Gaussian Boson Sampling
• No imminent quantum supremacy by boson sampling
• Molecular Docking with Gaussian Boson Sampling
• Using Gaussian Boson Sampling to Find Dense Subgraphs
• Gaussian Boson Sampling using threshold detectors
• How many entries of a typical orthogonal matrix can be approximated by independent normals?
• Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Simulating boson sampling in lossy architectures
• A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Regimes of classical simulability for noisy Gaussian boson sampling
• BosonSampling with Lost Photons
• Experimental Gaussian Boson Sampling
• Simple factorization of unitary transformations
• Scalable squeezed light source for continuous variable quantum sampling
• Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
• Boson sampling with Gaussian measurements
• Point Processes with Gaussian Boson Sampling
• Further Compactifying Linear Optical Unitaries
• Quantum Algorithm for Simulating Molecular Vibrational Excitations
• Training Gaussian Boson Sampling Distributions
• Simulating complex networks in phase space: Gaussian boson sampling

Cited by in corpus (27)

• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Computational advantage of quantum random sampling
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Matrix decompositions in Quantum Optics: Takagi/Autonne, Bloch-Messiah/Euler, Iwasawa, and Williamson
• Classical models may be a better explanation of the Jiuzhang 1.0 Gaussian Boson Sampler than its targeted squeezed light model
• Riemannian optimization of photonic quantum circuits in phase and Fock space
• Page curves and typical entanglement in linear optics
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• Deep thermalization in Gaussian continuous-variable quantum systems
• Gain-induced group delay in spontaneous parametric down-conversion
• Photon-number moments and cumulants of Gaussian states
• Near-optimal decomposition of unitary matrices using phase masks and the discrete Fourier transform
• Perfect pulsed inline twin-beam squeezers
• Approximating outcome probabilities of linear optical circuits
• Multiphoton Correlations between Quantum Images
• Transition of Anticoncentration in Gaussian Boson Sampling
• The stellar decomposition of Gaussian quantum states
• Accurate Unsupervised Photon Counting from Transition Edge Sensor Signals
• The Second Moment of Hafnians in Gaussian Boson Sampling
• Gaussian boson sampling at finite temperature
• Gaussian boson sampling with click-counting detectors
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Quantum interference with time-frequency modes and multiple-photons generated by a silicon nitride microresonator
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
• Quantum computational advantage of noisy boson sampling with partially distinguishable photons
• Boosting Gaussian Boson Sampling using Optical Parametric Amplification Networks
• Complexity of Gaussian quantum optics with a limited number of non-linearities