Hamiltonians whose low-energy states require \(\Omega(n)\) T gates

• Published in: arXiv.org 2024-06
• Main Authors: Coble, Nolan J, Coudron, Matthew, Nelson, Jon, Seyed Sajjad Nezhadi
• Format: Article
• Language: English
• Subjects: Energy; Gates
• ISSN: 2331-8422

The recent resolution of the NLTS Conjecture [ABN22] establishes a prerequisite to the Quantum PCP (QPCP) Conjecture through a novel use of newly-constructed QLDPC codes [LZ22]. Even with NLTS now solved, there remain many independent and unresolved prerequisites to the QPCP Conjecture, such as the NLSS Conjecture of [GL22]. In this work we focus on a specific and natural prerequisite to both NLSS and the QPCP Conjecture, namely, the existence of local Hamiltonians whose low-energy states all require \(\omega(\log n)\) T gates to prepare. In fact, we prove a stronger result which is not necessarily implied by either conjecture: we construct local Hamiltonians whose low-energy states require \(\Omega(n)\) T gates. We further show that our procedure can be applied to the NLTS Hamiltonians of [ABN22] to yield local Hamiltonians whose low-energy states require both \(\Omega(\log n)\)-depth and \(\Omega(n)\) T gates to prepare. In order to accomplish this we define a "pseudo-stabilizer" property of a state with respect to each local Hamiltonian term, and prove an additive local energy lower bound for each term at which the state is pseudo-stabilizer. By proving a relationship between the number of T gates preparing a state and the number of terms at which the state is pseudo-stabilizer, we are able to give a constant energy lower bound which applies to any state with T-count less than \(c \cdot n\) for some fixed positive constant \(c\). This result represents a significant improvement over [CCNN23] where we used a different technique to give an energy bound which only distinguishes between stabilizer states and states which require a non-zero number of T gates.