Scott Aaronson: Quantum Complexity and Quantum Optics
December-30-13
2:37 AM
See also [link], problem sets at [link]
[link]
The Physical Church-Thesis: Anything that can be physically computed can be computed by a Turing machine.
Beyond Turing:
"Zeno Computer" - fails as at 10^43 Hz the energy needed to cool the computer will turn it into a black hole.
"Special Relativity Computer" - will need an exponential amount of energy to accelerate.
A definition of the class "P".
ECT: "Extended Church-Turing Thesis": P is always the same, and the physical P is the CS P.
A definition of "NP".
[link]