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].
© 2013 Optical Society of America
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
Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari, Agata M. Brańczyk, Justin Dove, Scott Aaronson, Timothy C. Ralph, and Andrew G. White
IB_6_1 International Quantum Electronics Conference (IQEC) 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