Complexity and Simulation of Many-Body Quantum Systems

Abstract

The Hamiltonians of quantum many-body systems can display an extremely diverse range of behaviours. In this thesis we show that there exist simple systems which can simulate all other quantum many-body systems, including all of their physical properties. We call these universal Hamiltonians. We first define a notion of analogue simulation which captures what it means for the Hamiltonian of one system to be reproduced in the Hamiltonian of another physical system. Then we obtain a full classification of simulation power in the case of families of Hamiltonians built up as a linear combination of 2-local qubit interactions. We also prove universality for other restricted classes of Hamiltonians such as those for which all the interaction strengths have the same sign or for Hamiltonians with spatially restricted interaction graphs. And we prove universality for large classes of qudit Hamiltonians (where the local dimension d > 2). Universality of a family of Hamiltonians implies that the problem of estimating the ground state energy, known as the Local Hamiltonian problem, is QMA-complete for Hamiltonians from that family. Our results prove that this is the case for many restricted families of Hamiltonians, for which the complexity of the Local Hamiltonian problem was not previously known. We also show that the Local Hamiltonian problem is QMAEXP-complete for a translationally invariant Hamiltonian of 4-local interactions between spins of dimension d=4, arranged on a face-centred cubic lattice, by directly encoding a verifier circuit into the interaction terms. Finally, we consider the problem of simulating a local measurement in the ground space of a local Hamiltonian, introduced by Ambainis as APX-SIM. We simplify some of the prior work on this problem and prove some previously unknown complexity class inequalities. We show that our notion of simulation preserves hardness of this problem and obtain a complexity classification of APX-SIM for Hamiltonians of 2-local qubit interactions.

Date of Award	23 Jan 2019
Original language	English
Awarding Institution	University of Bristol
Supervisor	Ashley M R Montanaro (Supervisor) & Raphael Clifford (Supervisor)