Fetching the paper…

Reading the bibliography…

2014

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

Rohde, Peter P., Motes, Keith R., Knott, Paul A. et al.

Original
PDF
Post on X

Understand

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.

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

Built on

E. Knill, R. Laflamme, and G. Milburn, Nature 409
2001
Earlier work this paper cites.
S. Aaronson and A. Arkhipov, Proc. ACM STOC (New York) p. 333 (2011)
2011
Earlier work this paper cites.
M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, Science 339
2013
Earlier work this paper cites.
A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, Nature Phot. 7
2013
Earlier work this paper cites.

Similar

M. Tillmann, B. Daki, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, Nature Phot. 7
2013
Cited alongside, same era.
J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, et al., Science 339
2013
Cited alongside, same era.
S. Aaronson and A. Arkhipov (2013), eprint arXiv:1309.7460v2
Original
2013
Cited alongside, same era.
V. S. Shchesnovich (2013), eprint arXiv:1311.6796
Original
2013
Cited alongside, same era.

Then

C. Shen, Z. Zhang, and L.-M. Duan (2013), eprint arXiv:1310.4860
Original
2013
Later among the works it cites.
M. C. Tichy, K. Mayer, A. Buchleitner, and K. Mølmer (2013), eprint arXiv:1312.3080
Original
2013
Later among the works it cites.
A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph (2013), eprint arXiv:1305.4346
Original
2013
Later among the works it cites.
V. Shchesnovich, arXiv:1403.4459 (2014)
Original
2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…