Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1111.2426 · Physical Review A

Error tolerance of the boson-sampling model for linear optics quantum computing

Peter P. Rohde, Timothy C. Ralph

Published Feb 23, 2012• 81 citations
arXivHTMLPDF

Abstract

Linear optics quantum computing is a promising approach to implementing scalable quantum computation. However, this approach has very demanding physical resource requirements. Recently, Aaronson and Arkhipov (e-print arXiv:1011.3245) showed that a simplified model, which avoids the requirement for fast feed-forward and postselection, while likely not capable of solving BQP-complete problems efficiently, can solve an interesting sampling problem believed to be classically hard. Loss and mode mismatch are the dominant sources of error in such systems. We provide evidence that even lossy systems or systems with mode mismatch are likely to be classically hard to solve. This is of practical interest to experimentalists wishing to demonstrate such systems since it suggests that, even with errors in their implementation, they are likely implementing an algorithm that is classically hard to solve. Our results also equivalently apply to the multiwalker quantum walk model.

DOI
10.1103/physreva.85.022332

Related papers

Sufficient condition for the mode mismatch of single photons for scalability of the boson-sampling computer

V. S. Shchesnovich

The boson sampler proposed by Aaronson and Arkhipov is a nonuniversal quantum computer, which can serve as evidence against the extended Church-Turing thesis. It samples the probability distribution at the output of a linear unitary optical network with indistinguishable single photons at the input. Four experimental groups have already tested their small-scale prototypes with up to four photons. A boson sampler with a few dozens of single photons is believed to be hard to simulate on a classical computer. For scalability of a realistic boson sampler with current technology it is necessary to know the effect of the photon mode mismatch on its operation. Here a nondeterministic model of the boson sampler is analyzed, which employs partially indistinguishable single photons emitted by identical sources. A sufficient condition on the average mutual fidelity $\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ of the single photons is found, which guarantees that the realistic boson sampler outperforms the classical computer. Moreover, the boson-sampler computer with partially indistinguishable single photons is scalable and has more power than classical computers when the single-photon mode mismatch $1\ensuremath{-}\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ scales as $O({N}^{\ensuremath{-}3/2})$ with the total number of photons $N$.

arXiv:1311.6796•Physical Review A•Feb 24, 2014•72 citations

Evidence for the conjecture that sampling generalized cat states with linear optics is hard

Peter P. Rohde, Keith R. Motes, Paul Knott +3 more

Boson sampling has been presented as a simplified model for linear optical quantum computing. In the boson-sampling model, Fock states are passed through a linear optics network and sampled via number-resolved photodetection. It has been shown that this sampling problem likely cannot be efficiently classically simulated. This raises the question as to whether there are other quantum states of light for which the equivalent sampling problem is also computationally hard. We present evidence, without using a full complexity proof, that a very broad class of quantum states of light---arbitrary superpositions of two or more coherent states---when evolved via passive linear optics and sampled with number-resolved photodetection, likely implements a classically hard sampling problem.

arXiv:1310.0297•Physical Review A•Jan 30, 2015•28 citations

Efficient Certification of Boson Sampling in Waveguide Lattices with parity-like Symmetry

Christoph Dittel, Robert Keil, Malte C. Tichy +6 more

The goal of universal quantum computing that challenges classical computation is still far from being reached. However, Aaronson and Arkhipov recently proposed a nonuniversal quantum computer [1] to solve sampling problems of identical bosons in linear-optical networks which are intractable for classical computers. Once outperforming the classically computable limit of such a boson-sampling device, the very hardness of boson sampling excludes any straightforward efficient verification of the results. A computationally accessible while physically non-trivial instance of the problem was proposed to prove many-particle interference and thereby benchmark the functionality of a candidate device [2]. However, the Fourier matrix proposed in [2] is a highly artificial singular case that remains challenging to implement experimentally.

European Quantum Electronics Conference (EQEC)•Jun 21, 2015•0 citations

The Classical Complexity of Boson Sampling

Peter Clifford, Raphaël Clifford A

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 in STOC ’11 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 P#P = BPPNP and the polynomial hierarchy collapses to the third level. The fastest known exact classical algorithm for the standard Boson Sampling problem requires 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 time and 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.

arXiv:1706.01260•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•26 citations

Sampling complexity of Bosonic random walkers on a one-dimensional lattice

Gopikrishnan Muraleedharan, Akimasa Miyake, Ivan Deutsch

Computers based quantum logic are believed to solve problems faster and more efficiently than computers based on classical boolean logic. However, a large-scale universal quantum computer with error correction may not be realized in near future. But we can ask the question: can we devise a specific problem that a quantum device can solve faster than current state of the art super computers? One such problem is the so called "Boson Sampling" problem introduced by Aaronson and Arkhipov. The problem is to generate random numbers according to same distribution as the output number configurations of photons in linear optics. It was shown that this is a very hard task for classical computers, but can be realized using quantum devices. However, realizing this in photonic systems is proving to be harder than ever because of various challenges in preparation and measurements. We propose and analyze an alternate platform to implement this problem, ultra-cold atoms trapped in one-dimensional optical lattices.

•Jan 1, 2018•0 citations

BosonSampling with lost photons

Scott Aaronson, Daniel J. Brod

BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here, we investigate the complexity of BosonSampling under photon losses, more specifically, the case where an unknown subset of the photons is randomly lost at the sources. We show that if $k$ out of $n$ photons are lost, then we cannot sample classically from a distribution that is $1/{n}^{\mathrm{\ensuremath{\Theta}}(k)}$ close (in total variation distance) to the ideal distribution, unless a ${\text{BPP}}^{\text{NP}}$ machine can estimate the permanents of Gaussian matrices in ${n}^{O(k)}$ time. In particular, if $k$ is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case.

arXiv:1510.05245•Physical Review A•Jan 21, 2016•78 citations
Linear optics quantum computing is a promising approach to implementing scalable quantum computation. However, this approach has very demanding physical resource requirements. Recently, Aaronson and Arkhipov (e-print arXiv:1011.3245) showed that a simplified model, which avoids the requirement for fast feed-forward and postselection, while likely not capable of solving BQP-complete problems efficiently, can solve an interesting sampling problem believed to be classically hard. Loss and mode mismatch are the dominant sources of error in such systems. We provide evidence that even lossy systems or systems with mode mismatch are likely to be classically hard to solve. This is of practical interest to experimentalists wishing to demonstrate such systems since it suggests that, even with errors in their implementation, they are likely implementing an algorithm that is classically hard to solve. Our results also equivalently apply to the multiwalker quantum walk model.
The boson sampler proposed by Aaronson and Arkhipov is a nonuniversal quantum computer, which can serve as evidence against the extended Church-Turing thesis. It samples the probability distribution at the output of a linear unitary optical network with indistinguishable single photons at the input. Four experimental groups have already tested their small-scale prototypes with up to four photons. A boson sampler with a few dozens of single photons is believed to be hard to simulate on a classical computer. For scalability of a realistic boson sampler with current technology it is necessary to know the effect of the photon mode mismatch on its operation. Here a nondeterministic model of the boson sampler is analyzed, which employs partially indistinguishable single photons emitted by identical sources. A sufficient condition on the average mutual fidelity $\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ of the single photons is found, which guarantees that the realistic boson sampler outperforms the classical computer. Moreover, the boson-sampler computer with partially indistinguishable single photons is scalable and has more power than classical computers when the single-photon mode mismatch $1\ensuremath{-}\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ scales as $O({N}^{\ensuremath{-}3/2})$ with the total number of photons NNN.
Boson sampling has been presented as a simplified model for linear optical quantum computing. In the boson-sampling model, Fock states are passed through a linear optics network and sampled via number-resolved photodetection. It has been shown that this sampling problem likely cannot be efficiently classically simulated. This raises the question as to whether there are other quantum states of light for which the equivalent sampling problem is also computationally hard. We present evidence, without using a full complexity proof, that a very broad class of quantum states of light---arbitrary superpositions of two or more coherent states---when evolved via passive linear optics and sampled with number-resolved photodetection, likely implements a classically hard sampling problem.
The goal of universal quantum computing that challenges classical computation is still far from being reached. However, Aaronson and Arkhipov recently proposed a nonuniversal quantum computer [1] to solve sampling problems of identical bosons in linear-optical networks which are intractable for classical computers. Once outperforming the classically computable limit of such a boson-sampling device, the very hardness of boson sampling excludes any straightforward efficient verification of the results. A computationally accessible while physically non-trivial instance of the problem was proposed to prove many-particle interference and thereby benchmark the functionality of a candidate device [2]. However, the Fourier matrix proposed in [2] is a highly artificial singular case that remains challenging to implement experimentally.
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 in STOC ’11 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 P#P = BPPNP and the polynomial hierarchy collapses to the third level. The fastest known exact classical algorithm for the standard Boson Sampling problem requires 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 time and 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.
Computers based quantum logic are believed to solve problems faster and more efficiently than computers based on classical boolean logic. However, a large-scale universal quantum computer with error correction may not be realized in near future. But we can ask the question: can we devise a specific problem that a quantum device can solve faster than current state of the art super computers? One such problem is the so called "Boson Sampling" problem introduced by Aaronson and Arkhipov. The problem is to generate random numbers according to same distribution as the output number configurations of photons in linear optics. It was shown that this is a very hard task for classical computers, but can be realized using quantum devices. However, realizing this in photonic systems is proving to be harder than ever because of various challenges in preparation and measurements. We propose and analyze an alternate platform to implement this problem, ultra-cold atoms trapped in one-dimensional optical lattices.
BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here, we investigate the complexity of BosonSampling under photon losses, more specifically, the case where an unknown subset of the photons is randomly lost at the sources. We show that if kkk out of nnn photons are lost, then we cannot sample classically from a distribution that is $1/{n}^{\mathrm{\ensuremath{\Theta}}(k)}$ close (in total variation distance) to the ideal distribution, unless a BPPNP{\text{BPP}}^{\text{NP}}BPPNP machine can estimate the permanents of Gaussian matrices in nO(k){n}^{O(k)}nO(k) time. In particular, if kkk is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case.