Limits on Efficient Computation in the Physical World
<|reference_start|>Limits on Efficient Computation in the Physical World: 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.<|reference_end|>
@article{aaronson2004limits,
    title={Limits on Efficient Computation in the Physical World},
    author={Scott Aaronson},
    journal={arXiv preprint arXiv:quant-ph/0412143},
    year={2004},
    archivePrefix={arXiv},
    eprint={quant-ph/0412143},
    primaryClass={quant-ph cs.CC}
}