pith. sign in

arxiv: 1401.2199 · v3 · pith:44KU24TLnew · submitted 2014-01-09 · 🪐 quant-ph

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

classification 🪐 quant-ph
keywords boson-samplingchurch-turingclaimcomputationaldisproveefficientlyextendedphysically
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.