A construction of Combinatorial NLTS
arXiv:2206.02741 · doi:10.1063/5.0113731
Abstract
The 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 (with complexity measured by the quantum circuit depth preparing the state). Here, we prove a weaker version called the combinatorial NLTS, where a quantum circuit lower bound is shown against states that violate a (small) constant fraction of local terms. This generalizes the prior NLETS results (Eldar and Harrow [2017]; Nirkhe, Vazirani and Yuen [2018]). Our construction is obtained by combining tensor networks with expander codes (Sipser and Spielman [1996]). The Hamiltonian is the parent Hamiltonian of a perturbed tensor network, inspired by the `uncle Hamiltonian' of Fernandez-Gonzalez et. al. [2015]. Thus, we deviate from the quantum CSS code Hamiltonians considered in most prior works.
arXiv comment14 pages, 4 figures, added funding information and some discussion
References in corpus (15)
- A variational eigenvalue solver on a quantum processor
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence
- The computational complexity of PEPS
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Variational Quantum State Diagonalization
- Quantum LDPC Codes with Almost Linear Minimum Distance
- Balanced Product Quantum Codes
- Fiber Bundle Codes: Breaking the Barrier for Quantum LDPC Codes
- NLTS Hamiltonians from good quantum codes
- An area law for 2D frustration-free spin systems
- Frustration free gapless Hamiltonians for Matrix Product States
- Towards local testability for quantum coding
- Improved approximation algorithms for bounded-degree local Hamiltonians
- Graph codes and local systems