Local Hamiltonians in Quantum Computation

Abstract

In this thesis, I investigate aspects of local Hamiltonians in quantum computing. First, I focus on the Adiabatic Quantum Computing model, based on evolution with a time dependent Hamiltonian. I show that to succeed using AQC, the Hamiltonian involved must have local structure, which leads to a result about eigenvalue gaps from information theory. I also improve results about simulating quantum circuits with AQC. Second, I look at classically simulating time evolution with local Hamiltonians and finding their ground state properties. I give a numerical method for finding the ground state of translationally invariant Hamiltonians on an infinite tree. This method is based on imaginary time evolution within the Matrix Product State ansatz, and uses a new method for bringing the state back to the ansatz after each imaginary time step. I then use it to investigate the phase transition in the transverse field Ising model on the Bethe lattice. Third, I focus on locally constrained quantum problems Local Hamiltonian and Quantum Satisfiability and prove several new results about their complexity. Finally, I define a Hamiltonian Quantum Cellular Automaton, a continuous-time model of computation which doesn't require control during the computation process, only preparation of product initial states. I construct two of these, showing that time evolution with a simple, local, translationally invariant and time-independent Hamiltonian can be used to simulate quantum circuits.

Ph.D. Thesis, June 2008, MIT, 176 pages

References in corpus (46)

• Fault-tolerant quantum computation by anyons
• The density-matrix renormalization group
• Efficient classical simulation of slightly entangled quantum computations
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Efficient simulation of one-dimensional quantum many-body systems
• Strengths and Weaknesses of Quantum Computing
• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• DMRG and periodic boundary conditions: a quantum information perspective
• Classical simulation of quantum many-body systems with a tree tensor network
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Robustness of adiabatic quantum computation
• Simulation of topological field theories by quantum computers
• Variational study of hard-core bosons in a 2-D optical lattice using Projected Entangled Pair States (PEPS)
• The power of quantum systems on a line
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• A Limit on the Speed of Quantum Computation in Determining Parity
• Quantum Lower Bounds by Polynomials
• Error correcting codes for adiabatic quantum computation
• Unified derivations of measurement-based schemes for quantum computation
• Anyon computers with smaller groups
• Towards Fault Tolerant Adiabatic Quantum Computation
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Adiabatic Quantum Computing for Random Satisfiability Problems
• Both Toffoli and Controlled-NOT need little help to do universal quantum computation
• Cavity method for quantum spin glasses on the Bethe lattice
• A Quantum Algorithm for the Hamiltonian NAND Tree
• The Quantum Transverse Field Ising Model on an Infinite Tree from Matrix Product States
• Quantum Adiabatic Evolution Algorithms with Different Paths
• An Elementary Proof of the Quantum Adiabatic Theorem
• Exponential complexity of an adiabatic algorithm for an NP-complete problem
• A new construction for a QMA complete 3-local Hamiltonian
• The computational difficulty of finding MPS ground states
• Hamiltonian Quantum Cellular Automata in 1D
• Quantum simulators, continuous-time automata, and translationally invariant systems
• A quantum cellular automaton for universal quantum computation
• Quantum Randomness and Nondeterminism
• A universally programmable Quantum Cellular Automaton
• Quantum Computation Beyond the Circuit Model
• Spin-1/2 particles moving on a 2D lattice with nearest-neighbor interactions can realize an autonomous quantum computer
• Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
• Robustness of Adiabatic Quantum Computing
• Models of Quantum Cellular Automata
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• Limitations of some simple adiabatic quantum algorithms
• Quantum adiabatic evolutions that can't be used to design efficient algorithms

Cited by in corpus (10)

• Adiabatic Quantum Computing
• The power of quantum systems on a line
• Quantum Hamiltonian Complexity
• Universal Quantum Hamiltonians
• Quantum Walks
• Quantum Computation Beyond the Circuit Model
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• Oracle complexity classes and local measurements on physical Hamiltonians
• Approximation, Proof Systems, and Correlations in a Quantum World