Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy

Abstract

Boson sampling is a sampling task proven to be hard to simulate efficiently using classical computers under plausible assumptions, which makes it an appealing candidate for quantum supremacy. However, due to a large noise rate for near-term quantum devices, it is still unclear whether those noisy devices maintain the quantum advantage for much larger quantum systems. Since the noise rate typically grows with the circuit depth, an alternative is to find evidence of simulation hardness at the shallow-depth quantum circuit. To find the evidence, one way is to identify the minimum depth required for the average-case hardness of approximating output probabilities, which is considered a necessary condition for the state-of-the-art technique to prove the simulation hardness of boson sampling. In this work, we analyze the output probability distribution of shallow-depth boson sampling for Fock-states and Gaussian states, and examine the limitation of the average-case hardness argument at this shallow-depth regime for geometrically local architectures. We propose a shallow-depth linear optical circuit architecture that can overcome the problems associated with geometrically local architectures. Our numerical results suggest that this architecture demonstrates possibilities of average-case hardness properties in a shallow-depth regime, through its resemblance to the global Haar-random boson sampling circuit. This result implies that the corresponding architecture has the potential to be utilized for scalable quantum supremacy with its shallow-depth boson sampling.

References in corpus (51)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Efficient classical simulation of slightly entangled quantum computations
• Quantum computational advantage using photons
• Efficient simulation of one-dimensional quantum many-body systems
• Characterizing Quantum Supremacy in Near-Term Devices
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Strong quantum computational advantage using a superconducting quantum processor
• Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms
• Matrix product states represent ground states faithfully
• Gaussian Boson Sampling
• Chaos and complexity by design
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Entropy scaling and simulability by Matrix Product States
• Evenly distributed unitaries: on the structure of unitary designs
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Chaos, Complexity, and Random Matrices
• Experimental Two-dimensional Quantum Walk on a Photonic Chip
• Random Quantum Circuits and Pseudo-Random Operators: Theory and Applications
• Measuring Gaussian quantum information and correlations using the Renyi entropy of order 2
• Efficient classical simulation of random shallow 2D quantum circuits
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• High-dimensional frequency crystals and quantum walks in electro-optic microcombs
• Spectral form factors and late time quantum chaos
• Efficient algorithm for boson sampling with partially distinguishable photons
• Simulating boson sampling in lossy architectures
• Architectures for quantum simulation showing a quantum speedup
• Convergence Conditions for Random Quantum Circuits
• Scalable Implementation of Boson Sampling with Trapped Ions
• Regimes of classical simulability for noisy Gaussian boson sampling
• Classical simulation of photonic linear optics with lost particles
• Schur complement inequalities for covariance matrices and monogamy of quantum correlations
• Direct dialling of Haar random unitary matrices
• Anticoncentration theorems for schemes showing a quantum speedup
• Scalable and Programmable Phononic Network with Trapped Ions
• A proposal for a scalable universal bosonic simulator using individually trapped ions
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Dynamical phase transitions in sampling complexity
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Classical simulation of boson sampling based on graph structure
• Classical simulation of linear optics subject to nonuniform losses
• Noise in BosonSampling and the threshold of efficient classical simulatability
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• Generating Haar-uniform Randomness using Stochastic Quantum Walks on a Photonic Chip
• Entanglement formation in continuous-variable random quantum networks
• On the Strong Subadditivity of the Rényi entropies for bosonic and fermionic Gaussian states
• Page curves and typical entanglement in linear optics
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Classical simulation of boson sampling with sparse output

Cited by in corpus (6)

• Classical simulability of constant-depth linear-optical circuits with noise
• General protocols for the efficient distillation of indistinguishable photons
• Quantum interference with time-frequency modes and multiple-photons generated by a silicon nitride microresonator
• Quantum computational advantage of noisy boson sampling with partially distinguishable photons
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Boundaries for quantum advantage with single photons and loop-based time-bin interferometers