Recognition: unknown
Limits on Efficient Computation in the Physical World
classification
🪐 quant-ph
cs.CC
keywords
intuitionsphysicalworldbasicbehavechallengeclassicalcomplexity
read the original abstract
More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while some intuitions from classical computer science must be jettisoned in the light of modern physics, many others emerge nearly unscathed; and I use powerful tools from computational complexity theory to help determine which are which.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Probing the Planck scale with quantum computation
A 500-logical-qubit quantum computer could reject laboratory-confined theories by surpassing the Planck-scale operation rate of 2^491 m^{-3} s^{-1}, with a 1600-qubit machine limited by the observable universe.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.