UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

The Complexity of Translationally Invariant Spin Chains with Low Local Dimension

Bausch, J; Cubitt, T; Ozols, M; (2017) The Complexity of Translationally Invariant Spin Chains with Low Local Dimension. Annales Henri Poincaré , 18 (11) pp. 3449-3513. 10.1007/s00023-017-0609-7. Green open access

[img]
Preview
Text
Bausch_Complexity_Translationally_Invariant.pdf - ["content_typename_Published version" not defined]

Download (5MB) | Preview

Abstract

We prove that estimating the ground state energy of a translationally invariant, nearest-neighbour Hamiltonian on a 1D spin chain is (Formula presented.)-complete, even for systems of low local dimension ((Formula presented.)). 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.

Type: Article
Title: The Complexity of Translationally Invariant Spin Chains with Low Local Dimension
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/s00023-017-0609-7
Publisher version: https://doi.org/10.1007/s00023-017-0609-7
Language: English
Additional information: Copyright © The Author(s) 2017. Open Access: This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/1501504
Downloads since deposit
41Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item