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.
Preview |
Text
Bausch_Complexity_Translationally_Invariant.pdf - Published Version 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 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: | https://discovery.ucl.ac.uk/id/eprint/1501504 |
Archive Staff Only
 |
View Item |
