Interacting boson problems are QMA-hard

Abstract

Computing the ground-state energy of interacting electron (fermion) problems has recently been shown to be hard for QMA, a quantum analogue of the complexity class NP. Fermionic problems are usually hard, a phenomenon widely attributed to the so-called sign problem occurring in Quantum Monte Carlo simulations. The corresponding bosonic problems are, according to conventional wisdom, tractable. Here, we discuss the complexity of interacting boson problems and show that they are also QMA-hard. In addition, we show that the bosonic version of the so-called N-representability problem is QMA-complete, as hard as its fermionic version. As a consequence, these problems are unlikely to have efficient quantum algorithms.

4 pages, comments welcome

References in corpus (8)

• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• A class of quantum many-body states that can be efficiently simulated
• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• The power of quantum systems on a line
• N-representability is QMA-complete
• A new construction for a QMA complete 3-local Hamiltonian
• A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems

Cited by in corpus (26)

• Hamiltonian complexity
• Quantum Hamiltonian Complexity
• A Separability-Entanglement Classifier via Machine Learning
• Computational Complexity in Electronic Structure
• Introduction to Quantum Algorithms for Physics and Chemistry
• Symmetric Extension of Two-Qubit States
• Quantum de Finetti theorem under fully-one-way adaptive measurements
• Measures of quantum computing speedup
• Continuous-variable gate decomposition for the Bose-Hubbard model
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Approximation algorithms for QMA-complete problems
• The quantum marginal problem for symmetric states: applications to variational optimization, nonlocality and self-testing
• Clock Quantum Monte Carlo: an imaginary-time method for real-time quantum dynamics
• The Bose-Hubbard model is QMA-complete
• Determining system Hamiltonian from eigenstate measurements without correlation functions
• Physical origins of ruled surfaces on the reduced density matrices geometry
• Non-Identity Check Remains QMA-Complete for Short Circuits
• Detecting Consistency of Overlapping Quantum Marginals by Separability
• Complexity classification of local Hamiltonian problems
• Rank Reduction for the Local Consistency Problem
• Electronic Structure in a Fixed Basis is QMA-complete
• Approximation, Proof Systems, and Correlations in a Quantum World
• Symmetric vs. bosonic extension for bipartite states
• Quantum marginals, faces, and coatoms
• Finding the Dynamics of an Integrable Quantum Many-Body System via Machine Learning
• Approximating Ground and Excited State Energies on a Quantum Computer