Hardness of approximation for ground state problems

• URL: http://arxiv.org/abs/2411.04874v1
• Date: Thu, 07 Nov 2024 17:11:00 GMT
• Title: Hardness of approximation for ground state problems
• Authors: Sevag Gharibian, Carsten Hecht,
• Abstract summary: 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)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: After nearly two decades of research, the question of a quantum PCP theorem for quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a result, proving QMA-hardness of approximation for ground state energy estimation has remained elusive. Recently, it was shown [Bittel, Gharibian, Kliesch, CCC 2023] that a natural problem involving variational quantum circuits is QCMA-hard to approximate within ratio N^(1-eps) for any eps > 0 and N the input size. Unfortunately, this problem was not related to quantum CSPs, leaving the question of hardness of approximation for quantum CSPs open. In this work, 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. In particular, 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). As a bonus, a simplification of our construction yields NP-completeness of approximation for a natural k-SAT reconfiguration problem, to be contrasted with the recent PCP-based PSPACE hardness of approximation results for a different definition of k-SAT reconfiguration [Karthik C.S. and Manurangsi, 2023, and Hirahara, Ohsaka, STOC 2024].

Related papers

• On the complexity of estimating ground state entanglement and free energy [0.6875312133832079]
  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.
  arXiv  Detail & Related papers  (2025-10-08T09:26:57Z)
• Topological control of quantum speed limits [55.2480439325792]
  We show that even if the quantum state is completely dispersionless, QFI in this state remains momentum-resolved.<n>We find bounds on quantum speed limit which scales as $sqrt|C|$ in a (dispersionless) topological phase.
  arXiv  Detail & Related papers  (2025-07-21T18:00:07Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition. We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation [39.20075231137991]
  We address the computation of the cumulative distribution function (CDF) of the spectral measure of the Hamiltonian. We introduce a signal processing technique for identifying the inflection point of the CDF. We conduct numerical experiments on a 26-qubit fully-connected Heisenberg model using a truncated density-matrix renormalization group (DMRG) initial state of low bond dimension.
  arXiv  Detail & Related papers  (2024-05-06T18:00:03Z)
• Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
  Quantum Circuits (PQCs) are still not fully understood outside the scope of their principal application.<n>We analyse the generation of random states in PQCs under restrictions on the qubits connectivities.<n>We place a connection between how steep is the increase on the uniformity of the distribution of the generated states and the generation of entanglement.
  arXiv  Detail & Related papers  (2024-05-03T17:32:55Z)
• Arbitrary Ground State Observables from Quantum Computed Moments [0.0]
  We extend the quantum computed moments (QCM) method to estimate arbitrary ground state observables of quantum systems. We present preliminary results of using QCM to determine the ground state magnetisation and spin-spin correlations of the Heisenberg model.
  arXiv  Detail & Related papers  (2023-12-12T04:29:43Z)
• ADAPT-QSCI: Adaptive Construction of Input State for Quantum-Selected Configuration Interaction [0.0]
  We present a quantum-classical hybrid algorithm for calculating the ground state and its energy of the quantum many-body Hamiltonian. We numerically illustrate that our method, dubbed textitADAPT-QSCI, can yield accurate ground-state energies for small molecules.
  arXiv  Detail & Related papers  (2023-11-02T09:15:50Z)
• On the feasibility of performing quantum chemistry calculations on quantum computers [0.0]
  We propose two criteria for evaluating two leading quantum approaches for finding the ground state of molecules. The first criterion applies to the variational quantum eigensolver (VQE) algorithm. The second criterion applies to the quantum phase estimation (QPE) algorithm.
  arXiv  Detail & Related papers  (2023-06-05T06:41:22Z)
• Many-Body Excited States with a Contracted Quantum Eigensolver [0.0]
  We develop an excited state approach based on the contracted quantum eigensolver (ES-CQE) We show the ES-CQE near-exact accuracy across the majority of states, covering regions of strong and weak electron correlation.
  arXiv  Detail & Related papers  (2023-05-16T17:53:07Z)
• Quantum Eigenvector Continuation for Chemistry Applications [57.70351255180495]
  We show that a significant amount of (quantum) computational effort can be saved by making use of already calculated ground states. In all cases, we show that the PES can be captured using relatively few basis states.
  arXiv  Detail & Related papers  (2023-04-28T19:22:58Z)
• Simulations of Frustrated Ising Hamiltonians with Quantum Approximate Optimization [0.0879626117219674]
  We investigate an alternative approach to preparing materials ground states using the quantum approximate optimization algorithm (QAOA) on near-term quantum computers. We study classical Ising spin models on unit cells of square, Shastry-Sutherland, and triangular lattices, with varying field amplitudes and couplings in the material Hamiltonian. We demonstrate the approach in calculations on a trapped-ion quantum computer and succeed in recovering each ground state of the Shastry-Sutherland unit cell with probabilities close to ideal theoretical values.
  arXiv  Detail & Related papers  (2022-06-10T20:25:40Z)
• Quantum Davidson Algorithm for Excited States [42.666709382892265]
  We introduce the quantum Krylov subspace (QKS) method to address both ground and excited states. By using the residues of eigenstates to expand the Krylov subspace, we formulate a compact subspace that aligns closely with the exact solutions. Using quantum simulators, we employ the novel QDavidson algorithm to delve into the excited state properties of various systems.
  arXiv  Detail & Related papers  (2022-04-22T15:03:03Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• A Quantum Optimal Control Problem with State Constrained Preserving Coherence [68.8204255655161]
  We consider a three-level $Lambda$-type atom subjected to Markovian decoherence characterized by non-unital decoherence channels. We formulate the quantum optimal control problem with state constraints where the decoherence level remains within a pre-defined bound.
  arXiv  Detail & Related papers  (2022-03-24T21:31:34Z)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  Quantum chemistry and materials is one of the most promising applications of quantum computing. Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
  arXiv  Detail & Related papers  (2022-03-14T16:51:36Z)

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.