{'fraction_non_alphanumeric': 0.055227374052608115, 'fraction_numerical': 0.023851983950066876, 'mean_word_length': 3.5545685279187818, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Unfrustration Condition and Degeneracy of Qudits on Trees

We generalize the previous results of [1] by proving unfrustration condition and degeneracy of the ground states of qudits (d-dimensional spins) on a k-child tree with generic local interactions. We find that the dimension of the ground space grows doubly exponentially in the region where rk<=(d^2)/4 for k>1. Further, we extend the results in [1] by proving that there are no zero energy ground states when r>(d^2)/4 for k=1 implying that the effective Hamiltonian is invertible.


II. GENERIC INTERACTION
Consider k-child trees of d-dimensional quantum particles (qudits) with nearest neighbor interactions-at every vertex, k edges fan out to connect to k qudits as shown in Fig. 1. The Hamiltonian of the system, is 2−local; each H m,n , shown as edges in Fig. 1, acts non-trivially only on two neighboring qudits . Our goal is to find the necessary and sufficient conditions for the quantum system, with generic local interactions, to be unfrustrated. Namely, the conditions under which ground states of the Hamiltonian are also common ground states of all H m,n . By generic we mean randomly sampled from any measure that is absolutely continuous with respect to the Haar measure. In this context, our notion of generic means that no particular local projector has a positive probability of being sampled.
As discussed previously [1,10], the question of existence of a common ground state of all the local terms is equivalent to asking the same question for an effective Hamiltonian whose interaction terms are, with Π m,n projecting onto the excited states of each original interaction term H m,n . When this modified system is unfrustrated, its ground state energy is zero (all the terms are positive semi-definite). The unfrustrated ground state belongs to the intersection of the ground state subspaces of each H m,n and is annihilated by all the projector terms. We choose to focus on a class of Hamiltonians for which each is a rank-r projector acting on a d 2 -dimensional Hilbert space of two qudits, chosen by picking an orthonormal set of r random vectors without translational invariance. The set of r constraints of each local term can be seen as a d 2 × r matrix whose columns are the orthonormal vectors |v p m,n . This matrix is represented by a point on the Steifel manifold [11].

III. RECURSIVE INVESTIGATION OF UNFRUSTRATED GROUND STATES
We now find conditions governing the existence of zero energy ground states (from now on, called solutions in short). We do so by counting the number of solutions possible for a subset of the tree, and then adding another site and imposing the constraints given by the Hamiltonian.
Below we use the extension of matrix product states (MPS) representation [5,[12][13][14] to describe the state of the qudits on the tree (also known as tensor product states) [14,15]. The structure of every tensor (as in MPS) at a given n indicates the connection with the parent and the subscripts n−1 indicate connections with the k children of that parent. We denote the membership among the k-edges by putting the corresponding label (e.g., 1 ≤ l ≤ k) in parenthesis as can be seen in Fig. 1. The value of n in what follows increases as we work our way up from the leaves to the root.
For a given n we will focus on a subtree rooted at some node h on the (n + 1) st level of the tree; a distance (n + 1) from the leaves. We will solve for |ψ (h) αn+1 which represent all of the linearly independent unfrustrated solutions on the entire subtree rooted at h. We will assume inductively that we have enumerated all of the linearly independent solutions |ψ (j) αn on subtrees at the n th level for 1 ≤ j ≤ k (see Fig. 1).

By definition the values
give the coefficients of the expansion of |ψ in terms of the physical index i (h) n+1 and independent bases for each subtree. In order to solve for the unfrustration condition and the degeneracy of the ground states on the subtree rooted at h we must apply the constraints associated to the projectors between h and each of its children. For a given child l of h it follows from the unfrustration condition that |ψ Here |v p n (l) ,(n+1) (h) is a set of random orthonormal vectors drawn from the d 2 dimensional space spanned by |i n+1 . Clearly, the unfrustration condition implies that |ψ (h) αn+1 is annihilated by each one of the rank-1 projectors, Using n−1 ,α n−1 ,··· ,α n−1 ,α n−1 ,··· ,α and combining it with Eq. (4) we get the expression where we denote α n−1 and a missing quantity by an over that quantity. We now apply the projector and consider its kernel The set of vectors |v p n (l) ,(n+1) (h) |ψ with respect to variables α n−1 , and ∀α (1) n , · · · , α (l) n , · · · , α (k) n .
Note that in Eq. (11) the repeated indices i n are summed over. This shows that the unfrustration condition holds iff Eq. (11) holds for all 1 ≤ p ≤ r, and 1 ≤ l ≤ k.
These constraints may be rewritten as where, In Eq. (13) the dummy variables β have exactly the same ranges of value as n but take values independently. Comment: We reserve the notation α's for when the constraints on all the other edges have been satisfied too. The delta notation is to emphasize that the constraints must hold for any choice of α (1) n , · · · , α (l) n , · · · , α (k) n , i.e., for all other subtrees other than l.
The constraint matrix C p,l,α , also denoted simply by C, has dD k n columns since Now, if the matrix C has full rank with probability one and dD k n > rkD k n−1 D k−1 n for suitable values of r, k, d, then the kernel of C has dimension It follows that there are D n+1 linearly independent solutions Γ , and thus D n+1 linearly independent solu- αn+1 on the subtree rooted at h. In the appendix we prove that C is indeed full rank. Furthermore, by the same token, if we have that dD k n ≤ rkD k n−1 D k−1 n then there are no solutions |ψ (h) αn+1 on the subtree rooted at h implying that the Hamiltonian is frustrated. We proceed to analyze the recursion Eq. (14), determine the criteria for r, k and d that assure the existence of unfrustrated ground states, and investigate the asymptotic growth of the number of solutions.

IV. RECURSION ANALYSIS
Consider the recursion in Eq. (14) with the initial conditions D 0 = 1, D 1 = d. Recall that we start at the leaves of the tree, where each unrestricted qudit on a leaf lives in a d-dimensional Hilbert space. The value D 0 = 1 can be viewed as a place-holder in the recursion and represents a formal 1−dimensional space preceding the leaves. Now suppose the solutions have the form, for some γ n ∈ R. It follows from the recursion (15) that Thus, if we define γ n by the recursion it follows that D n = γ n D k n−1 ∀n. Provided that we have founds positive solutions up to the n th step, i.e., non-negative D 0 , D 1 , · · · , D n−1 , the value of D n becomes non-positive iff the value of γ n becomes non-positive.
The following expressions are equivalent: whose roots, taking the equality, are denoted by Note that the inequality (18) is satisfied exactly when γ n ∈ [x − , x + ]. In the above computation we are assuming that γ n is positive since a non-positive value of γ n indicates that there are no unfrustrated solutions on the chain with n (or more) sites. When rk > d 2 4 these roots are not real and it follows that γ n is a strictly decreasing sequence. We thus know that γ n must eventually become non-positive, or it must converge to a positive number. However, it is easy to see that if γ n converges to some positive number γ * then γ * must be a fixed point of (18) satisfying γ * 2 − dγ * + rk = 0, but this is impossible since the roots are not real. It follows that, in the case rk > d 2 4 there exists an N such that, for all n ≥ N there are no unfrustrated solutions on the n site chain (with probability 1).
On the other hand, if rk ≤ d 2 4 we note that if γ n ≥ x + we have that Since γ 0 = d ≥ x + , using Eq. (18), γ n is a decreasing sequence which is bounded below by x + . Therefore, γ n must converge to some γ ≥ x + , which implies that its limit γ must be a fixed point of γ * 2 − dγ * + rk = 0, hence It follows that, for rk ≤ d 2 4 , D n ≥ G n where G n is the solution to the recursion G n = x + G k n−1 with G 1 = d and implies a growing number of solutions. Furthermore, the recursion for G n and that D n converge in the sense that the respective recursion constants γ n and x + converge. In particular, Eq. (20) shows that, in the regime rk ≤ d 2 4 the dimension of the unfrustrated ground space grows doubly exponentially as long as k > 1.

V. PROOF OF FRUSTRATION FOR k = 1
We now prove the non-existence of unfrustrated ground states for the n-qudit Hamiltonian with generic local interactions on the line when r > d 2 4 . In [1] the unfrustration condition was proved; however, it was only conjectured that the kernel would be empty with probability one when r > d 2 4 . Naturally, the result below holds for sufficiently large n since when n is small the Hamiltonian may have zero eigenvalues.
The intuition for the (non-)existence of the zero energy ground states follows from the solution of the recursion relation in Eq. (14). It follows from sections II and III that the dimension of unfrustrated ground states is given by the solution of the recursion relation Eq. (14) as long as D n is non-negative. We also know from section III that r ≤ d 2 4 implies that D n ≥ 0 ∀n, and that r > d 2 4 implies D n ≤ 0 for some n. It is natural to conjecture that the Hamiltonian is frustrated in the regime r > d 2 4 for sufficiently large n. We define E n to be the dimension of the kernel of the Hamiltonian on the first n qudits, which we distinguish from D n . The latter being the solution to the recursion Eq. (14). Of course we still have E n = D n for sufficiently small n. In this section we prove that, when d 2 2 ≥ r > d 2 4 , D n0+1 ≤ 0 implies E n0+2 = 0; i.e., the chain becomes frustrated. Note that the restriction d 2 2 ≥ r may be used without loss of generality (WLOG) since non-existence of unfrustrated states when d 2 2 ≥ r > d 2 4 automatically implies non-existence of unfrustrated states when r > d 2 2 . We recall that Thus, we would like to start with this second condition and prove the desired result. We begin with a lemma which gives us the desired result, but uses a slightly stronger condition. Lemma 1. Assume that n 0 ∈ Z + is such that E n = D n > 0 for n ≤ n 0 − 1, E n0 > 0, and that En 0 Proof. For k = 1 the constraint matrix is C p,αn 0 −1 ;in 0 +1,αn 0 , which has rE n0−1 rows, and dE n0 columns by definition. It follows from the assumption that dE n0 ≤ rE n0−1 , so C has more rows than columns and one needs to prove linear independence of the columns in order to prove that the kernel is empty. Thus, we must prove that the statement in 0 +1,αn 0 y in 0 +1,αn 0 C p,αn 0 −1;in 0 +1,αn 0 = in 0 +1,αn 0 implies y in 0 +1,αn 0 = 0 ∀ i n0+1 , α n0 .
Following the reasoning in the Appendix, we know that (WLOG, and with probability 1) we may apply Lemma 2 to row reduce the matrix Γ in 0 ,[n0] αn 0 −1 ;αn 0 on the set of rows Note, in particular that |s| = E n0 , and for (i n0 , α n0−1 ) ∈ s we have i n0 ≤ by assumption. Thus we have satisfied the requirements of Lemma 2 and may assume WLOG that Γ in 0 ,[n0] αn 0 −1;αn 0 is row reduced on the rows corresponding to s.
It follows that, given α n0 , ∃(i n0 , α n0−1 ) ∈ s, such that Similarly, we know from the "geometrization theorem" of [16] that we only need to prove full rankness of columns of C p,αn 0 −1;in 0 +1,αn 0 for a specific choice of projectors. It will then hold with probability 1 for random projectors.
We will assign projectors as follows: Now, given Eq. (21) we will show Given (i n0+1 , α n0 ) we choose (i n0 , α n0−1 ) corresponding to α n0 in Eq. (24). We then choose p so that We know that such a p exists in the range p ∈ [1, ..., r] because we know i n0 ≤ En 0 En 0 −1 ≤ r d by assumption, so we have di n0 ≤ r. The existence of such a p now follows from Eq. (25).
Note, in Lemma 1 that, given E n0+1 = 0 it follows easily from the the definition of E n , that E n = 0 ∀ n ≥ n 0 + 1.
Now, as discussed earlier, we would like to be able to prove that E n0+1 = 0 using only the condition En 0 En 0 −1 ≤ r d . However, Lemma 1 uses the assumption En 0 En 0 −1 ≤ r d which is slightly stronger. We can work around this using the following strategy: instead of proving E n0+1 = 0, we use reasoning similar to that in Lemma 1 to show that E n0+1 is fairly small. The bound on E n0+1 will be sufficient to show that En 0 +1 En 0 ≤ r d (when d ≥ 8) and then we can apply Lemma 1 to show that E n0+2 = 0. This intuition is made precise in the following theorem.
2r < r d , then the Hamiltonian for qudits on the line with generic local interactions is frustrated for sufficiently large n with probability one.
Comment: r > d 2 4 and d ≥ 8 together imply d 2 2r < r d , so that this theorem is always valid when r > d 2 4 , and d ≥ 8. Proof. Assume that n 0 ∈ Z + is such that E n = D n > 0 for n ≤ n 0 , D n0 = E n0 > 0, and D n0+1 ≤ 0, so that There are now two cases. If we have that Dn 0 Dn 0 −1 ≤ r d , then we can apply Lemma 1 directly to show that E n0+1 = 0. This, in turn implies that E n = 0 for all n ≥ n 0 + 1 so that we have E n0+2 = 0, and we are done.
In the second case, we have Our goal now is to show that E n0+1 is small by showing that a large subset of the columns of C p,αn 0 −1;in 0 +1,αn 0 are linearly indepedent. We will accomplish this by following the general idea behind the proof of Lemma 1, except that the role of En 0 −1 will be replaced by En 0 En 0 −1 . As a result we will not be able to prove that C p,αn 0 −1;in 0 +1,αn 0 has full column rank, but we will select a subset F of the pairs (i n0+1 , α n0 ), and prove linear indepedence for the corresponding columns of C p,αn 0 −1 ;in 0 +1 ,αn 0 (that is, only for those columns whose labels are contained in F ).
We first recall the fact that we may, WLOG, use Lemma 2 to row reduce the matrix Γ in 0 ,[n0] αn 0 −1;αn 0 on the set s given by Eq. 23.
Note, in particular that |s| = E n0 . Further note that, for (i n0 , α n0−1 ) ∈ s, we have i n0 ≤ is a positive number less than 1.
The total number of columns of C p,αn 0 −1;in 0 +1,αn 0 is dE n0 . We have shown that at least |F | = dE n0 − dEn 0 −1 4 of those columns are linearly independent. Thus the dimension of the kernel of C p,αn 0 −1;in 0 +1,αn 0 is at most That is, we now have the bound E n0+1 ≤ dEn 0 −1 4 .

Now, we know that
En 0 En 0 −1 > r d ≥ 1, and it follows that Thus, So, where the final inequality follows by assumption. Applying Lemma 1 now gives E n0+2 = 0, and we are done.

VI. APPENDIX
We now prove that the constraint matrix C in Eq. (13) is generically full rank; i.e., with probability 1. The proof given here is a generalization of that given in [1] for qudit chains. Just as in that earlier proof, we use the "geometrization theorem" of [16] to prove full rankness by finding a single set of projectors, |v p n (l) ,(n+1) (h) , for which C is full rank. This will be sufficient to prove that C will be full rank with probability one if the projectors are picked at random.
For simplicity we will assume that k ≤ d 2 . It is not clear whether this is necessary for existence of unfrustrated ground states. However, if the tree with k ≤ d 2 is frustrated then a larger tree with the same parameters except k > d 2 will also be frustrated since it contains a subtree with k ≤ d 2 . We assume for simplicity that d is even. The example used to prove full rankness for k = 1 in [1] involves an inductive process by which certain entries of the Γ matrices can be found explicitly. To gain the additional flexibility needed to prove full-rankness of C for k > 1 we will introduce a new technique using the idea that we can, WLOG, take invertible linear combinations of the Γ i (l) n ,[n] α n ≤ d 2 , has rank s with probability 1. Proof. By the argument in the "geometrization theorem" of [16], it is sufficient to prove this statement for a specific choice of projectors |v p (n−1) (m) ,n (l) . We will choose projectors such that From Eq. (11) the constraint on Γ has the form (see Figure 1) It thus follows from our choice of projectors that Γ In order to prove that the constraint matrix C is full rank we need to prove that p,l,α n−1 , β (1) n , · · · , β (l) n , · · · , β (k) n .
We prove this by showing it for a specific choice of the projectors. We assign the projectors as follows: Thus, the projectors are orthogonal basis vectors on the d 2 dimensional space in the computational basis. Note that this assignment obeys the following threes properties: 1) For every projector we have n+1 . It follows from Eq. (35) that each projector has at most one non-zero entry. To prove that each projector has exactly one non-zero entry it remains to verify the third requirement. We must show that all vectors created this way are non-zero. This is true iff 2r d + 1 (l − 1) + 2p d ≤ d for all l and p. Since this expression is an increasing function of l and p, it is sufficient to show 2r In the case x ≥ 2 this gives In the case x < 2 This proves the third assertion. Now we may suppose that we have performed the Gaussian elimination described above where the set S is the set S ≡ {0, · · · , d 2 } × {0, · · · ., D n−1 } k . Note that |S| = d 2 D k n−1 ≤ γ n D k n−1 = D n as follows from the work in Section IV, and the fact that rk ≤ d 2 2 . This allows us to apply Lemma 2 and use Gaussian elimination. We will therefore assume that Γ's have the form described in (33) for all i (l) n ≤ d 2 . Now let us imagine that there are real numbers y p,l,α (1···k) n−1 ,β j =l n such that p,l,α Take p , l , γ (1···k) , τ (j =l) to be any fixed set of values for p, l, α (1···k) n−1 , β j =l n . We now prove that y p ,l ,γ (1···k) ,τ (j =l) = 0, thereby completing the proof that C has full row rank.
And so we are done.