treme Quantum Information Theory, the U.S. Army Re- search Laboratory’s Army Research Office through grant number W911NF-09-1-0438, the National Science Foun- dation through grant number CCF-0829421. DN thanks Eddie Farhi’s group for their hospitality and gratefully 

[1] K. H. Fischer and J. A. Hertz, Spin Glasses (Cambridge University Press, Cambridge, 1993). 

[2] S. Cook, in Proceedings of the Third Annual ACM Sym- posium on Theory of Computing (ACM Press, New York, 1971), pp. 151–158. 

[3] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, Quantum Inf. Comput. 7, 401 (2007). 

[4] M. Fannes, B. Nachtergaele, and R. F.Werner, Commun. Math. Phys. 144, 443 (1992). 

[5] D. Nagaj, E. Farhi, J. Goldstone, P. Shor, and I. Sylvester, Phys. Rev. B 77, 214431 (2008). 

[6] F. Verstraete, V. Murg, and J. I. Cirac, Adv. Phys. 57, 143 (2008). 

[7] G. Vidal, Phys. Rev. Lett. 91, 147902 (2003). 

[8] M. A. Nielson and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2000). 

[9] S. R. White, Phys. Rev. Lett. 69, 2863 (1992). 

[10] Z. C. Gu, M. Levin, and X. G. Wen, Phys. Rev. B 78, 205116 (2008). 

[11] F. Verstraete, M. Wolf, D. Perez-Garcia, and J. I. Cirac, Phys. Rev. Lett. 96, 220601 (2006). 

[12] D. Aharonov, D. Gottesman, and J. Kempe, Commun. Math. Phys. 287, 41 (2009). 

[13] D. Nagaj, e-print arXiv:0808.2117v1 [quant-ph]. 

[14] S. Bravyi, e-print arXiv:quant-ph/0602108v1. 

[15] G. Vidal, Phys. Rev. Lett. 93, 040502 (2004). An alter- native yet equivalent notation for the MPS is given in [3]. 

[16] M. B. Hastings, Phys. Rev. Lett. 103, 050502 (2009). 

[17] C. Laumann, R. Moessner, A. Scardicchio, and S. L. Sondhi, Quantum Inf. Comput. 10, 0001 (2010). 

We now address the question of the rank of the matrix C in equation (9). This C , which gives the constraints on Γ [ n +1] depends on | v p n,n $_{+1}$〉 , and through Γ [ n ] on all the | v p k,k $_{+1}$〉 with k < n . We would like to say that for random | v 〉 and when s$_{k}$ < D$_{k}$ for random choices of the s$_{k}$ dimensional subspace, the rank of C is generically the maximum rank allowed, min( $^{rs$_{n}$}$− $_{1}$, ds$_{n}$ ) . This is not obviously true. In particular for the case s$_{k}$ = D$_{k}$ in the regime r ≤ d 2 4 , to which we restrict ourselves from now on, D$_{n}$ grows exponentially in n , while the number of parameters in the | v p k,k $_{+1}$〉 on which C depends only grows linearly. Thus C is far from a generic matrix of its size, but we now prove that its rank is indeed $^{rD$_{n}$}$− $_{1}$. The argument used by Laumann et al [17] to prove their ‘geometrization theorem’ also applies to our prob- 

## VI. APPENDIX 

acknowledges support from the Slovak Research and De- velopment Agency under the contract No. APVV LPP- 0430-09 and from the European project OP CE QUTE ITMS NFP 26240120009. 

lem. It shows that for a chain of N qudits with ran- dom | v p k,k $_{+1}$〉 , i.e. for a Hamiltonian H as in equations (2), (4) and (5) the number of zero-energy states, i.e. dim(ker( H )) , is with probability one (which is what we mean by generic) equal to its minimum value. The calculation in section II leading to the recursion rela- tion (11) and its solution, shows that in the regime r ≤ d $^{2}$/ 4 this minimum is ≥ D$_{N}$, since if the rank of the $^{rD$_{k}$}$− 1 × dD$_{k}$ matrix C is ever less than $^{rD$_{k}$}$− 1 we can choose s$_{k}$$_{+1}$ = D$_{k}$$_{+1}$ . Hence it is sufficient to find a single set of | v p k,k $_{+1}$〉 for which dim(ker( H )) = D$_{N}$ to prove that D$_{N}$ is the generic value, i.e. that greater val- ues occur with probability zero. This implies that the rank of each C is generically $^{rD$_{k}$}$− $_{1}$, since otherwise at the first k where C had smaller rank we could construct more than D$_{k}$$_{+1}$ solutions for a chain of length k + 1 . p 

We construct | v k,k $_{+1}$〉 with the property 〈 v p k,k $_{+1}$| i$_{k}$i$_{k}$$_{+1}$ 〉 = 0 unless i$_{k}$ ≤ d 2 and i$_{k}$$_{+1}$ > d $_{2}$. This can be done for r linearly independent | v $^{p}$〉 if r ≤ d 2 4 . We now assume d is even; the modifications for d odd are obvious. We proceed by induction on n . Assume that in each Γ i k , [ k ] α k$_{−}$ $_{1}$,α k with k ≤ n , α$_{k}$ runs from 1 to D$_{k}$ . From the definition of C (following equation 9) and the special choice of | v 〉 , C$_{pα}$ n$_{−}$ $_{1}$,i n $_{+1}$α n = 0 for i$_{n}$$_{+1}$ ≤ d 2 and so from equation (9) Γ i n $_{+1}$, [ n +1] α n ,α $^{n}$+1 is unconstrained for i$_{n}$$_{+1}$ ≤ d $_{2}$. This allows us to choose, for 1 ≤ α$_{n}$$_{+1}$ ≤ d $_{2}$D$_{n}$ , 

Γ i n $_{+1}$, [ n +1] α n ,α $^{n}$+1 = 1 when α$_{n}$$_{+1}$ = d $_{2}$( α$_{n}$ − 1) + i$_{n}$$_{+1}$ with 1 ≤ α$_{n}$ ≤ D$_{n}$ , 1 ≤ i$_{n}$$_{+1}$ ≤ d 2 Γ i n $_{+1}$, [ n +1] α n ,α $^{n}$+1 = 0 otherwise. As part of our induction, we assume that for 1 ≤ α$_{n}$ ≤ d $^{$_{2}$D$_{n}$}$− $_{1}$, Γ i n , [ n ] α n$_{−}$ $_{1}$,α n = 1 when α$_{n}$ = d $_{2}$( $^{α$_{n}$}$− 1 − 1) + i$_{n}$ with 1 ≤ $^{α$_{n}$}$− 1 ≤ $^{D$_{n}$}$− $_{1}$, 1 ≤ i$_{n}$ ≤ d 2 Γ i n , [ n ] α n$_{−}$ $_{1}$,α n = 0 otherwise. 

Now we can show that the rows of C$_{pα}$ n$_{−}$ $_{1}$,i n $_{+1}$α n are linearly independent. For if, ∑ p,α n$_{−}$ $_{1}$y$_{p,α}$ n$_{−}$ $_{1}$C$_{pα}$ n$_{−}$ $_{1}$,i n $_{+1}$α n = 0 for all i$_{n}$$_{+1}$, α$_{n}$ this is true in particular for all i$_{n}$$_{+1}$ > d/ 2 , α$_{n}$ ≤ d $^{$_{2}$D$_{n}$}$− $_{1}$, when it becomes ∑ $_{p}$y$_{pα}$ n$_{−}$ $_{1}$〈 v p n,n $_{+1}$| i$_{n}$i$_{n}$$_{+1}$ 〉 = 0 for all i$_{n}$ ≤ d $_{2}$, i$_{n}$$_{+1}$ > d $_{2}$, and $^{α$_{n}$}$− 1 ≤ $^{D$_{n}$}$− $_{1}$. Since the | v $^{p}$〉 are linearly independent, this is only true if y$_{pα}$ $^{n$_{−}$}$1 = 0 for all p , $^{α$_{n}$}$− $_{1}$. Hence the rank of C is $^{rD$_{n}$}$− 1 and α$_{n}$$_{+1}$ can take altogether dD$_{n}$ − $^{rD$_{n}$}$− 1 = D$_{n}$$_{+1}$ values, which is what we wanted to prove. 

