content_image/379876.jpg
# Unfrustrated Qudit Chains and their Ground States 

Ramis Movassagh, 1, ∗ Edward Farhi, 2 Jeffrey Goldstone, 2 Daniel Nagaj, 3 Tobias J. Osborne, 4 and Peter W. Shor 5 

$^{1}$Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts, U.S.A 

$^{2}$Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts, U.S.A 

$^{5}$Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 

$^{3}$Research Center for Quantum Information, Institute of Physics, Slovak Academy of Sciences, Bratislava, Slovakia 

$^{4}$Institute for Advanced Study, Wissenschaftskolleg zu Berlin, Berlin, Germany 

(Dated: November 12, 2018) 

We investigate chains of d dimensional quantum spins (qudits) on a line with generic nearest neighbor interactions without translational invariance. We find the conditions under which these systems are not frustrated, i.e. when the ground states are also the common ground states of all the local terms in the Hamiltonians. The states of a quantum spin chain are naturally represented in the Matrix Product States (MPS) framework. Using imaginary time evolution in the MPS ansatz, we numerically investigate the range of parameters in which we expect the ground states to be highly entangled and find them hard to approximate using our MPS method. 

A system with local interactions is not frustrated , if the global ground state of the Hamiltonian H = ∑ k H$_{k}$ is also a ground state of all the local terms H$_{k}$ each of which involves only a few particles. Frustration in a classical or quantum system (e.g. a spin glass [1]) is often the reason why finding its ground state properties is hard. A locally constrained unfrustrated system could still have ground states that are hard to find (e.g., 3-SAT where one needs to test whether a Boolean formula, made up of 3-literal clauses, is satisfiable by an assignment of the Boolean variables [2]). 

We choose to investigate chains of d -dimensional quan- tum spins (qudits) with 2-local nearest-neighbor inter- actions. Our first result is an analytic derivation of the necessary and sufficient conditions for such quantum sys- tems to be unfrustrated. Second, we look at their ground state properties and find a range of parameters where we conjecture that these states are highly entangled and thus may be difficult to find computationally. We then cor- roborate this by a numerical investigation using a Matrix Product State (MPS) method. 

The Matrix Product State description of a quantum state has proved to be a very useful tool for the inves- tigation of one dimensional quantum spin chains [3–5]. A pure state of a system of N interacting d -dimensional quantum spins can be written in the computational basis as | Ψ 〉 = ∑ d i k =1 ψ i$_{1}$i$_{2}$...i N | i$_{1}$ 〉| i$_{2}$ 〉 . . . | i$_{N}$ 〉 with d N param- eters ψ { i } . For a one-dimensional chain the coefficients ψ { i } can be conveniently expressed in a Matrix Product 

PACS numbers: 

## I. INTRODUCTION 

State (MPS) form [6, 7], 

<img src='content_image/379876.jpg'>

providing a local description of the system in terms of matrices Γ i k , [ k $^{]}$. One arrives at this form using a series of Schmidt decompositions [8]. The required size of the matrices is related to the number χ of nonzero Schmidt coefficients required for a decomposition of the state into two subsystems. In general, χ needs to grow like d N/ 2 for the MPS to be exact. 

Is it possible to capture the essential physics of the sys- tem accurately enough with an efficient simulation with a much smaller χ ∼ poly ( N ) , spanning only a small part of the full Hilbert space of the system? In our case, the qudits are arranged on a 1D lattice and only have nearest- neighbor interactions. We could thus expect that a re- duced space might suffice for our needs. This concept is common for the various approaches proposed for efficient (tractable on a classical computer) numerical investiga- tion of quantum many body systems such as the Den- sity Matrix Renormalization Group [9], Matrix Product States [6], Tensor Product States [10] and projected en- tangled pair states (PEPSs) [11]. 

While the MPS formulation has been shown to work very well numerically for most one-dimensional particle systems, complexity theory issues seem to show there must be exceptions to this rule. Finding the ground-state energy of a one-dimensional qudit chain with d = 11 has been shown to be as hard as any problem in QMA [12, 13]. It is not believed that classical computers can efficiently solve problems in QMA. However, to our knowledge until now there have not been any concrete examples (except at phase transitions) for which MPS methods do not ap- pear to work reasonably well. This research was under- taken to try to discover natural examples of Hamiltonians for which MPS cannot efficiently find or approximate the 

