Complexity Classification of Product State Problems for Local Hamiltonians

• URL: http://arxiv.org/abs/2401.06725v2
• Date: Mon, 06 Jan 2025 18:38:18 GMT
• Title: Complexity Classification of Product State Problems for Local Hamiltonians
• Authors: John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, Justin Yirka,
• Abstract summary: We classify the complexity of finding minimum-energy product states for Hamiltonians defined by any fixed set of allowed 2-qubit interactions. We prove that estimating the minimum energy of a product state is in P if and only if all allowed interactions are 1-local, and NP-complete otherwise.
• Score: 0.94371657253557
• License:
• Abstract: Product states, unentangled tensor products of single qubits, are a ubiquitous ansatz in quantum computation, including for state-of-the-art Hamiltonian approximation algorithms. A natural question is whether we should expect to efficiently solve product state problems on any interesting families of Hamiltonians. We completely classify the complexity of finding minimum-energy product states for Hamiltonians defined by any fixed set of allowed 2-qubit interactions. Our results follow a line of work classifying the complexity of solving Hamiltonian problems and classical constraint satisfaction problems based on the allowed constraints. We prove that estimating the minimum energy of a product state is in P if and only if all allowed interactions are 1-local, and NP-complete otherwise. Equivalently, any family of non-trivial two-body interactions generates Hamiltonians with NP-complete product-state problems. Our hardness constructions only require coupling strengths of constant magnitude. A crucial component of our proofs is a collection of hardness results for a new variant of the Vector Max-Cut problem, which should be of independent interest. Our definition involves sums of distances rather than squared distances and allows linear stretches. We similarly give a proof that the original Vector Max-Cut problem is NP-complete in 3 dimensions. This implies that optimizing over product states for Quantum Max-Cut (the quantum Heisenberg model) is NP-complete, even when every term is guaranteed to have positive unit weight.

Related papers

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Quasi-quantum states and the quasi-quantum PCP theorem [0.21485350418225244]
  We show that solving the $k$-local Hamiltonian over the quasi-quantum states is equivalent to optimizing a distribution of assignment over a classical $k$-local CSP. Our main result is a PCP theorem for the $k$-local Hamiltonian over the quasi-quantum states in the form of a hardness-of-approximation result.
  arXiv  Detail & Related papers  (2024-10-17T13:43:18Z)
• Coherence generation with Hamiltonians [44.99833362998488]
  We explore methods to generate quantum coherence through unitary evolutions. This quantity is defined as the maximum derivative of coherence that can be achieved by a Hamiltonian. We identify the quantum states that lead to the largest coherence derivative induced by the Hamiltonian.
  arXiv  Detail & Related papers  (2024-02-27T15:06:40Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
  arXiv  Detail & Related papers  (2023-09-19T22:53:17Z)
• On The Study Of Partial Qubit Hamiltonian For Efficient Molecular Simulation Using Variational Quantum Eigensolvers [0.0]
  We present a new approach for extracting information from the partial qubit Hamiltonian of simple molecules to design more efficient variational quantum eigensolvers. The results of this study have the potential to demonstrate the potential advancement in the field of quantum computing and its implementation in quantum chemistry.
  arXiv  Detail & Related papers  (2023-08-24T03:25:05Z)
• Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture [0.0]
  We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem. These problems do not have a guiding state provided as a part of the input, but merely come with the promise that one exists. We show that guidable local Hamiltonian problems for both classes of guiding states are $mathsfQCMA$-complete in the inverse-polynomial precision setting.
  arXiv  Detail & Related papers  (2023-02-22T19:00:00Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations [17.209060627291315]
  We prove concentration for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from [DPMRF22]; (ii) injective matrix product states, answering an open question from [DPMRF22]; (iii) output states of dense Hamiltonian evolution, i.e. states of the form $eiota H(p) cdots eiota H(1) |psirangle for any $n$-qubit product state $|psirangle$, where each $H(
  arXiv  Detail & Related papers  (2022-09-06T18:00:02Z)
• Simultaneous Stoquasticity [0.0]
  Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation.
  arXiv  Detail & Related papers  (2022-02-17T19:08:30Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)

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.