The Bose-Hubbard model is QMA-complete

DOI10.1007/978-3-662-43948-7_26zbMATH Open1409.68122arXiv1311.3297OpenAlexW3099163724MaRDI QIDQ5167751FDOQ5167751

Authors: Andrew M. Childs, David Gosset, Zak Webb 

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients.

Full work available at URL: https://arxiv.org/abs/1311.3297

Recommendations

• scientific article; zbMATH DE number 6538680
• The complexity of quantum spin systems on a two-dimensional square lattice
• The Complexity of the Local Hamiltonian Problem
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Complexity classification of local Hamiltonian problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cited In (5)

• Complexity classification of local Hamiltonian problems
• Title not available (Why is that?)
• On complexity of the quantum Ising model
• Bose-Hubbard model on two-dimensional line graphs
• Approximating ground and excited state energies on a quantum computer

This page was built for publication: The Bose-Hubbard model is QMA-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167751)