Circuit lower bounds for low-energy states of quantum code Hamiltonians

Abstract

The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings, 2014 -- which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n). Such codes are known to exist and are not necessarily locally testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.

arXiv commentPrevious versions contain revisions to introduction and non-technical content. Prior to version 3, asymptotic constants were worse and the dependency in Theorem 1 was epsilon^{1/3}. Version 5 introduced the lower bound for linear-distance LDPC stabilizer codes which was not in previous versions as well as additional technical appendices

References in corpus (25)

• Fault-tolerant quantum computation by anyons
• A variational eigenvalue solver on a quantum processor
• Surface codes: Towards practical large-scale quantum computation
• Topological entanglement entropy
• Quantum Annealing in the Transverse Ising Model
• A Quantum Approximate Optimization Algorithm
• Measurement-based quantum computation with cluster states
• Improved Simulation of Stabilizer Circuits
• An Area Law for One Dimensional Quantum Systems
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Variational Quantum State Diagonalization
• Tradeoffs for reliable quantum information storage in 2D systems
• Quantum LDPC Codes with Almost Linear Minimum Distance
• Topological Order at Non-zero Temperature
• Quantum NP - A Survey
• Stochastic Error Cancellation in Analog Quantum Simulation
• Fiber Bundle Codes: Breaking the $N^{1/2}\mathrm{polylog}(N)$ Barrier for Quantum LDPC Codes
• An improved 1D area law for frustration-free systems
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• Bounds for Small-Error and Zero-Error Quantum Algorithms
• Towards local testability for quantum coding
• Quantum Codes from High-Dimensional Manifolds
• On the Complexity of Two Dimensional Commuting Local Hamiltonians

Cited by in corpus (5)

• NLTS Hamiltonians from good quantum codes
• Symmetry-enforced many-body separability transitions
• Exponential clustering of bipartite quantum entanglement at arbitrary temperatures
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• Combinatorial NLTS From the Overlap Gap Property