Combinatorial NLTS From the Overlap Gap Property

• URL: http://arxiv.org/abs/2304.00643v3
• Date: Mon, 11 Mar 2024 19:04:15 GMT
• Title: Combinatorial NLTS From the Overlap Gap Property
• Authors: Eric R. Anschuetz and David Gamarnik and Bobak Kiani
• Abstract summary: Anshu, Breuckmann, and Nirkhe [ABN22] resolved positively the so-called No Low-Energy Trivial State conjecture by Freedman and Hastings. The conjecture postulated the existence of linear-size local Hamiltonians on n qubit systems for which no near-ground state can be prepared by a shallow (sublogarithmic depth) circuit.
• Score: 2.915868985330569
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In an important recent development, Anshu, Breuckmann, and Nirkhe [ABN22] resolved positively the so-called No Low-Energy Trivial State (NLTS) conjecture by Freedman and Hastings. The conjecture postulated the existence of linear-size local Hamiltonians on n qubit systems for which no near-ground state can be prepared by a shallow (sublogarithmic depth) circuit. The construction in [ABN22] is based on recently developed good quantum codes. Earlier results in this direction included the constructions of the so-called Combinatorial NLTS -- a weaker version of NLTS -- where a state is defined to have low energy if it violates at most a vanishing fraction of the Hamiltonian terms [AB22]. These constructions were also based on codes. In this paper we provide a "non-code" construction of a class of Hamiltonians satisfying the Combinatorial NLTS. The construction is inspired by one in [AB22], but our proof uses the complex solution space geometry of random K-SAT instead of properties of codes. Specifically, it is known that above a certain clause-to-variables density the set of satisfying assignments of random K-SAT exhibits an overlap gap property, which implies that it can be partitioned into exponentially many clusters each constituting at most an exponentially small fraction of the total set of satisfying solutions. We establish a certain robust version of this clustering property for the space of near-satisfying assignments and show that for our constructed Hamiltonians every combinatorial near-ground state induces a near-uniform distribution supported by this set. Standard arguments then are used to show that such distributions cannot be prepared by quantum circuits with depth o(log n). Since the clustering property is exhibited by many random structures, including proper coloring and maximum cut, we anticipate that our approach is extendable to these models as well.

Related papers

• LDPC stabilizer codes as gapped quantum phases: stability under graph-local perturbations [0.025206105035672277]
  We generalize the proof of stability of topological order, due to Bravyi, Hastings and Michalakis, to Hamiltonians corresponding to low-density parity check codes. We show that LDPC codes very generally define stable gapped quantum phases, even in the non-Euclidean setting.
  arXiv  Detail & Related papers  (2024-11-04T18:52:44Z)
• Unextendibility, uncompletability, and many-copy indistinguishable ensembles [77.34726150561087]
  We study unextendibility, uncompletability and analyze their connections to many-copy indistinguishable ensembles. We report a class of multipartite many-copy indistinguishable ensembles for which local indistinguishability property increases with decreasing mixedness.
  arXiv  Detail & Related papers  (2023-03-30T16:16:41Z)
• 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 Pseudoentanglement [4.3053817709507]
  Entanglement is a quantum resource, in some ways analogous to randomness in classical computation. We give a construction of pseudoentangled states with entanglement entropy arbitrarily close to $log n$ across every cut. We discuss applications of this result to Matrix Product State testing, entanglement distillation, and the complexity of the AdS/CFT correspondence.
  arXiv  Detail & Related papers  (2022-11-01T21:04: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)
• A construction of Combinatorial NLTS [22.539300644593936]
  NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] posits that there exist families of Hamiltonians with all low energy states of high complexity. Here, we prove a weaker version called the NLTS, where a quantum circuit lower bound is shown against states that violate a (small) constant fraction of local terms.
  arXiv  Detail & Related papers  (2022-06-06T16:55:34Z)
• Proofs of network quantum nonlocality aided by machine learning [68.8204255655161]
  We show that the family of quantum triangle distributions of [DOI40103/PhysRevLett.123.140] did not admit triangle-local models in a larger range than the original proof. We produce a large collection of network Bell inequalities for the triangle scenario with binary outcomes, which are of independent interest.
  arXiv  Detail & Related papers  (2022-03-30T18:00:00Z)
• 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)
• Geometry of Banach spaces: a new route towards Position Based Cryptography [65.51757376525798]
  We study Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. We show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol.
  arXiv  Detail & Related papers  (2021-03-30T13:55:11Z)
• Models of zero-range interaction for the bosonic trimer at unitarity [91.3755431537592]
  We present the construction of quantum Hamiltonians for a three-body system consisting of identical bosons mutually coupled by a two-body interaction of zero range. For a large part of the presentation, infinite scattering length will be considered.
  arXiv  Detail & Related papers  (2020-06-03T17:54:43Z)
• A new approach to the construction of Schur-Weyl states [0.0]
  The Schur-Weyl states belong to a special class of states with a symmetry described by two Young and Weyl tableaux. We present a new method of Schur-Weyl states construction in a spin chain system representation.
  arXiv  Detail & Related papers  (2020-04-30T14:10:14Z)

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.