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

European Quantum Electronics Conference (EQEC)

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

Christoph Dittel, Robert Keil, Malte C. Tichy, Armando Pérez-Leija, Thomas Kauten, Steffen Weimann, Maxime Lebugle, Alexander Szameit, Gregor Weihs

Published Jun 21, 2015• 0 citations
OpenAlex

Abstract

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.

Related papers

Boson-Sampling in the light of sample complexity

Christian Gogolin, Martin Kliesch, Leandro Aolita +1 more

Boson-Sampling is a classically computationally hard problem that can - in principle - be efficiently solved with quantum linear optical networks. Very recently, a rush of experimental activity has ignited with the aim of developing such devices as feasible instances of quantum simulators. Even approximate Boson-Sampling is believed to be hard with high probability if the unitary describing the optical network is drawn from the Haar measure. In this work we show that in this setup, with probability exponentially close to one in the number of bosons, no symmetric algorithm can distinguish the Boson-Sampling distribution from the uniform one from fewer than exponentially many samples. This means that the two distributions are operationally indistinguishable without detailed a priori knowledge. We carefully discuss the prospects of efficiently using knowledge about the implemented unitary for devising non-symmetric algorithms that could potentially improve upon this. We conclude that due to the very fact that Boson-Sampling is believed to be hard, efficient classical certification of Boson-Sampling devices seems to be out of reach.

arXiv:1306.3995•Jun 17, 2013•83 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

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

On the Power of Quantum Fourier Sampling

Bill Fefferman, Christopher Umans

A line of work initiated by Terhal and DiVincenzo [Terhal/DiVincenzo, arXiv, 2002] and Bremner, Jozsa, and Shepherd [Bremner/Jozsa/Sheperd, Proc. Royal Soc. A, 2010], shows that restricted classes of quantum computation can efficiently sample from probability distributions that cannot be exactly sampled efficiently on a classical computer, unless the PH collapses. Aaronson and Arkhipov [Aaronson/Arkhipov, J. Theory of Comp., 2013] take this further by considering a distribution that can be sampled efficiently by linear optical quantum computation, that under two feasible conjectures, cannot even be approximately sampled within bounded total variation distance, unless the PH collapses. In this work we use Quantum Fourier Sampling to construct a class of distributions that can be sampled exactly by a quantum computer. We then argue that these distributions cannot be approximately sampled classically, unless the PH collapses, under variants of the Aaronson-Arkhipov conjectures. In particular, we show a general class of quantumly sampleable distributions each of which is based on an "Efficiently Specifiable" polynomial, for which a classical approximate sampler implies an average-case approximation. This class of polynomials contains the Permanent but also includes, for example, the Hamiltonian Cycle polynomial, as well as many other familiar #P-hard polynomials. Since our distribution likely requires the full power of universal quantum computation, while the Aaronson-Arkhipov distribution uses only linear optical quantum computation with noninteracting bosons, why is our result interesting? We can think of at least three reasons: 1. Since the conjectures required in [Aaronson/Arkhipov, J. Theory of Comp., 2013] have not yet been proven, it seems worthwhile to weaken them as much as possible. We do this in two ways, by weakening both conjectures to apply to any "Efficiently Specifiable" polynomial, and by weakening the so-called Anti-Concentration conjecture so that it need only hold for one distribution in a broad class of distributions. 2. Our construction can be understood without any knowledge of linear optics. While this may be a disadvantage for experimentalists, in our opinion it results in a very clean and simple exposition that may be more immediately accessible to computer scientists. 3. It is extremely common for quantum computations to employ “Quantum Fourier Sampling” in the following way: first apply a classically efficient function to a uniform superposition of inputs, then apply a Quantum Fourier Transform followed by a measurement. Our distributions are obtained in exactly this way, where the classically efficient function is related to a (presumed) hard polynomial. Establishing rigorously a robust sense in which the central primitive of Quantum Fourier Sampling is classically hard seems a worthwhile goal in itself.

Leibniz international proceedings in informatics•Jan 1, 2016•7 citations

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

Peter P. Rohde, Timothy C. Ralph

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.

arXiv:1111.2426•Physical Review A•Feb 23, 2012•81 citations

The Power of Quantum Fourier Sampling

Bill Fefferman, Chris Umans

A line of work initiated by Terhal and DiVincenzo and Bremner, Jozsa, and Shepherd, shows that quantum computers can efficiently sample from probability distributions that cannot be exactly sampled efficiently on a classical computer, unless the PH collapses. Aaronson and Arkhipov take this further by considering a distribution that can be sampled efficiently by linear optical quantum computation, that under two feasible conjectures, cannot even be approximately sampled classically within bounded total variation distance, unless the PH collapses. In this work we use Quantum Fourier Sampling to construct a class of distributions that can be sampled by a quantum computer. We then argue that these distributions cannot be approximately sampled classically, unless the PH collapses, under variants of the Aaronson and Arkhipov conjectures. In particular, we show a general class of quantumly sampleable distributions each of which is based on an "Efficiently Specifiable" polynomial, for which a classical approximate sampler implies an average-case approximation. This class of polynomials contains the Permanent but also includes, for example, the Hamiltonian Cycle polynomial, and many other familiar #P-hard polynomials. Although our construction, unlike that proposed by Aaronson and Arkhipov, likely requires a universal quantum computer, we are able to use this additional power to weaken the conjectures needed to prove approximate sampling hardness results.

arXiv:1507.05592•Jul 20, 2015•45 citations
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.
Boson-Sampling is a classically computationally hard problem that can - in principle - be efficiently solved with quantum linear optical networks. Very recently, a rush of experimental activity has ignited with the aim of developing such devices as feasible instances of quantum simulators. Even approximate Boson-Sampling is believed to be hard with high probability if the unitary describing the optical network is drawn from the Haar measure. In this work we show that in this setup, with probability exponentially close to one in the number of bosons, no symmetric algorithm can distinguish the Boson-Sampling distribution from the uniform one from fewer than exponentially many samples. This means that the two distributions are operationally indistinguishable without detailed a priori knowledge. We carefully discuss the prospects of efficiently using knowledge about the implemented unitary for devising non-symmetric algorithms that could potentially improve upon this. We conclude that due to the very fact that Boson-Sampling is believed to be hard, efficient classical certification of Boson-Sampling devices seems to be out of reach.
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.
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.
A line of work initiated by Terhal and DiVincenzo [Terhal/DiVincenzo, arXiv, 2002] and Bremner, Jozsa, and Shepherd [Bremner/Jozsa/Sheperd, Proc. Royal Soc. A, 2010], shows that restricted classes of quantum computation can efficiently sample from probability distributions that cannot be exactly sampled efficiently on a classical computer, unless the PH collapses. Aaronson and Arkhipov [Aaronson/Arkhipov, J. Theory of Comp., 2013] take this further by considering a distribution that can be sampled efficiently by linear optical quantum computation, that under two feasible conjectures, cannot even be approximately sampled within bounded total variation distance, unless the PH collapses. In this work we use Quantum Fourier Sampling to construct a class of distributions that can be sampled exactly by a quantum computer. We then argue that these distributions cannot be approximately sampled classically, unless the PH collapses, under variants of the Aaronson-Arkhipov conjectures. In particular, we show a general class of quantumly sampleable distributions each of which is based on an "Efficiently Specifiable" polynomial, for which a classical approximate sampler implies an average-case approximation. This class of polynomials contains the Permanent but also includes, for example, the Hamiltonian Cycle polynomial, as well as many other familiar #P-hard polynomials. Since our distribution likely requires the full power of universal quantum computation, while the Aaronson-Arkhipov distribution uses only linear optical quantum computation with noninteracting bosons, why is our result interesting? We can think of at least three reasons: 1. Since the conjectures required in [Aaronson/Arkhipov, J. Theory of Comp., 2013] have not yet been proven, it seems worthwhile to weaken them as much as possible. We do this in two ways, by weakening both conjectures to apply to any "Efficiently Specifiable" polynomial, and by weakening the so-called Anti-Concentration conjecture so that it need only hold for one distribution in a broad class of distributions. 2. Our construction can be understood without any knowledge of linear optics. While this may be a disadvantage for experimentalists, in our opinion it results in a very clean and simple exposition that may be more immediately accessible to computer scientists. 3. It is extremely common for quantum computations to employ “Quantum Fourier Sampling” in the following way: first apply a classically efficient function to a uniform superposition of inputs, then apply a Quantum Fourier Transform followed by a measurement. Our distributions are obtained in exactly this way, where the classically efficient function is related to a (presumed) hard polynomial. Establishing rigorously a robust sense in which the central primitive of Quantum Fourier Sampling is classically hard seems a worthwhile goal in itself.
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.
A line of work initiated by Terhal and DiVincenzo and Bremner, Jozsa, and Shepherd, shows that quantum computers can efficiently sample from probability distributions that cannot be exactly sampled efficiently on a classical computer, unless the PH collapses. Aaronson and Arkhipov take this further by considering a distribution that can be sampled efficiently by linear optical quantum computation, that under two feasible conjectures, cannot even be approximately sampled classically within bounded total variation distance, unless the PH collapses. In this work we use Quantum Fourier Sampling to construct a class of distributions that can be sampled by a quantum computer. We then argue that these distributions cannot be approximately sampled classically, unless the PH collapses, under variants of the Aaronson and Arkhipov conjectures. In particular, we show a general class of quantumly sampleable distributions each of which is based on an "Efficiently Specifiable" polynomial, for which a classical approximate sampler implies an average-case approximation. This class of polynomials contains the Permanent but also includes, for example, the Hamiltonian Cycle polynomial, and many other familiar #P-hard polynomials. Although our construction, unlike that proposed by Aaronson and Arkhipov, likely requires a universal quantum computer, we are able to use this additional power to weaken the conjectures needed to prove approximate sampling hardness results.