Projects per year
Abstract
The calculation of groundstate energies of physical systems can be formalized as the klocal Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensedmatter physics. In this work we characterize the complexity of this problem for all 2local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NPcomplete; polynomialtime equivalent to the Ising model with transverse magnetic fields; or QMAcomplete. The third of these classes has been shown to be StoqMAcomplete by Bravyi and Hastings. The characterization holds even if S does not contain any 1local terms; for example, we prove for the first time QMAcompleteness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2local interactions: for any constant k, all klocal qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomialtime equivalent to the Ising model with transverse magnetic fields; or QMAcomplete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.
Original language  English 

Pages (fromto)  268316 
Number of pages  49 
Journal  SIAM Journal on Computing 
Volume  45 
Issue number  2 
Early online date  23 Mar 2016 
DOIs  
Publication status  Published  Jun 2016 
Keywords
 quantum complexity
 quantum computation
 constraint satisfaction problems
 local Hamiltonian problem
Fingerprint
Dive into the research topics of 'Complexity Classification of Local Hamiltonian Problems'. Together they form a unique fingerprint.Projects
 2 Finished
Profiles

Professor Ashley M R Montanaro
 School of Mathematics  Professor of Quantum Computation
 The Bristol Centre for Nanoscience and Quantum Information
 Algorithms and Complexity
 Mathematical Physics
 Quantum Information Theory
Person: Academic , Member, Group lead