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

The Rochester Conferences on Coherence and Quantum Optics and the Quantum Information and Measurement meeting

Experimental BosonSampling

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

Published Jan 1, 2013• 94 citations
Publisher

Abstract

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

DOI
10.1364/cqo.2013.w5b.3

Related papers

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 in a photonic circuit

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

IEEE/LEOS Summer Topical Meetings•Jul 1, 2013•0 citations

Quantum Computers: the Church-Turing Hypothesis Versus the Turing Principle

Christopher G. Timpson

Springer eBooks•Jan 1, 2004•12 citations

Quantum Speed-up of Computations

Itamar Pitowsky

Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system...Nophysically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. An even more extreme formulation of (more or less) the same thesis is due to Aharonov (1998): A probabilistic Turing machine can simulate any reasonable physical device in polynomial cost. She calls this The Modern Church Thesis. Aharonov refers here to probabilistic Turing machines that use random numbers in addition to the usual deterministic table of steps. It seems that such machines are capable to perform certain tasks faster than fully deterministic machines. The most famous randomized algorithm of that kind concerns the decision whether a given natural number is prime. A probabilistic algorithm that decides primality in a number of

Philosophy of Science•Sep 1, 2002•36 citations

The History and the Contemporary Status of the No Cloning Theorem and the Extended Church-Turing Thesis

Spalding, Dalton

This project aims to trace the history and the evolution of two fundamental concepts that have cut across physics, mathematics and computer science over the past 100 years. First: Evolution of the so-called No-Cloning Theorem. In classical computing (Pre-Quantum), information can be copied without limitations. The discovery of the No-Cloning Theorem by Wootters and Zurek (1982) and Dieks (1982) revised this concept dramatically; they independently proved that unknown quantum states cannot be perfectly copied. I look at mathematical proofs of this theorem, construct physics-based nonmathematical plausibility arguments for it, and explore the role it plays in Quantum Key Distribution (QKD) protocols, such as BB84 (Bennett and Brassard, 1984) and the Ekert Protocol (Artur Ekert 1991). Second: Evolution of the concept of computability in quantum computing. I began by trying to understand the classical Church-Turing thesis (1936) which states that any computation performed by a physically realizable system can be simulated by a Turing machine. Then I try to explore the Extended Church-Turing Thesis (ECTT, 1980s) which conjectures that all efficiently computable functions in the physical world can be efficiently simulated by a probabilistic Turing machine. The recent discovery of quantum algorithms (for example, Shor’s algorithm, 1994) suggests that quantum computers could violate this thesis by solving problems exponentially faster than classical computers. The very modern debate (2020’s) surrounding this topic asks whether quantum computing truly invalidates ECTT or whether deeper physical constraints (such as decoherence) might limit quantum computers in a fashion that would be consistent with ECTT. This debate is far from settled. I have grappled with these hard questions and will summarize what I understand to be the status of this debate.

•Apr 12, 2025•0 citations

Quantum Computers Approach Milestone for Boson Sampling

Anonymous

Physics•Dec 18, 2019•0 citations
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 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 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].
Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system...Nophysically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. An even more extreme formulation of (more or less) the same thesis is due to Aharonov (1998): A probabilistic Turing machine can simulate any reasonable physical device in polynomial cost. She calls this The Modern Church Thesis. Aharonov refers here to probabilistic Turing machines that use random numbers in addition to the usual deterministic table of steps. It seems that such machines are capable to perform certain tasks faster than fully deterministic machines. The most famous randomized algorithm of that kind concerns the decision whether a given natural number is prime. A probabilistic algorithm that decides primality in a number of
This project aims to trace the history and the evolution of two fundamental concepts that have cut across physics, mathematics and computer science over the past 100 years. First: Evolution of the so-called No-Cloning Theorem. In classical computing (Pre-Quantum), information can be copied without limitations. The discovery of the No-Cloning Theorem by Wootters and Zurek (1982) and Dieks (1982) revised this concept dramatically; they independently proved that unknown quantum states cannot be perfectly copied. I look at mathematical proofs of this theorem, construct physics-based nonmathematical plausibility arguments for it, and explore the role it plays in Quantum Key Distribution (QKD) protocols, such as BB84 (Bennett and Brassard, 1984) and the Ekert Protocol (Artur Ekert 1991). Second: Evolution of the concept of computability in quantum computing. I began by trying to understand the classical Church-Turing thesis (1936) which states that any computation performed by a physically realizable system can be simulated by a Turing machine. Then I try to explore the Extended Church-Turing Thesis (ECTT, 1980s) which conjectures that all efficiently computable functions in the physical world can be efficiently simulated by a probabilistic Turing machine. The recent discovery of quantum algorithms (for example, Shor’s algorithm, 1994) suggests that quantum computers could violate this thesis by solving problems exponentially faster than classical computers. The very modern debate (2020’s) surrounding this topic asks whether quantum computing truly invalidates ECTT or whether deeper physical constraints (such as decoherence) might limit quantum computers in a fashion that would be consistent with ECTT. This debate is far from settled. I have grappled with these hard questions and will summarize what I understand to be the status of this debate.