2016/05/31 by Johannes Bausch, Toby Cubitt, Maris Ozols · 2 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum many-body systems #cs.CC #msc:68Q10 #msc:68Q17 #msc:81V70 #quant-ph
paper · pdf · doi:10.1007/s00023-017-0609-7
published as Ann. Henri Poincaré (2017) 18(11), 3449-3513 · 69 pages
openalex created_date 2016/06/24 · arxiv created 2017/09/09 · openalex publication_date 2017/10/29 · arxiv updated 2017/11/15 · openalex updated_date 2026/07/28
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.