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

arXiv:1403.4459

Conditions for an experimental Boson-sampling computer to disprove the Extended Church-Turing thesis

V. S. Shchesnovich

Published Mar 18, 2014• 13 citations
arXivHTMLPDF

Abstract

We give a set of sufficient conditions on the experimental Boson-Sampling computer to satisfy Theorem 1.3 of Aaronson & Arkhipov (Theory of Computing \textbf{9}, 143 (2013)) stating a computational problem whose simulation on a classical computer would collapse the polynomial hierarchy of the computational complexity to the third level. This implies that such an experimental device is in conflict with the Extended Church-Turing thesis. In practical terms, we give a set of sufficient conditions for the scalability of the experimental Boson-Sampling computer beyond the power of the classical computers. The derived conditions can be also used for devising efficient verification tests of the Boson-Sampling computer.

DOI
10.48550/arxiv.1403.4459

Related papers

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•18 citations

Sufficient condition for the mode mismatch of single photons for scalability of the boson-sampling computer

V. S. Shchesnovich

The boson sampler proposed by Aaronson and Arkhipov is a nonuniversal quantum computer, which can serve as evidence against the extended Church-Turing thesis. It samples the probability distribution at the output of a linear unitary optical network with indistinguishable single photons at the input. Four experimental groups have already tested their small-scale prototypes with up to four photons. A boson sampler with a few dozens of single photons is believed to be hard to simulate on a classical computer. For scalability of a realistic boson sampler with current technology it is necessary to know the effect of the photon mode mismatch on its operation. Here a nondeterministic model of the boson sampler is analyzed, which employs partially indistinguishable single photons emitted by identical sources. A sufficient condition on the average mutual fidelity $\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ of the single photons is found, which guarantees that the realistic boson sampler outperforms the classical computer. Moreover, the boson-sampler computer with partially indistinguishable single photons is scalable and has more power than classical computers when the single-photon mode mismatch $1\ensuremath{-}\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ scales as $O({N}^{\ensuremath{-}3/2})$ with the total number of photons $N$.

arXiv:1311.6796•Physical Review A•Feb 24, 2014•75 citations

The Classical Complexity of Boson Sampling

Peter Clifford, Raphaël Clifford

We study the classical complexity of the exact Boson Sampling problem where the objective is to produce provably correct random samples from a particular quantum mechanical distribution. The computational framework was proposed in STOC ’11 by Aaronson and Arkhipov in 2011 as an attainable demonstration of ‘quantum supremacy’, that is a practical quantum computing experiment able to produce output at a speed beyond the reach of classical (that is non-quantum) computer hardware. Since its introduction Boson Sampling has been the subject of intense international research in the world of quantum computing. On the face of it, the problem is challenging for classical computation. Aaronson and Arkhipov show that exact Boson Sampling is not efficiently solvable by a classical computer unless P#P = BPPNP and the polynomial hierarchy collapses to the third level. The fastest known exact classical algorithm for the standard Boson Sampling problem requires time to produce samples for a system with input size n and m output modes, making it infeasible for anything but the smallest values of n and m. We give an algorithm that is much faster, running in time and additional space. The algorithm is simple to implement and has low constant factor overheads. As a consequence our classical algorithm is able to solve the exact Boson Sampling problem for system sizes far beyond current photonic quantum computing experimentation, thereby significantly reducing the likelihood of achieving near-term quantum supremacy in the context of Boson Sampling.

arXiv:1706.01260•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•104 citations

Stringent and Efficient Assessment of Boson-Sampling Devices

Malte C. Tichy, Klaus Mayer, Andreas Buchleitner +1 more

Boson sampling holds the potential to experimentally falsify the extended Church-Turing thesis. The computational hardness of boson sampling, however, complicates the certification that an experimental device yields correct results in the regime in which it outmatches classical computers. To certify a boson sampler, one needs to verify quantum predictions and rule out models that yield these predictions without true many-boson interference. We show that a semiclassical model for many-boson propagation reproduces coarse-grained observables that are proposed as witnesses of boson sampling. A test based on Fourier matrices is demonstrated to falsify physically plausible alternatives to coherent many-boson propagation.

arXiv:1312.3080•Physical Review Letters•Jul 9, 2014•128 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

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•91 citations
We give a set of sufficient conditions on the experimental Boson-Sampling computer to satisfy Theorem 1.3 of Aaronson & Arkhipov (Theory of Computing \textbf{9}, 143 (2013)) stating a computational problem whose simulation on a classical computer would collapse the polynomial hierarchy of the computational complexity to the third level. This implies that such an experimental device is in conflict with the Extended Church-Turing thesis. In practical terms, we give a set of sufficient conditions for the scalability of the experimental Boson-Sampling computer beyond the power of the classical computers. The derived conditions can be also used for devising efficient verification tests of the Boson-Sampling computer.
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.
The boson sampler proposed by Aaronson and Arkhipov is a nonuniversal quantum computer, which can serve as evidence against the extended Church-Turing thesis. It samples the probability distribution at the output of a linear unitary optical network with indistinguishable single photons at the input. Four experimental groups have already tested their small-scale prototypes with up to four photons. A boson sampler with a few dozens of single photons is believed to be hard to simulate on a classical computer. For scalability of a realistic boson sampler with current technology it is necessary to know the effect of the photon mode mismatch on its operation. Here a nondeterministic model of the boson sampler is analyzed, which employs partially indistinguishable single photons emitted by identical sources. A sufficient condition on the average mutual fidelity $\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ of the single photons is found, which guarantees that the realistic boson sampler outperforms the classical computer. Moreover, the boson-sampler computer with partially indistinguishable single photons is scalable and has more power than classical computers when the single-photon mode mismatch $1\ensuremath{-}\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ scales as $O({N}^{\ensuremath{-}3/2})$ with the total number of photons NNN.
We study the classical complexity of the exact Boson Sampling problem where the objective is to produce provably correct random samples from a particular quantum mechanical distribution. The computational framework was proposed in STOC ’11 by Aaronson and Arkhipov in 2011 as an attainable demonstration of ‘quantum supremacy’, that is a practical quantum computing experiment able to produce output at a speed beyond the reach of classical (that is non-quantum) computer hardware. Since its introduction Boson Sampling has been the subject of intense international research in the world of quantum computing. On the face of it, the problem is challenging for classical computation. Aaronson and Arkhipov show that exact Boson Sampling is not efficiently solvable by a classical computer unless P#P = BPPNP and the polynomial hierarchy collapses to the third level. The fastest known exact classical algorithm for the standard Boson Sampling problem requires time to produce samples for a system with input size n and m output modes, making it infeasible for anything but the smallest values of n and m. We give an algorithm that is much faster, running in time and additional space. The algorithm is simple to implement and has low constant factor overheads. As a consequence our classical algorithm is able to solve the exact Boson Sampling problem for system sizes far beyond current photonic quantum computing experimentation, thereby significantly reducing the likelihood of achieving near-term quantum supremacy in the context of Boson Sampling.
Boson sampling holds the potential to experimentally falsify the extended Church-Turing thesis. The computational hardness of boson sampling, however, complicates the certification that an experimental device yields correct results in the regime in which it outmatches classical computers. To certify a boson sampler, one needs to verify quantum predictions and rule out models that yield these predictions without true many-boson interference. We show that a semiclassical model for many-boson propagation reproduces coarse-grained observables that are proposed as witnesses of boson sampling. A test based on Fourier matrices is demonstrated to falsify physically plausible alternatives to coherent many-boson propagation.
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].
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.