Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
arXiv:2102.12474 · doi:10.1126/sciadv.abi7894
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.
arXiv commentv3: 24 pages, 5 figures. Close to accepted version
References in corpus (52)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum computational advantage using photons
- Characterizing Quantum Supremacy in Near-Term Devices
- Quantum circuits with many photons on a programmable nanophotonic chip
- Boson sampling with 20 input photons in 60-mode interferometers at state spaces
- Gaussian Boson Sampling
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- Deterministic generation of a two-dimensional cluster state
- Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Hyper-optimized tensor network contraction
- A detailed study of Gaussian Boson Sampling
- No imminent quantum supremacy by boson sampling
- Scalable boson sampling with a single-photon device
- Deploying a Top-100 Supercomputer for Large Parallel Workloads: the Niagara Supercomputer
- A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
- 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
- Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
- Tensor Networks in a Nutshell
- How many entries of a typical orthogonal matrix can be approximated by independent normals?
- A Note on Linear Optics Gates by Post-Selection
- Photon distribution for one mode mixed light with generic gaussian Wigner function
- Simulating boson sampling in lossy architectures
- Architectures for quantum simulation showing a quantum speedup
- Regimes of classical simulability for noisy Gaussian boson sampling
- Classical simulation of photonic linear optics with lost particles
- Faster identification of optimal contraction sequences for tensor networks
- Quantum process tomography with coherent states
- Simulating realistic non-Gaussian state preparation
- On-demand photonic entanglement synthesizer
- Fusion-based quantum computation
- Scalable squeezed light source for continuous variable quantum sampling
- Anticoncentration theorems for schemes showing a quantum speedup
- Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
- A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
- Probing Measurement Induced Effects in Quantum Walks via Recurrence
- Tensor network states in time-bin quantum optics
- Proposal for Quantum Simulation via All-Optically Generated Tensor Network States
- Noise and the frontier of quantum supremacy
- Gaussian Noise Sensitivity and BosonSampling
- Universal extensions of restricted classes of quantum operations
- Quantum supremacy and random circuits
- Photonic quantum walks with four-dimensional coins
- The complexity of simulating constant-depth BosonSampling
- Noise Threshold of Quantum Supremacy
- Implementing Scalable Boson Sampling with Time-Bin Encoding: Analysis of Loss, Mode Mismatch, and Time Jitter
- Distances between Random Orthogonal Matrices and Independent Normals
- 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