home | literature reviews

"NP-complete Problems and Physical Reality", Scott Aaronson, 2005

Reviewed August 23, 2023

Citation: Aaronson, Scott. "Guest column: NP-complete problems and physical reality." ACM Sigact News 36.1 (2005): 30-52.

Web: https://arxiv.org/abs/quant-ph/0502072

Tags: Philosophical, Computer-scientific, No-go

This paper gives a delightful discussion of why the statement "NP-complete problems cannot be efficiently solved by physics" should be taken as a foundational physical law.

This gives a good gut-check for topological quantum computing: the quantum field computer can always be efficiently BQP-simulated. Perhaps if Freedman had read this article he would have been more skeptical about his claim in

> Freedman, Michael H. "P/NP, and the quantum field computer." Proceedings of the National Academy of Sciences 95.1 (1998): 98-101.

that TQFTs might be able to solve #P-complete problems.