Quantum Computing and the Limits of the Efficiently Computable
Mr. Scott Aaronson, Associate Professor of Electrical Engineering and Computer Science at MIT, discusses what can and can't be feasibly computed according to physical law. He argues that this is a fundamental question, not only for mathematics and computer science, but also for physics; and that the infeasibility of certain computational problems (such as NP-complete problems) could plausibly be taken as a physical principle, analogous to the Second Law or the impossibility of superluminal signalling.
He first explains the basics of computational complexity, including the infamous P versus NP problem and the Extended Church-Turing Thesis. Then he discusses quantum computers: what they are, whether they can be scalably built, and what's known today about their capabilities and limitations. Lastly, he touches on speculative models of computation that would go even beyond quantum computers, using (for example) closed timelike curves or nonlinearities in the Schrodinger equation.
Mr. Aaronson emphasises that, even if "intractable" computations occur in a particular description of a physical system, what really matters is whether those computations have observable consequences.
| Quantum Computing and the Limits of the Efficiently Computable |
| Related Links |
| Quantum Technologies We will describe our progress in the Centre for Quantum Photonics to delivering this promise using an integrated quantum photonics platform - generating, manipulating and interacting single particles of light (photons) in waveguide circuits on silicon chips. |
| DNA Hard Drives, Quantum Computing, Moore's Law Quantum computer science is a field that right now is in its very early stages, since scientists have yet been able to develop any quantum hardware. |
| The Machine That Changed the World This is a 1992 documentary series on the history of electronic digital computers, from the dawn of the computer in the 1800s to the early 1990s. |