Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling

Abstract

Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make progress in improving both the theoretical evidence and experimental prospects. We provide evidence for the hardness of GBS, comparable to the strongest theoretical proposals for QCA. We also propose a new QCA architecture we call high-dimensional GBS, which is programmable and can be implemented with low loss using few optical components. We show that particular algorithms for simulating GBS are outperformed by high-dimensional GBS experiments at modest system sizes. This work thus opens the path to demonstrating QCA with programmable photonic processors.

v3: 24 pages, 5 figures. Close to accepted version

References in corpus (19)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Quantum circuits with many photons on a programmable nanophotonic chip
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• Scalable boson-sampling with time-bin encoding using a loop-based architecture
• Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
• A 12-mode Universal Photonic Processor for Quantum Information Processing
• Tensor Networks in a Nutshell
• Quantum process tomography with coherent states
• Fusion-based quantum computation
• Gaussian Noise Sensitivity and BosonSampling
• Noise and the frontier of quantum supremacy
• Universal extensions of restricted classes of quantum operations
• The complexity of simulating constant-depth BosonSampling
• Noise Threshold of Quantum Supremacy
• Classical simulation of bosonic linear-optical random circuits beyond linear light cone
• Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions

Cited by in corpus (49)

• Computational advantage of quantum random sampling
• Triggered single-photon generation and resonance fluorescence in ultra-low loss integrated photonic circuits
• NISQ Computers: A Path to Quantum Supremacy
• Beyond photon pairs: Nonlinear quantum photonics in the high-gain regime
• Resources for bosonic quantum computational advantage
• Classical algorithm for simulating experimental Gaussian boson sampling
• A universal programmable Gaussian Boson Sampler for drug discovery
• Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
• The Complexity of Bipartite Gaussian Boson Sampling
• Classical simulation of boson sampling based on graph structure
• Quantum simulation of thermodynamics in an integrated quantum photonic processor
• Matrix decompositions in Quantum Optics: Takagi/Autonne, Bloch-Messiah/Euler, Iwasawa, and Williamson
• Generation of three-dimensional cluster entangled state
• Spoofing cross entropy measure in boson sampling
• Simulating lossy Gaussian boson sampling with matrix product operators
• Waveguided sources of consistent, single-temporal-mode squeezed light: the good, the bad, and the ugly
• Classical models may be a better explanation of the Jiuzhang 1.0 Gaussian Boson Sampler than its targeted squeezed light model
• Quantum-inspired classical algorithm for molecular vibronic spectra
• Riemannian optimization of photonic quantum circuits in phase and Fock space
• Quantum-inspired permanent identities
• Page curves and typical entanglement in linear optics
• Hybrid Quantum-Classical Boson Sampling Algorithm for Molecular Vibrationally Resolved Electronic Spectroscopy with Duschinsky Rotation and Anharmonicity
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• Certification of Gaussian Boson Sampling via graph theory
• Deep thermalization in Gaussian continuous-variable quantum systems
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Full Quantum Process Tomography of a Universal Entangling Gate on an IBM's Quantum Computer
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• 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
• Boson Sampling for Generalized Bosons
• Approximating outcome probabilities of linear optical circuits
• Accurate Unsupervised Photon Counting from Transition Edge Sensor Signals
• Transition of Anticoncentration in Gaussian Boson Sampling
• Machine Learning for maximizing the memristivity of single and coupled quantum memristors
• The Second Moment of Hafnians in Gaussian Boson Sampling
• Gaussian boson sampling with click-counting detectors
• Validation of a noisy Gaussian boson sampler via graph theory
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Average Rényi Entanglement Entropy in Gaussian Boson Sampling
• Quantum computational advantage of noisy boson sampling with partially distinguishable photons
• Quantum interference with time-frequency modes and multiple-photons generated by a silicon nitride microresonator
• Matrix phase-space representations for gaussian boson sampling
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
• Variational Tensor Network Simulation of Gaussian Boson Sampling and Beyond
• Complexity of Gaussian quantum optics with a limited number of non-linearities
• Boundaries for quantum advantage with single photons and loop-based time-bin interferometers
• Classical algorithms for measurement-adaptive Gaussian circuits