The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension

Abstract

We prove that estimating the ground state energy of a translationally-invariant, nearest-neighbour Hamiltonian on a 1D spin chain is QMAEXP-complete, even for systems of low local dimension (roughly 40). This is an improvement over the best previously-known result by several orders of magnitude, and it shows that spin-glass-like frustration can occur in translationally-invariant quantum systems with a local dimension comparable to the smallest-known non-translationally-invariant systems with similar behaviour. While previous constructions of such systems rely on standard models of quantum computation, we construct a new model that is particularly well-suited for encoding quantum computation into the ground state of a translationally-invariant system. This allows us to shift the proof burden from optimizing the Hamiltonian encoding a standard computational model to proving universality of a simple model. Previous techniques for encoding quantum computation into the ground state of a local Hamiltonian allow only a linear sequence of gates, hence only a linear (or nearly linear) path in the graph of all computational states. We extend these techniques by allowing significantly more general paths, including branching and cycles, thus enabling a highly efficient encoding of our computational model. However, this requires more sophisticated techniques for analysing the spectrum of the resulting Hamiltonian. To address this, we introduce a framework of graphs with unitary edge labels. After relating our Hamiltonian to the Laplacian of such a unitary labelled graph, we analyse its spectrum by combining matrix analysis and spectral graph theory techniques.

69 pages

References in corpus (4)

• The power of quantum systems on a line
• Hamiltonian Quantum Cellular Automata in 1D
• Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
• Quantum Proofs

Cited by in corpus (17)

• Universal Quantum Hamiltonians
• Undecidability of the Spectral Gap in One Dimension
• Isometric tensor network optimization for extensive Hamiltonians is free of barren plateaus
• Uncomputability of Phase Diagrams
• Analysis and limitations of modified circuit-to-Hamiltonian constructions
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
• The complexity of simulating local measurements on quantum systems
• Absence of barren plateaus and scaling of gradients in the energy optimization of isometric tensor network states
• A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
• Translationally invariant universal classical Hamiltonians
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Translationally-Invariant Universal Quantum Hamiltonians in 1D
• Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
• The 7 faces of quantum NP
• Autonomous Quantum Processing Unit: An Autonomous Thermal Computing Machine & its Physical Limitations
• Predictive complexity of quantum subsystems
• A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems