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

Frontiers in Optics

Boson Sampling with Continuous Variable Measurements

Timothy C. Ralph

Published Jan 1, 2016• 0 citations
Publisher

Abstract

We show that it is classically hard to sample the output distribution of certain continuous variable measurements from a BosonSampling device. Our argument is presented for exact BosonSampling. We discuss extending this result to approximate sampling.
DOI
10.1364/fio.2016.ff1c.2

Related papers

Exact boson sampling using Gaussian continuous-variable measurements

Austin P. Lund, Saleh Rahimi-Keshari, Timothy C. Ralph

Boson sampling is a quantum mechanical task involving Fock basis state preparation and detection and evolution using only linear interactions. A classical algorithm for producing samples from this quantum task cannot be efficient unless the polynomial hierarchy of complexity classes collapses, a situation believed to be highly implausible. We present a method for constructing a device which uses Fock state preparations, linear interactions, and Gaussian continuous-variable measurements for which one can show that exact sampling would be hard for a classical algorithm in the same way as boson sampling. The detection events used from this arrangement do not allow a similar conclusion to be drawn for the classical hardness of approximate sampling. We discuss the details of this result outlining some specific properties required by approximate sampling hardness.

arXiv:1705.06041•Physical Review A•Aug 2, 2017•27 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

Experimental BosonSampling

Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari +4 more

The extended Church-Turing theeie posits that any computable function can be oalculated efficitntly by a probabilistic Turing machine. If this thesis held true, thee global effort; to build quantum computers might ultimhiely be unnecessary. The thesis would however be strongly contradicted by a physical device that efficiently performs a task believed to be intractable for classical computers. BOSONSAMPLING—the sampling from a distribution of n photons undergoing some linear-optical process—is a recently developed, and experimentally accessible example of such a task [1].

The Rochester Conferences on Coherence and Quantum Optics and the Quantum Information and Measurement meeting•Jan 1, 2013•94 citations

Classical Boson Sampling [R package BosonSampling version 0.1.3]

Peter Clifford, Raphaël Clifford

•May 14, 2021•0 citations

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

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
Boson sampling is a quantum mechanical task involving Fock basis state preparation and detection and evolution using only linear interactions. A classical algorithm for producing samples from this quantum task cannot be efficient unless the polynomial hierarchy of complexity classes collapses, a situation believed to be highly implausible. We present a method for constructing a device which uses Fock state preparations, linear interactions, and Gaussian continuous-variable measurements for which one can show that exact sampling would be hard for a classical algorithm in the same way as boson sampling. The detection events used from this arrangement do not allow a similar conclusion to be drawn for the classical hardness of approximate sampling. We discuss the details of this result outlining some specific properties required by approximate sampling hardness.
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.
The extended Church-Turing theeie posits that any computable function can be oalculated efficitntly by a probabilistic Turing machine. If this thesis held true, thee global effort; to build quantum computers might ultimhiely be unnecessary. The thesis would however be strongly contradicted by a physical device that efficiently performs a task believed to be intractable for classical computers. BOSONSAMPLING—the sampling from a distribution of n photons undergoing some linear-optical process—is a recently developed, and experimentally accessible example of such a task [1].
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.
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.