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.

44 pages; v3 - journal version

References in corpus (10)

• Quantum computational advantage using photons
• Integrated Photonic Quantum Technologies
• Photonic Boson Sampling in a Tunable Circuit
• Quantum circuits with many photons on a programmable nanophotonic chip
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Experimental Scattershot Boson Sampling
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Experimental Gaussian Boson Sampling
• Training Gaussian Boson Sampling Distributions

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