The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
arXiv:1605.01718 · doi:10.1007/s00023-017-0609-7
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.
arXiv comment69 pages
References in corpus (14)
- Undecidability of the Spectral Gap (short version)
- The power of quantum systems on a line
- Quantum Hamiltonian Complexity
- Power law violation of the area law in quantum spin chains
- Criticality without frustration for quantum spin-1 chains
- Hamiltonian Quantum Cellular Automata in 1D
- Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
- Solving condensed-matter ground-state problems by semidefinite relaxations
- Quantum Proofs
- No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems
- Space-Time Circuit-to-Hamiltonian Construction and Its Applications
- Size-Driven Quantum Phase Transitions
- Universal 2-local Hamiltonian Quantum Computing
- Hamiltonian quantum computer in one dimension
Cited by in corpus (19)
- 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
- Undecidability of the Spectral Gap (full version)
- The complexity of simulating local measurements on quantum systems
- A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
- Absence of barren plateaus and scaling of gradients in the energy optimization of isometric tensor network states
- Translationally invariant universal classical Hamiltonians
- Double-bracket quantum algorithms for quantum imaginary-time evolution
- Two-dimensional local Hamiltonian problem with area laws is QMA-complete
- Translationally-Invariant Universal Quantum Hamiltonians in 1D
- The 7 faces of quantum NP
- Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
- Autonomous Quantum Processing Unit: An Autonomous Thermal Computing Machine & its Physical Limitations
- A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems
- Predictive complexity of quantum subsystems