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

Does Boson Sampling need Fault-Tolerance?

Anthony Leverrier, Raúl García−Patrón

Published Oct 14, 2013• 1 citation
OpenAlex

Abstract

Abstract. BosonSampling is a problem where a quantum computer offers a provable speedup over classical computers. Its main feature is that it can be solved with current linear op-tics technology, without the need for a full quantum computer. In this work, we investigate whether an experimentally realistic BosonSampler can really solve BosonSampling without any fault-tolerance mechanism. More precisely, we study how the unavoidable errors linked to an imperfect calibration of the optical elements affect the final result of the computation. We show that the fidelity of each optical element must be at least 1 − O(1/n2), where n refers to the number of single photons in the scheme. Such a requirement seems to be achievable with state-of-the-art equipment. 1.

Related papers

Analysis of circuit imperfections in BosonSampling

Anthony Leverrier, Raúl García−Patrón

BosonSampling is a problem where a quantum computer offers a provable speedup over classical computers. Its main feature is that it can be solved with current linear optics technology, without the need for a full quantum computer. In this work, we investigate whether an experimentally realistic BosonSampler can really solve BosonSampling without any fault-tolerance mechanism. More precisely, we study how the unavoidable errors linked to an imperfect calibration of the optical elements affect the final result of the computation. We show that the fidelity of each optical element must be at least 1 − O(1/n^2 ), where n refers to the number of single photons in the scheme. Such a requirement seems to be achievable with state-of-the-art equipment.

arXiv:1309.4687•Quantum Information and Computation•Apr 1, 2015•42 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•88 citations

BosonSampling is far from uniform

Scott Aaronson, Alex Arkhipov

BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. \ In a recent manuscript, Gogolin et al.\ claimed that even an ideal BosonSampling device's output would be operationally indistinguishable\textquotedblright\ from a uniform random outcome, at least \textquotedblleft without detailed a priori knowledge; or at any rate, that telling the two apart might itself be a hard problem. We first answer these claims---explaining why the first is based on a definition of a priori knowledge such that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments.However, we then go further, and address some interesting research questions inspired by Gogolin et al.'s arguments. We prove that, with high probability over a Haar-random matrix $A$, the BosonSampling distribution induced by $A$ is far from the uniform distribution in total variation distance. More surprisingly, and counter to Gogolin et al., we give an efficient algorithm that distinguishes these two distributions with constant bias. Finally, we offer three bonus results about BosonSampling. First, we report an observation of Fernando Brandao: that one can efficiently sample a distribution that has large entropy and that's indistinguishable from a BosonSampling distribution by any circuit of fixed polynomial size. Second, we show that BosonSampling distributions can be efficiently distinguished from uniform even with photon losses and for general initial states. Third, we offer the simplest known proof that Fermion Sampling is solvable in classical polynomial time, and we reuse techniques from our Boson Sampling analysis to characterize random FermionSampling distributions.

arXiv:1309.7460•Quantum Information and Computation•Nov 1, 2014•175 citations

Quantum computation with identical bosons

A. A. Архипов

We investigate the computational complexity of quantum computing with identical noninteracting bosons, such as that in a linear optical system.We explore the challenges in building devices that implement this model and in certifying their correctness.In work done with Scott Aaronson, we introduce BOSONSAMPLING, a computational model of quantum linear optics [1].We argue that the statistical distribution of outcomes cannot be reproduced by any classical device in a reasonable time span.This gives hands-on evidence of quantum advantage, that there are quantum phenomena are prohibitive to simulate in the classical world.Moreover, this quantum advantage is already present in limited optical systems, suggesting a lower bar to building devices that exhibit super-classical computation.We lay out the computational complexity argument for the classical difficulty of simulating BOSONSAM-PLING.An efficient classical simulation would have unlikely complexity consequences for the polynomial hierarchy PH.We look into the difficulties in proving an analogous approximate result, including the conjectures that seem to be needed to push it through.We then discuss experimental implementations of BOSONSAMPLING.The scalability of current implementations is limited by various sources of noise that accumulate as the problem size grows.We prove a result [51 that pertains to the inexactnesses of components that comprise the linear optical network, giving bounds on the tolerances that suffice to obtain an output distribution close to the ideal one.Finally, we look at the challenge of certifying a BOSONSAMPLING device.We show the impossibility of one technique, to use a submatrix whose permanent is so large that its corresponding outcome appears very frequently.Joint work with Aaronson [21 argues that the outputs of a BOSONSAMPLING device can be verified not to come from a uniform distribution.Results on the statistical bunching of bosons obtained with Kuperberg [61 are another approach to certification.We further present a novel certification technique based on classically estimating the distribution of integer combinations of the boson counts.

•Jan 1, 2017•0 citations

Boson Sampling from a Gaussian State

Austin P. Lund, Anthony Laing, Saleh Rahimi-Keshari +3 more

We pose a randomized boson-sampling problem. Strong evidence exists that such a problem becomes intractable on a classical computer as a function of the number of bosons. We describe a quantum optical processor that can solve this problem efficiently based on a Gaussian input state, a linear optical network, and nonadaptive photon counting measurements. All the elements required to build such a processor currently exist. The demonstration of such a device would provide empirical evidence that quantum computers can, indeed, outperform classical computers and could lead to applications.

arXiv:1305.4346•Physical Review Letters•Sep 5, 2014•321 citations

Quantum sampling problems, BosonSampling and quantum supremacy

Austin P. Lund, Michael J. Bremner, Timothy C. Ralph

Abstract There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.

arXiv:1702.03061•npj Quantum Information•Apr 5, 2017•203 citations
Abstract. BosonSampling is a problem where a quantum computer offers a provable speedup over classical computers. Its main feature is that it can be solved with current linear op-tics technology, without the need for a full quantum computer. In this work, we investigate whether an experimentally realistic BosonSampler can really solve BosonSampling without any fault-tolerance mechanism. More precisely, we study how the unavoidable errors linked to an imperfect calibration of the optical elements affect the final result of the computation. We show that the fidelity of each optical element must be at least 1 − O(1/n2), where n refers to the number of single photons in the scheme. Such a requirement seems to be achievable with state-of-the-art equipment. 1.
BosonSampling is a problem where a quantum computer offers a provable speedup over classical computers. Its main feature is that it can be solved with current linear optics technology, without the need for a full quantum computer. In this work, we investigate whether an experimentally realistic BosonSampler can really solve BosonSampling without any fault-tolerance mechanism. More precisely, we study how the unavoidable errors linked to an imperfect calibration of the optical elements affect the final result of the computation. We show that the fidelity of each optical element must be at least 1 − O(1/n^2 ), where n refers to the number of single photons in the scheme. Such a requirement seems to be achievable with state-of-the-art equipment.
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.
BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. \ In a recent manuscript, Gogolin et al.\ claimed that even an ideal BosonSampling device's output would be operationally indistinguishable\textquotedblright\ from a uniform random outcome, at least \textquotedblleft without detailed a priori knowledge; or at any rate, that telling the two apart might itself be a hard problem. We first answer these claims---explaining why the first is based on a definition of a priori knowledge such that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments.However, we then go further, and address some interesting research questions inspired by Gogolin et al.'s arguments. We prove that, with high probability over a Haar-random matrix AAA, the BosonSampling distribution induced by AAA is far from the uniform distribution in total variation distance. More surprisingly, and counter to Gogolin et al., we give an efficient algorithm that distinguishes these two distributions with constant bias. Finally, we offer three bonus results about BosonSampling. First, we report an observation of Fernando Brandao: that one can efficiently sample a distribution that has large entropy and that's indistinguishable from a BosonSampling distribution by any circuit of fixed polynomial size. Second, we show that BosonSampling distributions can be efficiently distinguished from uniform even with photon losses and for general initial states. Third, we offer the simplest known proof that Fermion Sampling is solvable in classical polynomial time, and we reuse techniques from our Boson Sampling analysis to characterize random FermionSampling distributions.
We investigate the computational complexity of quantum computing with identical noninteracting bosons, such as that in a linear optical system.We explore the challenges in building devices that implement this model and in certifying their correctness.In work done with Scott Aaronson, we introduce BOSONSAMPLING, a computational model of quantum linear optics [1].We argue that the statistical distribution of outcomes cannot be reproduced by any classical device in a reasonable time span.This gives hands-on evidence of quantum advantage, that there are quantum phenomena are prohibitive to simulate in the classical world.Moreover, this quantum advantage is already present in limited optical systems, suggesting a lower bar to building devices that exhibit super-classical computation.We lay out the computational complexity argument for the classical difficulty of simulating BOSONSAM-PLING.An efficient classical simulation would have unlikely complexity consequences for the polynomial hierarchy PH.We look into the difficulties in proving an analogous approximate result, including the conjectures that seem to be needed to push it through.We then discuss experimental implementations of BOSONSAMPLING.The scalability of current implementations is limited by various sources of noise that accumulate as the problem size grows.We prove a result [51 that pertains to the inexactnesses of components that comprise the linear optical network, giving bounds on the tolerances that suffice to obtain an output distribution close to the ideal one.Finally, we look at the challenge of certifying a BOSONSAMPLING device.We show the impossibility of one technique, to use a submatrix whose permanent is so large that its corresponding outcome appears very frequently.Joint work with Aaronson [21 argues that the outputs of a BOSONSAMPLING device can be verified not to come from a uniform distribution.Results on the statistical bunching of bosons obtained with Kuperberg [61 are another approach to certification.We further present a novel certification technique based on classically estimating the distribution of integer combinations of the boson counts.
We pose a randomized boson-sampling problem. Strong evidence exists that such a problem becomes intractable on a classical computer as a function of the number of bosons. We describe a quantum optical processor that can solve this problem efficiently based on a Gaussian input state, a linear optical network, and nonadaptive photon counting measurements. All the elements required to build such a processor currently exist. The demonstration of such a device would provide empirical evidence that quantum computers can, indeed, outperform classical computers and could lead to applications.
Abstract There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.