The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been show
n to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.
We analyze continuous-time quantum walks on necklace graphs - cyclical graphs consisting of many copies of a smaller graph (pearl). Using a Bloch-type ansatz for the eigenfunctions, we block-diagonalize the Hamiltonian, reducing the effective size of
the problem to the size of a single pearl. We then present a general approach for showing that the mixing time scales (with growing size of the necklace) similarly to that of a simple walk on a cycle. Finally, we present results for mixing on several necklace graphs.
We present a Hamiltonian quantum computation scheme universal for quantum computation (BQP). Our Hamiltonian is a sum of a polynomial number (in the number of gates L in the quantum circuit) of time-independent, constant-norm, 2-local qubit-qubit int
eraction terms. Furthermore, each qubit in the system interacts only with a constant number of other qubits. The computer runs in three steps - starts in a simple initial product-state, evolves it for time of order L^2 (up to logarithmic factors) and wraps up with a two-qubit measurement. Our model differs from the previous universal 2-local Hamiltonian constructions in that it does not use perturbation gadgets, does not need large energy penalties in the Hamiltonian and does not need to run slowly to ensure adiabatic evolution.
We present two universal models of quantum computation with a time-independent, frustration-free Hamiltonian. The first construction uses 3-local (qubit) projectors, and the second one requires only 2-local qubit-qutrit projectors. We build on Feynma
ns Hamiltonian computer idea and use a railroad-switch type clock register. The resources required to simulate a quantum circuit with L gates in this model are O(L) small-dimensional quantum systems (qubits or qutrits), a time-independent Hamiltonian composed of O(L) local, constant norm, projector terms, the possibility to prepare computational basis product states, a running time O(L log^2 L), and the possibility to measure a few qubits in the computational basis. Our models also give a simplified proof of the universality of 3-local Adiabatic Quantum Computation.
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 involve
d 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 doesnt 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.
