Combinatorial NLTS From the Overlap Gap Property

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.

19 pages, 2 figures, Quantum submission

References in corpus (13)

• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Clustering of solutions in the random satisfiability problem
• Algorithmic barriers from phase transitions
• Extremal Cuts of Sparse Random Graphs
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Suboptimality of local algorithms for a class of max-cut problems
• Local Hamiltonians Whose Ground States are Hard to Approximate
• NLTS Hamiltonians from good quantum codes
• Disordered Systems Insights on Computational Hardness
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• A construction of Combinatorial NLTS
• Limits of Short-Time Evolution of Local Hamiltonians
• Shattering in the Ising Pure $p$-Spin Model

Cited by in corpus (2)

• Quantum Glassiness From Efficient Learning
• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians