The complexity of simulating constant-depth BosonSampling
arXiv:1412.6788 · doi:10.1103/PhysRevA.91.042316
Abstract
BosonSampling is a restricted model of quantum computation proposed recently, where a non-adaptive linear-optical network is used to solve a sampling problem that seems to be hard for classical computers. Here we show that, even if the linear-optical network has a constant number (greater than four) of beam splitter layers, the exact version of the BosonSampling problem is still classically hard, unless the polynomial hierarchy collapses to its third level. This is based on similar result known for constant-depth quantum circuits and circuits of 2-local commuting gates (IQP).
9 pages, 3 figures
References in corpus (20)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Review article: Linear optical quantum computing
- Quantum Teleportation is a Universal Computational Primitive
- On the Power of One Bit of Quantum Information
- Boson Sampling on a Photonic Chip
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Universal blind quantum computation
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- On the experimental verification of quantum complexity in linear optics
- Unified derivations of measurement-based schemes for quantum computation
- A Note on Linear Optics Gates by Post-Selection
- On the hardness of classically simulating the one clean qubit model
- Error tolerance of the BosonSampling model for linear optics quantum computing
- General rules for bosonic bunching in multimode interferometers
- Quantum computation by local measurement
- Measurement-based classical computation
- Spontaneous parametric down-conversion photon sources are scalable in the asymptotic limit for boson-sampling
Cited by in corpus (19)
- Quantum Supremacy through the Quantum Approximate Optimization Algorithm
- Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
- Regimes of classical simulability for noisy Gaussian boson sampling
- Verification of Many-Qubit States
- Classical simulation of photonic linear optics with lost particles
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- Dynamical phase transitions in sampling complexity
- Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
- Classical simulation of boson sampling based on graph structure
- Driven Boson Sampling
- Efficient computation of permanents, with applications to boson sampling and random matrices
- Complexity phase diagram for interacting and long-range bosonic Hamiltonians
- Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy
- Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
- Classical simulability of constant-depth linear-optical circuits with noise
- Classical simulation of bosonic linear-optical random circuits beyond linear light cone
- SUperman: Efficient Permanent Computation on GPUs
- On computational complexity and average-case hardness of shallow-depth boson sampling
- Average Rényi Entanglement Entropy in Gaussian Boson Sampling