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, experimentally accessible example of such a task [1].
© 2013 IEEE
PDF ArticleMore Like This
M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White
W5B.3 Conference on Coherence and Quantum Optics (CQO) 2013
M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White
W5B.3 Quantum Information and Measurement (QIM) 2013
Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari, Justin Dove, Scott Aaronson, Timothy C. Ralph, and Andrew G. White
QW1C.3 CLEO: QELS_Fundamental Science (CLEO:FS) 2013