Limits on Efficient Computation in the Physical World

2004/12/20 by Scott Aaronson, Aaronson, Scott · 22 citations
Computer Science · Physics and Astronomy · #Algorithm #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computation #Computational Complexity (cs.CC) #Computer science #Epistemology #FOS: Computer and information sciences #FOS: Physical sciences #Philosophy #Physical science #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum computer #Quantum mechanics #Theoretical computer science #Theoretical physics #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0412143

published in arXiv (Cornell University) (Cornell University) · UC Berkeley PhD thesis, 258 pages. Some minor errors fixed

openalex publication_date 2004/12/20 · arxiv created 2005/02/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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.

Citations

• The fabric of reality
• Quantum NP - A Survey
• Quantum searching a classical database (or how we learned to stop worrying and love the bomb)
• Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete
• Is Quantum Mechanics An Island In Theoryspace?
• Spatial search and the Dirac equation
• Relativizations of the P = ?NP Question
• Computational capacity of the universe
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Strengths and Weaknesses of Quantum Computing
• Exponential algorithmic speedup by a quantum walk
• Universal upper bound on the entropy-to-energy ratio for bounded systems
• Quantum Complexity Theory
• Gaussian elimination is not optimal
• BPP and the polynomial hierarchy
• Spatial search by quantum walk
• Experimental Realization of Einstein-Podolsky-Rosen-BohmGedankenexperiment: A New Violation of Bell's Inequalities
• Improved simulation of stabilizer circuits
• On the Structure of Polynomial Time Reducibility
• NP is as easy as detecting unique solutions
• Parity, circuits, and the polynomial-time hierarchy
• The holographic principle
• Relative to a Random OracleA, \bf P^A ≠ \bf NP^A ≠ co-\bf NP^A with Probability 1
• Exponential separation of quantum and classical one-way communication complexity
• A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound
• Algebraic methods in the theory of lower bounds for Boolean circuit complexity
• Algebraic methods for interactive proof systems
• A fast quantum mechanical algorithm for database search
• Nonlinear Quantum Mechanics Implies Polynomial-Time Solution forNP-Complete and #PProblems
• Quantum vs. classical communication and computation
• Measurement-based quantum computation with cluster states
• How easy is local search?
• Quantum Algorithms Revisited
• Quantum interference and the quantum potential
• Good Quantum Error-Correcting Codes Exist
• Quantum lower bounds by polynomials
• A quantum lower bound for the collision problem
• Quantum Theory From Five Reasonable Axioms
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Quantum computations: algorithms and error correction
• Quantum circuit complexity
• Simulating physics with computers
• A Suggested Interpretation of the Quantum Theory in Terms of "Hidden" Variables. I
• Natural Proofs

Related

• Physical complexity and black hole quantum computers
• One Complexity Theorist's View of Quantum Computing
• On Measurement and Computation
• The Nature of Computation
• Quantum Complexity vs Classical Complexity: A Survey