The classical complexity of boson sampling

DOI10.48550/ARXIV.1706.01260MaRDI QIDQ126355zbMATH OpenFDO

Authors Peter Clifford, Raphaël Clifford, Peter Clifford, Raphaël Clifford

Publication date 5 June 2017

Full work available at URL https://arxiv.org/abs/1706.01260, http://dl.acm.org/citation.cfm?id=3175276

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Nuclear physics (81V35)

Abstract: We study the classical complexity of the exact Boson Sampling problem where the objective is to produce provably correct random samples from a particular quantum mechanical distribution. The computational framework was proposed by Aaronson and Arkhipov in 2011 as an attainable demonstration of `quantum supremacy', that is a practical quantum computing experiment able to produce output at a speed beyond the reach of classical (that is non-quantum) computer hardware. Since its introduction Boson Sampling has been the subject of intense international research in the world of quantum computing. On the face of it, the problem is challenging for classical computation. Aaronson and Arkhipov show that exact Boson Sampling is not efficiently solvable by a classical computer unless $$ and the polynomial hierarchy collapses to the third level. The fastest known exact classical algorithm for the standard Boson Sampling problem takes $O(m+n-1choosenn{2}^n)$ time to produce samples for a system with input size $n$ and $m$ output modes, making it infeasible for anything but the smallest values of $n$ and $m$. We give an algorithm that is much faster, running in $O(n{2}^n+operatornamepoly(m,n))$ time and $O(m)$ additional space. The algorithm is simple to implement and has low constant factor overheads. As a consequence our classical algorithm is able to solve the exact Boson Sampling problem for system sizes far beyond current photonic quantum computing experimentation, thereby significantly reducing the likelihood of achieving near-term quantum supremacy in the context of Boson Sampling.

Recommendations

• The computational complexity of linear optics
• The computational complexity of linear optics
• On the classical complexity of sampling from quantum interference of indistinguishable bosons
• Towards quantum supremacy with lossy scattershot boson sampling
• Complexity-theoretic foundations of quantum supremacy experiments

Cited in

(25)

• Implementation of photon partial distinguishability in a quantum optical circuit simulation
• Strong simulation of linear optical processes
• Multi-boson correlation sampling
• The computational complexity of linear optics
• Sampling of bosonic qubits
• On the classical hardness of spoofing linear cross-entropy benchmarking
• The computational complexity of linear optics
• Complexity-theoretic foundations of quantum supremacy experiments
• Graph isomorphism and Gaussian boson sampling
• Unitary matrix decompositions for optimal and modular linear optics architectures
• The equivalence of sampling and searching
• Partial distinguishability as a coherence resource in boson sampling
• Efficient computation of permanents, with applications to boson sampling and random matrices
• Classical benchmarking of Gaussian boson sampling on the Titan supercomputer
• Quantum path computing: computing architecture with propagation paths in multiple plane diffraction of classical sources of fermion and boson particles
• Towards quantum supremacy with lossy scattershot boson sampling
• Boson-sampling with non-interacting fermions
• Majorization and the time complexity of linear optical networks
• On the classical complexity of sampling from quantum interference of indistinguishable bosons
• Models in quantum computing: a systematic review
• A quantum hash function with grouped coarse-grained boson sampling
• Cryptographic one-way function based on boson sampling
• BosonSampling
• Boson sampling with non-identical single photons
• Vibronic spectra of molecules – an experiment with a quantum computer simulator

This page was built for publication: The classical complexity of boson sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q126355)