Limits on Efficient Computation in the Physical World
arXiv:quant-ph/0412143
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.
UC Berkeley PhD thesis, 258 pages. Some minor errors fixed
References in corpus (44)
- Good Quantum Error-Correcting Codes Exist
- Efficient classical simulation of slightly entangled quantum computations
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Persistent entanglement in arrays of interacting particles
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
- The holographic principle
- Measurement-based quantum computation with cluster states
- Improved Simulation of Stabilizer Circuits
- Strengths and Weaknesses of Quantum Computing
- Discreteness of area and volume in quantum gravity
- Quantum Algorithms Revisited
- A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound
- Quantum fingerprinting
- A Quantum Random Walk Search Algorithm
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Quantum Theory of Probability and Decisions
- Separability of very noisy mixed states and implications for NMR quantum computing
- Computational capacity of the universe
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- Quantum measurements and the Abelian Stabilizer Problem
- Quantum Theory From Five Reasonable Axioms
- An example of the difference between quantum and classical random walks
- Unknown Quantum States: The Quantum de Finetti Representation
- Entangled Quantum States of Magnetic Dipoles
- Stability of macroscopic entanglement under decoherence
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Implementation of the Five Qubit Error Correction Benchmark
- Quantum communication complexity of symmetric predicates
- Choice of Consistent Family, and Quantum Incompatibility
- NP-complete Problems and Physical Reality
- Spatial search and the Dirac equation
- Quantum NP - A Survey
- Quantum lower bounds for the collision and the element distinctness problems
- Improved Quantum Communication Complexity Bounds for Disjointness and Equality
- A Comparison of Quantum Oracles
- Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
- Is Quantum Mechanics An Island In Theoryspace?
- Could Grover's quantum algorithm help in searching an actual database?
- A quantum lower bound for the collision problem
- 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
- Book Review: 'A New Kind of Science'
Cited by in corpus (9)
- Circuit Quantum Electrodynamics
- NP-complete Problems and Physical Reality
- A review of Quantum Cellular Automata
- Quantum Computing's Classical Problem, Classical Computing's Quantum Problem
- Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful
- Is Post Selection Physical: A Device Independent Outlook
- The Observer Class Hypothesis
- One-in-Two-Matching Problem is NP-complete
- Quantum Computing, Postselection, and Probabilistic Polynomial-Time