Product states optimize quantum $p$-spin models for large $p$

• URL: http://arxiv.org/abs/2309.11709v3
• Date: Fri, 5 Apr 2024 15:15:11 GMT
• Title: Product states optimize quantum $p$-spin models for large $p$
• Authors: Eric R. Anschuetz, David Gamarnik, Bobak T. Kiani,
• Abstract summary: We consider the problem of estimating the maximal energy of quantum $p$-local spin glass random Hamiltonians. Our results challenge prevailing beliefs in physics that extremely low-temperature states of random local Hamiltonians should exhibit non-negligible entanglement.
• Score: 2.594420805049218
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of estimating the maximal energy of quantum $p$-local spin glass random Hamiltonians, the quantum analogues of widely studied classical spin glass models. Denoting by $E^*(p)$ the (appropriately normalized) maximal energy in the limit of a large number of qubits $n$, we show that $E^*(p)$ approaches $\sqrt{2\log 6}$ as $p$ increases. This value is interpreted as the maximal energy of a much simpler so-called Random Energy Model, widely studied in the setting of classical spin glasses. Our most notable and (arguably) surprising result proves the existence of near-maximal energy states which are product states, and thus not entangled. Specifically, we prove that with high probability as $n\to\infty$, for any $E<E^*(p)$ there exists a product state with energy $\geq E$ at sufficiently large constant $p$. Even more surprisingly, this remains true even when restricting to tensor products of Pauli eigenstates. Our approximations go beyond what is known from monogamy-of-entanglement style arguments -- the best of which, in this normalization, achieve approximation error growing with $n$. Our results not only challenge prevailing beliefs in physics that extremely low-temperature states of random local Hamiltonians should exhibit non-negligible entanglement, but they also imply that classical algorithms can be just as effective as quantum algorithms in optimizing Hamiltonians with large locality -- though performing such optimization is still likely a hard problem. Our results are robust with respect to the choice of the randomness (disorder) and apply to the case of sparse random Hamiltonian using Lindeberg's interpolation method. The proof of the main result is obtained by estimating the expected trace of the associated partition function, and then matching its asymptotics with the extremal energy of product states using the second moment method.

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)
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians [2.594420805049218]
  We consider the problem of estimating the ground state energy of quantum $p$local spin glass random Hamiltonians. Our main result shows that the maximum energy achievable by product states has a well-defined limit.
  arXiv  Detail & Related papers  (2024-04-03T18:00:05Z)
• The classical limit of Quantum Max-Cut [0.18416014644193066]
  We show that the limit of large quantum spin $S$ should be understood as a semiclassical limit. We present two families of classical approximation algorithms for $mathrmQMaxCut_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states.
  arXiv  Detail & Related papers  (2024-01-23T18:53:34Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• 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)
• Some Remarks on the Regularized Hamiltonian for Three Bosons with Contact Interactions [77.34726150561087]
  We discuss some properties of a model Hamiltonian for a system of three bosons interacting via zero-range forces in three dimensions. In particular, starting from a suitable quadratic form $Q$, the self-adjoint and bounded from below Hamiltonian $mathcal H$ can be constructed. We show that the threshold value $gamma_c$ is optimal, in the sense that the quadratic form $Q$ is unbounded from below if $gammagamma_c$.
  arXiv  Detail & Related papers  (2022-07-01T10:01:14Z)
• 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)
• Hamiltonian simulation with random inputs [74.82351543483588]
  Theory of average-case performance of Hamiltonian simulation with random initial states. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models.
  arXiv  Detail & Related papers  (2021-11-08T19:08:42Z)
• Improved approximation algorithms for bounded-degree local Hamiltonians [12.961180148172197]
  We describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. We extend our results to $k$-local Hamiltonians and entangled initial states.
  arXiv  Detail & Related papers  (2021-05-03T22:23:47Z)

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.