Limits on Efficient Computation in the Physical World
E1002077
"Limits on Efficient Computation in the Physical World" is a research work by Scott Aaronson that explores how the laws of physics constrain what can be computed efficiently, particularly in the context of quantum computing and complexity theory.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Limits on Efficient Computation in the Physical World canonical | 1 |
Statements (45)
| Predicate | Object |
|---|---|
| instanceOf |
research paper
ⓘ
scientific article ⓘ |
| aim |
to characterize which physical theories would allow solving hard problems efficiently
ⓘ
to connect open problems in physics with open problems in complexity theory ⓘ |
| approach |
comparison of classical and quantum computational models
ⓘ
complexity-theoretic analysis of physical models ⓘ thought experiments based on alternative physical theories ⓘ |
| author | Scott Aaronson NERFINISHED ⓘ |
| conclusion |
known laws of physics do not appear to allow efficient solution of NP-complete problems
ⓘ
quantum mechanics increases computational power but likely not enough to solve NP-complete problems in polynomial time ⓘ small changes to physical laws could dramatically change computational power ⓘ |
| creator | Scott Aaronson NERFINISHED ⓘ |
| examines |
computational implications of closed timelike curves
ⓘ
computational implications of nonlinear quantum mechanics ⓘ computational implications of postselected quantum measurements ⓘ whether quantum gravity could change computational complexity ⓘ |
| field |
computational complexity theory
ⓘ
physics of computation ⓘ quantum computing ⓘ theoretical computer science ⓘ |
| focus |
how physical laws constrain efficient computation
ⓘ
implications of quantum mechanics for computational power ⓘ whether exotic physical theories could solve NP-complete problems efficiently ⓘ |
| genre |
academic research
ⓘ
survey and position paper ⓘ |
| language | English ⓘ |
| position |
complexity theory can help rule out unphysical theories
ⓘ
computational complexity provides constraints on possible physical laws ⓘ |
| relatedTo |
Church–Turing thesis
NERFINISHED
ⓘ
NP-completeness NERFINISHED ⓘ computational models based on exotic physics ⓘ extended Church–Turing thesis NERFINISHED ⓘ physical limits of computation ⓘ quantum speedups ⓘ |
| topic |
BQP
NERFINISHED
ⓘ
NP ⓘ black-hole computation thought experiments ⓘ hypercomputation thought experiments ⓘ limits of efficient computation ⓘ nonlinear quantum mechanics and computation ⓘ physical Church–Turing thesis ⓘ postselection in quantum computation ⓘ quantum complexity classes ⓘ relationship between physics and complexity theory ⓘ relativistic computation ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.