Classical simulation of lossy boson sampling using matrix product operators

Abstract

Characterizing the computational advantage from noisy intermediate-scale quantum (NISQ) devices is an important task from theoretical and practical perspectives. Here, we numerically investigate the computational power of NISQ devices focusing on boson sampling, one of the well-known promising problems which can exhibit quantum supremacy. We study hardness of lossy boson sampling using matrix product operator (MPO) simulation to address the effect of photon-loss on classical simulability using MPO entanglement entropy (EE), which characterizes a running time of an MPO algorithm. An advantage of MPO simulation over other classical algorithms proposed to date is that its simulation accuracy can be efficiently controlled by increasing an MPO's bond dimension. Notably, we show by simulating lossy boson sampling using an MPO that as an input photon number grows, its computational cost, or MPO EE, behaves differently depending on a loss-scaling, exhibiting a different feature from that of lossless boson sampling. Especially when an output photon number scales faster than the square root of an input photon number, our study shows an exponential scaling of time complexity for MPO simulation. On the contrary, when an output photon number scales slower than the square root of an input photon number, MPO EE may decrease, indicating that an exponential time complexity might not be necessary.

arXiv comment22 pages, 7 figures

References in corpus (41)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The density-matrix renormalization group in the age of matrix product states
• Efficient classical simulation of slightly entangled quantum computations
• Quantum computational advantage using photons
• Characterizing Quantum Supremacy in Near-Term Devices
• Universal Linear Optics
• Boson Sampling on a Photonic Chip
• Matrix product states represent ground states faithfully
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
• Photonic Boson Sampling in a Tunable Circuit
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Gaussian Boson Sampling
• Entropy scaling and simulability by Matrix Product States
• 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion
• Efficient experimental validation of photonic boson sampling against the uniform distribution
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Tensor network states and algorithms in the presence of a global U(1) symmetry
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Experimental Scattershot Boson Sampling
• Generation and sampling of quantum states of light in a silicon chip
• On the experimental verification of quantum complexity in linear optics
• BosonSampling with single-photon Fock states from a bright solid-state source
• What limits the simulation of quantum computers?
• Scalable boson sampling with a single-photon device
• Efficient multiphoton sampling of molecular vibronic spectra on a superconducting bosonic processor
• Toward Scalable Boson Sampling with Photon Loss
• Functional renormalization for spontaneous symmetry breaking in the Hubbard model
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Simulating boson sampling in lossy architectures
• Regimes of classical simulability for noisy Gaussian boson sampling
• Classical simulation of photonic linear optics with lost particles
• Direct dialling of Haar random unitary matrices
• BosonSampling with Lost Photons
• Experimental Gaussian Boson Sampling
• Classical simulation of linear optics subject to nonuniform losses
• Efficient description of many-body systems with Matrix Product Density Operators
• Simulating the Dynamics of Single Photons in BosonSampling Devices with Matrix Product States
• Matrix Product States with adaptive global symmetries

Cited by in corpus (34)

• Computational advantage of quantum random sampling
• Classical algorithm for simulating experimental Gaussian boson sampling
• Classical simulation of boson sampling based on graph structure
• Noise and the frontier of quantum supremacy
• An entanglement perspective on the quantum approximate optimization algorithm
• An atomic boson sampler
• Hydrodynamics of quantum entropies in Ising chains with linear dissipation
• Quantum machine learning with Adaptive Boson Sampling via post-selection
• Spoofing cross entropy measure in boson sampling
• Simulating lossy Gaussian boson sampling with matrix product operators
• Dequantizing quantum machine learning models using tensor networks
• Tensor networks for quantum computing
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits
• Certification of Gaussian Boson Sampling via graph theory
• Entanglement entropy scaling of noisy random quantum circuits in two dimensions
• Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks
• Monitoring-induced Entanglement Entropy and Sampling Complexity
• Analysis of optical loss thresholds in the fusion-based quantum computing architecture
• Classical simulability of constant-depth linear-optical circuits with noise
• Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
• Classical simulation of bosonic linear-optical random circuits beyond linear light cone
• Entanglement in the full state vector of boson sampling
• Validation of a noisy Gaussian boson sampler via graph theory
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms
• Classical modelling of a bosonic sampler with photon collisions
• Linear-optical protocols for mitigating and suppressing noise in bosonic systems
• Classical algorithms for measurement-adaptive Gaussian circuits
• Realistic photon-number resolution in Gaussian boson sampling
• Measurement-induced entanglement in noisy 2D random circuits
• Optical Quantum Computing
• Boosting Gaussian Boson Sampling using Optical Parametric Amplification Networks