Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The Bose-Hubbard model is QMA-complete

Andrew M. Childs, David Gosset, Zak Webb

Published Jan 1, 2013• 28 citations
OpenAlex

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.

Related papers

Electronic Structure in a Fixed Basis is QMA-complete

Bryan O’Gorman, Sandy Irani, James Daniel Whitfield +1 more

Finding the ground state energy of electrons subject to an external electric field is a fundamental problem in computational chemistry. We prove that this electronic-structure problem, when restricted to a fixed single-particle basis and fixed number of electrons, is QMA-complete. Schuch and Verstraete have shown hardness for the electronic-structure problem with an additional site-specific external magnetic field, but without the restriction to a fixed basis. In their reduction, a local Hamiltonian on qubits is encoded in the site-specific magnetic field. In our reduction, the local Hamiltonian is encoded in the choice of spatial orbitals used to discretize the electronic-structure Hamiltonian. As a step in their proof, Schuch and Verstraete show a reduction from the antiferromagnetic Heisenberg Hamiltonian to the Fermi-Hubbard Hamiltonian. We combine this reduction with the fact that the antiferromagnetic Heisenberg Hamiltonian is QMA-hard to observe that the Fermi-Hubbard Hamiltonian on generic graphs is QMA-hard, even when all the hopping coefficients have the same sign. We then reduce from Fermi-Hubbard by showing that an instance of Fermi-Hubbard can be closely approximated by an instance of the Electronic-Structure Hamiltonian in a fixed basis. Finally, we show that estimating the energy of the lowest-energy Slater-determinant state (i.e., the Hartree-Fock state) is NP-complete for the Electronic-Structure Hamiltonian in a fixed basis.

arXiv:2103.08215•Mar 15, 2021•4 citations

A phase-space method for the Bose-Hubbard model

Jain, P., Crispin W. Gardiner

We present a phase-space method for the Bose-Hubbard model based on the Q-function representation. In particular, we consider two model Hamiltonians in the mean-field approximation; the first is the standard "one site" model where quantum tunneling is approximated entirely using mean-field terms; the second "two site" model explicitly includes tunneling between two adjacent sites while treating tunneling with other neighbouring sites using the mean-field approximation. The ground state is determined by minimizing the classical energy functional subject to quantum mechanical constraints, which take the form of uncertainty relations. For each model Hamiltonian we compare the ground state results from the Q-function method with the exact numerical solution. The results from the Q-function method, which are easy to compute, give a good qualitative description of the main features of the Bose-Hubbard model including the superfluid to Mott insulator. We find the quantum mechanical constraints dominate the problem and show there are some limitations of the method particularly in the weak lattice regime.

arXiv:cond-mat/0404642•Apr 27, 2004•3 citations

Intractability of Electronic Structure in a Fixed Basis

Bryan O’Gorman, Sandy Irani, James Daniel Whitfield +1 more

Finding the ground-state energy of electrons subject to an external electric field is a fundamental problem in computational chemistry.While the theory of QMA-completeness has been instrumental in understanding the complexity of finding ground states in many-body quantum systems, prior to this work it has been unknown whether or not the special form of the Hamiltonian for the electronic structure of molecules can be exploited to find ground states efficiently or whether the problem remains hard for this special case.We prove that the electronic-structure problem, when restricted to a fixed single-particle basis and a fixed number of electrons, is QMA-complete.In our proof, the local Hamiltonian is encoded in the choice of spatial orbitals used to discretize the electronic-structure Hamiltonian.In contrast, Schuch and Verstraete have proved hardness for the electronic-structure problem with an additional site-specific external magnetic field, but without the restriction to a fixed basis, by encoding a local Hamiltonian on qubits in the site-specific magnetic field.We also show that estimation of the energy of the lowest-energy Slater-determinant state (i.e., the Hartree-Fock state) is nondeterministic polynomial time (NP)-complete for the electronic-structure Hamiltonian in a fixed basis.

PRX Quantum•May 2, 2022•30 citations

Rigorous Results for the Ground States of the Spin-2 Bose-Hubbard Model

Hong Wei Yang, Hosho Katsura

We present rigorous and universal results for the ground states of the f=2 spinor Bose-Hubbard model. The model includes three two-body on-site interaction terms, two of which are spin dependent while the other one is spin independent. We prove that, depending only on the coefficients of the two spin-dependent terms, the ground state exhibits maximum or minimum total spin or SU(5) ferromagnetism. Exact ground-state degeneracies and the forms of ground-state wave function are also determined in each case. All these results are valid regardless of dimension, lattice structure, or particle number. Our approach takes advantage of the symmetry of the Hamiltonian and employs mathematical tools including the Perron-Frobenius theorem and the Lie algebra so(5).

arXiv:1803.09441•Physical Review Letters•Feb 7, 2019•4 citations

A phase-space method for the Bose–Hubbard model: application to mean-field models

P Jain, Crispin W. Gardiner

We present a phase-space method for the Bose–Hubbard model based on the Q-function representation. In particular, we consider two model Hamiltonians in the mean-field approximation; the first is the standard 'one-site' model where quantum tunnelling is approximated entirely using mean-field terms; the second 'two-site' model explicitly includes tunnelling between two adjacent sites while treating tunnelling with other neighbouring sites using the mean-field approximation. The ground state is determined by minimizing the classical energy functional subject to quantum mechanical constraints, which take the form of uncertainty relations. For each model Hamiltonian, we compare the ground state results from the Q-function method with the exact numerical solution. The results from the Q-function method, which are easy to compute, give a good qualitative description of the main features of the Bose–Hubbard model including the superfluid to Mott insulator. We find the quantum mechanical constraints dominate the problem and show there are some limitations of the method particularly in the weak lattice regime.

Journal of Physics B Atomic Molecular and Optical Physics•Sep 15, 2004•11 citations

Operator growth and Krylov complexity in Bose-Hubbard model

Arpan Bhattacharyya, Debodirna Ghosh, Poulami Nandi

Abstract We study Krylov complexity of a one-dimensional Bosonic system, the celebrated Bose-Hubbard Model. The Bose-Hubbard Hamiltonian consists of interacting bosons on a lattice, describing ultra-cold atoms. Apart from showing superfluid-Mott insulator phase transition, the model also exhibits both chaotic and integrable (mixed) dynamics depending on the value of the interaction parameter. We focus on the three-site Bose Hubbard Model (with different particle numbers), which is known to be highly mixed. We use the Lanczos algorithm to find the Lanczos coefficients and the Krylov basis. The orthonormal Krylov basis captures the operator growth for a system with a given Hamiltonian. However, the Lanczos algorithm needs to be modified for our case due to the instabilities instilled by the piling up of computational errors. Next, we compute the Krylov complexity and its early and late-time behaviour. Our results capture the chaotic and integrable nature of the system. Our paper takes the first step to use the Lanczos algorithm non-perturbatively for a discrete quartic bosonic Hamiltonian without depending on the auto-correlation method.

arXiv:2306.05542•Journal of High Energy Physics•Dec 18, 2023•30 citations
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.
Finding the ground state energy of electrons subject to an external electric field is a fundamental problem in computational chemistry. We prove that this electronic-structure problem, when restricted to a fixed single-particle basis and fixed number of electrons, is QMA-complete. Schuch and Verstraete have shown hardness for the electronic-structure problem with an additional site-specific external magnetic field, but without the restriction to a fixed basis. In their reduction, a local Hamiltonian on qubits is encoded in the site-specific magnetic field. In our reduction, the local Hamiltonian is encoded in the choice of spatial orbitals used to discretize the electronic-structure Hamiltonian. As a step in their proof, Schuch and Verstraete show a reduction from the antiferromagnetic Heisenberg Hamiltonian to the Fermi-Hubbard Hamiltonian. We combine this reduction with the fact that the antiferromagnetic Heisenberg Hamiltonian is QMA-hard to observe that the Fermi-Hubbard Hamiltonian on generic graphs is QMA-hard, even when all the hopping coefficients have the same sign. We then reduce from Fermi-Hubbard by showing that an instance of Fermi-Hubbard can be closely approximated by an instance of the Electronic-Structure Hamiltonian in a fixed basis. Finally, we show that estimating the energy of the lowest-energy Slater-determinant state (i.e., the Hartree-Fock state) is NP-complete for the Electronic-Structure Hamiltonian in a fixed basis.
We present a phase-space method for the Bose-Hubbard model based on the Q-function representation. In particular, we consider two model Hamiltonians in the mean-field approximation; the first is the standard "one site" model where quantum tunneling is approximated entirely using mean-field terms; the second "two site" model explicitly includes tunneling between two adjacent sites while treating tunneling with other neighbouring sites using the mean-field approximation. The ground state is determined by minimizing the classical energy functional subject to quantum mechanical constraints, which take the form of uncertainty relations. For each model Hamiltonian we compare the ground state results from the Q-function method with the exact numerical solution. The results from the Q-function method, which are easy to compute, give a good qualitative description of the main features of the Bose-Hubbard model including the superfluid to Mott insulator. We find the quantum mechanical constraints dominate the problem and show there are some limitations of the method particularly in the weak lattice regime.
Finding the ground-state energy of electrons subject to an external electric field is a fundamental problem in computational chemistry.While the theory of QMA-completeness has been instrumental in understanding the complexity of finding ground states in many-body quantum systems, prior to this work it has been unknown whether or not the special form of the Hamiltonian for the electronic structure of molecules can be exploited to find ground states efficiently or whether the problem remains hard for this special case.We prove that the electronic-structure problem, when restricted to a fixed single-particle basis and a fixed number of electrons, is QMA-complete.In our proof, the local Hamiltonian is encoded in the choice of spatial orbitals used to discretize the electronic-structure Hamiltonian.In contrast, Schuch and Verstraete have proved hardness for the electronic-structure problem with an additional site-specific external magnetic field, but without the restriction to a fixed basis, by encoding a local Hamiltonian on qubits in the site-specific magnetic field.We also show that estimation of the energy of the lowest-energy Slater-determinant state (i.e., the Hartree-Fock state) is nondeterministic polynomial time (NP)-complete for the electronic-structure Hamiltonian in a fixed basis.
We present rigorous and universal results for the ground states of the f=2 spinor Bose-Hubbard model. The model includes three two-body on-site interaction terms, two of which are spin dependent while the other one is spin independent. We prove that, depending only on the coefficients of the two spin-dependent terms, the ground state exhibits maximum or minimum total spin or SU(5) ferromagnetism. Exact ground-state degeneracies and the forms of ground-state wave function are also determined in each case. All these results are valid regardless of dimension, lattice structure, or particle number. Our approach takes advantage of the symmetry of the Hamiltonian and employs mathematical tools including the Perron-Frobenius theorem and the Lie algebra so(5).
We present a phase-space method for the Bose–Hubbard model based on the Q-function representation. In particular, we consider two model Hamiltonians in the mean-field approximation; the first is the standard 'one-site' model where quantum tunnelling is approximated entirely using mean-field terms; the second 'two-site' model explicitly includes tunnelling between two adjacent sites while treating tunnelling with other neighbouring sites using the mean-field approximation. The ground state is determined by minimizing the classical energy functional subject to quantum mechanical constraints, which take the form of uncertainty relations. For each model Hamiltonian, we compare the ground state results from the Q-function method with the exact numerical solution. The results from the Q-function method, which are easy to compute, give a good qualitative description of the main features of the Bose–Hubbard model including the superfluid to Mott insulator. We find the quantum mechanical constraints dominate the problem and show there are some limitations of the method particularly in the weak lattice regime.
Abstract We study Krylov complexity of a one-dimensional Bosonic system, the celebrated Bose-Hubbard Model. The Bose-Hubbard Hamiltonian consists of interacting bosons on a lattice, describing ultra-cold atoms. Apart from showing superfluid-Mott insulator phase transition, the model also exhibits both chaotic and integrable (mixed) dynamics depending on the value of the interaction parameter. We focus on the three-site Bose Hubbard Model (with different particle numbers), which is known to be highly mixed. We use the Lanczos algorithm to find the Lanczos coefficients and the Krylov basis. The orthonormal Krylov basis captures the operator growth for a system with a given Hamiltonian. However, the Lanczos algorithm needs to be modified for our case due to the instabilities instilled by the piling up of computational errors. Next, we compute the Krylov complexity and its early and late-time behaviour. Our results capture the chaotic and integrable nature of the system. Our paper takes the first step to use the Lanczos algorithm non-perturbatively for a discrete quartic bosonic Hamiltonian without depending on the auto-correlation method.