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

IEEE/LEOS Summer Topical Meetings

Experimental bosonsampling in a photonic circuit

Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari, Justin Dove, Scott Aaronson, Timothy C. Ralph, Andrew G. White

Published Jul 1, 2013• 0 citations
Publisher

Abstract

The extended Church-Turing thesis posits that any computable function can be calculated efficiently by a probabilistic Turing machine. If this thesis held true, the global effort to build quantum computers might ultimately 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].

DOI
10.1109/phosst.2013.6614564

Related papers

Experimental BosonSampling

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

The extended Church-Turing thesis posits that any computable function can be calculated efficiently by a probabilistic Turing machine. If this thesis held true, the global effort to build quantum computers might ultimately 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•31 citations

BosonSampling with realistic single-photon sources

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

The extended Church-Turing thesis posits that any computable function can be calculated efficiently by a probabilistic Turing machine. If this thesis held true, the global effort to build quantum computers might ultimately 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, experimentally accessible example of such a task [1].

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•May 1, 2013•0 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•26 citations

Will boson-sampling ever disprove the Extended Church-Turing thesis?

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

Boson-sampling is a highly simplified, but non-universal, approach to implementing optical quantum computation. It was shown by Aaronson and Arkhipov that this protocol cannot be efficiently classically simulated unless the polynomial hierarchy collapses, which would be a shocking result in computational complexity theory. Based on this, numerous authors have made the claim that experimental boson-sampling would provide evidence against, or disprove, the Extended Church-Turing thesis -- that any physically realisable system can be efficiently simulated on a Turing machine. We argue against this claim on the basis that, under a general, physically realistic independent error model, boson-sampling does not implement a provably hard computational problem in the asymptotic limit of large systems.

arXiv:1401.2199•Jan 9, 2014•6 citations

Bosonsampling is far from uniform

AaronsonScott, ArkhipovAlex

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 manusc...

Quantum Information and Computation•Nov 1, 2014•7 citations

An Introduction to Boson-Sampling

Bryan T. Gard, Keith R. Motes, Jonathan P. Olson +2 more

Boson-sampling is a simplified model for quantum computing that may hold the key to implementing the first ever post-classical quantum computer. Boson-sampling is a non-universal quantum computer that is significantly more straightforward to build than any universal quantum computer proposed so far. We begin this chapter by motivating boson-sampling and discussing the history of linear optics quantum computing. We then summarize the boson-sampling formalism, discuss what a sampling problem is, explain why boson-sampling is easier than linear optics quantum computing, and discuss the Extended Church-Turing thesis. Next, sampling with other classes of quantum optical states is analyzed. Finally, we discuss the feasibility of building a boson-sampling device using existing technology.

arXiv:1406.6767•WORLD SCIENTIFIC eBooks•Jun 28, 2015•26 citations
The extended Church-Turing thesis posits that any computable function can be calculated efficiently by a probabilistic Turing machine. If this thesis held true, the global effort to build quantum computers might ultimately 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 extended Church-Turing thesis posits that any computable function can be calculated efficiently by a probabilistic Turing machine. If this thesis held true, the global effort to build quantum computers might ultimately 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 extended Church-Turing thesis posits that any computable function can be calculated efficiently by a probabilistic Turing machine. If this thesis held true, the global effort to build quantum computers might ultimately 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, experimentally accessible example of such a task [1].
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 highly simplified, but non-universal, approach to implementing optical quantum computation. It was shown by Aaronson and Arkhipov that this protocol cannot be efficiently classically simulated unless the polynomial hierarchy collapses, which would be a shocking result in computational complexity theory. Based on this, numerous authors have made the claim that experimental boson-sampling would provide evidence against, or disprove, the Extended Church-Turing thesis -- that any physically realisable system can be efficiently simulated on a Turing machine. We argue against this claim on the basis that, under a general, physically realistic independent error model, boson-sampling does not implement a provably hard computational problem in the asymptotic limit of large systems.
Boson-sampling is a simplified model for quantum computing that may hold the key to implementing the first ever post-classical quantum computer. Boson-sampling is a non-universal quantum computer that is significantly more straightforward to build than any universal quantum computer proposed so far. We begin this chapter by motivating boson-sampling and discussing the history of linear optics quantum computing. We then summarize the boson-sampling formalism, discuss what a sampling problem is, explain why boson-sampling is easier than linear optics quantum computing, and discuss the Extended Church-Turing thesis. Next, sampling with other classes of quantum optical states is analyzed. Finally, we discuss the feasibility of building a boson-sampling device using existing technology.