On the complexity of estimating ground state entanglement and free energy

• URL: http://arxiv.org/abs/2510.06796v1
• Date: Wed, 08 Oct 2025 09:26:57 GMT
• Title: On the complexity of estimating ground state entanglement and free energy
• Authors: Sevag Gharibian, Jonas Kamminga,
• Abstract summary: We study the complexity of estimating ground state entanglement, and entropy estimation for low energy states and Gibbs states.<n>We yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians.
• Score: 0.6875312133832079
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).

Related papers

• Superstate Quantum Mechanics [35.18016233072556]
  We introduce Superstate Quantum Mechanics (SQM) as a theory that considers states in Hilbert space subject to multiple quadratic constraints.<n>In this case, the stationary SQM problem is a quantum inverse problem with multiple applications in physics, machine learning, and artificial intelligence.
  arXiv  Detail & Related papers  (2025-01-25T19:41:04Z)
• Hardness of approximation for ground state problems [0.0]
  We show that if instead of focusing on ground state energies, one considers computing properties of the ground space, QCMA-hardness of computing ground space properties can be shown. We show that it is (1) QCMA-complete within ratio N(1-eps) to approximate the Ground State Connectivity problem (GSCON), and (2) QCMA-hard within the same ratio to estimate the amount of entanglement of a local Hamiltonian's ground state, denoted Ground State Entanglement (GSE)
  arXiv  Detail & Related papers  (2024-11-07T17:11:00Z)
• Formalizing, Normalizing, and Splitting the Energy Network Re-Dispatch for Quantum Annealing [37.81697222352684]
  Adiabatic quantum computation (AQC) is a well-established method to approximate the ground state of a quantum system. In this work, we investigate issues in the context of energy network re-dispatch problems. Our results are compared to baselines from an open-source energy network simulation.
  arXiv  Detail & Related papers  (2024-09-15T20:29:40Z)
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation [39.20075231137991]
  We investigate the feasibility of early fault-tolerant quantum algorithms focusing on ground-state energy estimation problems.<n> scaling these methods to larger system sizes reveals three key challenges: the smoothness of the CDF for large supports, the lack of tight lower bounds on the overlap with the true ground state, and the difficulty of preparing high-quality initial states.
  arXiv  Detail & Related papers  (2024-05-06T18:00:03Z)
• Hamiltonian-reconstruction distance as a success metric for the Variational Quantum Eigensolver [1.0916270449935084]
  Variational Quantum Eigensolver (VQE) is a hybrid quantum-classical algorithm for quantum simulation that can run on near-term quantum hardware. A challenge in VQE is to know how close the algorithm's output solution is to the true ground state, when the true ground state and ground-state energy are unknown. Recent developments in Hamiltonian reconstruction give a metric can be used to assess the quality of a variational solution to a Hamiltonian-eigensolving problem.
  arXiv  Detail & Related papers  (2024-03-18T17:28:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Local Hamiltonian Problem with succinct ground state is MA-Complete [0.788657961743755]
  Finding the ground energy of a quantum system is a fundamental problem in condensed matter physics and quantum chemistry.<n>Existing classical algorithms for tackling this problem often assume that the ground state has a succinct classical description.<n>We study the complexity of the local Hamiltonian problem with succinct ground state and prove it is MA-Complete.
  arXiv  Detail & Related papers  (2023-09-18T21:08:51Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Improved Hardness Results for the Guided Local Hamiltonian Problem [1.53934570513443]
  Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. We show that the BQP-completeness persists even with 2-local Hamiltonians. We also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians.
  arXiv  Detail & Related papers  (2022-07-21T01:13:32Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• Einselection from incompatible decoherence channels [62.997667081978825]
  We analyze an open quantum dynamics inspired by CQED experiments with two non-commuting Lindblad operators. We show that Fock states remain the most robust states to decoherence up to a critical coupling.
  arXiv  Detail & Related papers  (2020-01-29T14:15:19Z)
• Pinned QMA: The power of fixing a few qubits in proofs [0.6299766708197883]
  We show that pinning a single qubit via often repeated measurements results in universal quantum computation already with commuting and stoquastic Hamiltonians. We hence identify a comprehensive picture of the computational power of pinning, reminiscent of the power of the one clean qubit model.
  arXiv  Detail & Related papers  (2020-01-10T19:20:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.