Quantum entanglement, sum of squares, and the log rank conjecture

Introduction

Entanglement is one of the more mysterious and subtle phenomena in quantum mechanics. The formal definition is below (Definition 1.2), but roughly speaking, a joint quantum state $\rho$ of two sub-systems $A$ and $B$ is entangled if a quantum measurement of one system can affect the other system in a way that cannot be captured using classical correlations. A non-entangled state is called separable. Entanglement has often been talked of as "spooky interaction at a distance" and is responsible for many of the more counter-intuitive features of quantum mechanics. It is also a crucial aspect of quantum algorithms that obtain speedups over the best known classical algorithms, and it may be necessary for such speedups [Vid03].

One of the indicators of the underlying complexity of entanglement is that even given the full description of a quantum state $\rho$ as a density matrix, there is no known efficient algorithm for determining whether $\rho$ is entangled or not. Indeed, the best known algorithms take time which is exponential in the dimension of the state (which itself is exponential in the number of underlying qubits). This is in contrast to the classical case, where there is an efficient algorithm for the analogous problem of finding whether a given probability distribution $\mu$ over a universe $A\times B$ is a product distribution which can be done by simply computing the rank of the PDF of $\mu$ when viewed as a matrix.

Given the inherently probabilistic and noisy setting of quantum computing, an arguably better motivated question is the robust version of distinguishing between the case that a state $\rho$ is separable, and the case that it is $\varepsilon$-far from being separable, in the sense that there exists some measurement $\mathcal{M}$ that accepts $\rho$ with probability $p$ but accepts every separable state with probability at most $p-\varepsilon$. This problem is known as the Quantum Separability Problem with parameter $\varepsilon$. Gharibian [Gha10], improving on Gurvits [Gur03], showed that this problem is NP hard when $\varepsilon$ is inversely polynomial in the dimension of the state. Harrow and Montanaro [HM13] showed that, assuming the Exponential Time Hypothesis, there is no $n^{o(\log n)}$ time algorithm for this problem for $\varepsilon$ which is a small constant.

A closely related problem, which is the one we focus on in this paper, is the Best Separable State (BSS) problem.Using the connection between optimization and separation oracles in convex programming, one can convert a sufficiently good algorithm for the search variant of one of these problems to the other. See [HM13, Sec. 4.2] for a thorough discussion of the relations between these and many other problems. In the BSS problem, the input is a measurement $\mathcal{M}$ on a two part system and two numbers $1\geqslant c>s\geqslant 0$ and the goal is to distinguish between the YES case that there is a separable state that $\mathcal{M}$ accepts with probability at least $c$ and the NO case that $\mathcal{M}$ accepts every separable state with probability at most $s$. In particular, certifying that a particular measurement $\mathcal{M}$ satisfies the NO case is extremely useful since it implies that $\mathcal{M}$ can serve as an entanglement witness [HHH96, LKCH00], in the sense that achieving acceptance probability with $\mathcal{M}$ larger than $s$ certifies the presence of entanglement in a state. Such entanglement witnesses are used to certify entanglement in experiments and systems such as candidate computing devices [Ved08], and so having an efficient way to certify that they are sound (do not accept separable states) can be extremely useful.

Analogous to the quantum separability problem, the BSS problem is NP hard when $c-s=1/poly(n)$ [BT09, Gur03] and Harrow and Montanaro [HM13, Corollary 13(i)] show that (assuming the ETH) there is no $n^{o(\log n)}$ time algorithm for $\textup{{BSS}}_{1,1/2}$. An outstanding open question is whether the [HM13] result is tight: whether there is a quasi-polynomial time algorithm for $\textup{{BSS}}_{c,s}$ for some constants $1\geqslant c>s\geqslant 0$. This question also has a quantum complexity interpretation. A measurement on a two part system can be thought of as a verifier (with hardwired input) that interacts with two provers. Requiring the state to be separable corresponds to stipulating that the two provers are not entangled. Thus it is not hard to see that an algorithm for $\textup{{BSS}}_{c,s}$ corresponds to an algorithm for deciding all languages in the complexity class $QMA(2)$ of two prover quantum Merlin Arthur systems with corresponding completeness and soundness parameters $c$ and $s$ respectively. In particular, a quasi-polynomial time algorithm for $\textup{{BSS}}_{0.99,0.5}$ would imply that $QMA(2)\subseteq EXP$, resolving a longstanding problem in quantum complexity.For more on information on this problem and its importance, see the presentations in the recent workshop http://qma2016.quics.umd.edu/ that was dedicated to it.

In 2004, Doherty, Parrilo and Spedalieri [DPS04] proposed an algorithm for the BSS problem based on the Sum of Squares semidefinite programming hierarchy [Par00, Las01]. It is not known whether this algorithm can solve the $\textup{{BSS}}_{c,s}$ problem (for constants $c>s$) in quasi-polynomial time. However Brandão, Christandl and Yard [BaCY11] showed that it runs in quasi-polynomial time when the measurement $\mathcal{M}$ is restricted to a special class of measurements known as one-way local operations and classical communications (1-LOCC). Brandão and Harrow [BH15] showed that similar performance for these types of measurements can be achieved by an algorithm based on searching on an appropriately defined $\varepsilon$-net.

The BSS problem is actually quite natural and well motivated from classical considerations. As we’ll see in Section 2 below, it turns out that at its core lies the following problem:

2 Our results

A quantum measurement operator is an $m\times m$ complex Hermitian matrix $\mathcal{M}$ such that $0\preceq\mathcal{M}\preceq I$. The probability that a measurement $\mathcal{M}$ accepts a state $\rho$ is $\operatorname{Tr}(\rho\mathcal{M})$.

To our knowledge, this algorithm is the first for this problem that beats the brute force bound of $2^{O(n)}$ time for general measurements.

Like the algorithms of [DPS04, BaCY11], our algorithm is based on the sum of squares SDP hierarchy, but we introduce new techniques for analyzing it that we believe are of independent interest. As we discuss in Section 8, it is a fascinating open question to explore whether our techniques can be quantitatively strengthened to yield faster algorithms and/or extended for other problems such as the $2$ to $4$ norm and small set expansion, that have been shown to be related to the BSS problem by [BBH+12] (albeit in a different regime of parameters than the one we deal with in this work). As we remark below, this question seems related to other longstanding open questions in computer science and in particular to the log rank conjecture in communication complexity [LS88].

We state our results for the case of perfect completeness for simplicity, but all of the proofs extend to the case of “near perfect completeness” where in the YES case we replace the condition $\operatorname{Tr}(\rho\mathcal{M})=1$ with the condition $\operatorname{Tr}(\rho\mathcal{M})=1-\tfrac{1}{n}$ (see Remark 4.3). It is an interesting open problem to find out whether our results can extend to the setting where in the YES case $\operatorname{Tr}(\rho\mathcal{M})=1-\varepsilon$ for some absolute constant $\varepsilon$. We conjecture that this is indeed the case.

While the natural setting for quantum information theory is the complex numbers, much of the power and interest already arises in the case of the real numbers, which is more natural for the sos algorithm (though it does have complex-valued generalization). For our purposes, there’s no difference between the real and the complex cases - we give a reduction from the complex case to the real case in Section B of the Appendix. Thus, from now on, we will focus solely on the case that all operators, subspaces, matrices are real.

Our techniques

Our algorithm follows a recent paradigm of constructing rounding algorithms for the sum of squares sdp by considering its solutions as "pseudo-distributions" [BKS16]. These can be thought of as capturing the uncertainty that a computationally bounded solver has about the optimal solution of the given problem, analogous to the way that probability distributions model uncertainty in the classical information-theoretic Bayesian setting.

Our algorithm works by combining the following observations:

Thus, even though in the sos setting there is no actual distribution $\mu$, and hence no actual matrix $A$, we can still use structural results on this "fake" (or "pseudo") matrix $A$ to obtain an actual rounding algorithm. We view this as a demonstration of the power of the "pseudo distribution" paradigm to help in the discovery of new algorithms, that might not seem as natural without placing them in this framework.

We now give a more detailed (yet still quite informal) overview of the proof. As mentioned above, we focus on the case that the $n^{2}\times n^{2}$ measurement matrix $\mathcal{M}$ is real (as opposed to complex) valued.

We start with the following simple observation:

At least at a "moral level", the following theorem shows that a $k$-deficient reweighting (for $k\ll n$) can be helpful to prove our main result:

Let $\mu$ be any distribution over rank one $n\times n$ matrices and $\varepsilon>0$. Then there exists an $\sqrt{n}\operatorname{poly}(1/\varepsilon)$-deficient reweighting $\mu^{\prime}$ of $\mu$ and a rank one matrix $L$ such that

One of the results of this paper is a proof of Theorem 2.3 (see Section 2.3). It turns out that this can be done using ideas from the works on the log rank conjecture.

2 From monochromatic rectangles to rank one reweightings

Let $A$ be any $N\times N$ matrix of rank at most $n$. Then there exists a subset $I\subseteq[N]$ with with $|I|\geqslant\exp(-\sqrt{n}\operatorname{poly}(1/\varepsilon))N$ and a rank one matrix $L$ such that

where $A_{I,I}$ is the submatrix corresponding to restricting the rows and columns of $A$ to the set $I$.

3 Overview of proof

Our inspiration is Lovett’s result [Lov14] which establishes a stronger conclusion for Boolean matrices. In particular, our proof follows Rothvoß’s proof [Rot14] of Lovett’s theorem, though the non-Boolean setting does generate some non-trivial complications. The $N\times N$ matrix $A$ satisfies that $A_{i,j}=\langle u_{i},u_{j}\rangle$. An equivalent way to phrase our goal is that we want to find a subset $I\subseteq[N]$ over the indices such that:

We will chose the set $I$ probabilistically and show that (i) and (ii) above hold in expectation. It is not hard to use standard concentration of measure bounds to then deduce the desired result but we omit these calculations from this informal overview.

4 Rectangle lemma for pseudo-distributions

Preliminaries

We use the following definitions related the sum of squares (sos) algorithm; see [BKS16] for a more in-depth treatment.

The Algorithm

We now describe our algorithm, and show its analysis. A crucial tool for the analysis is the following general structure theorem on distributions over rank one matrices:

Furthermore, we can find the reweighting polynomial $p=\mu^{\prime}/\mu$ in time $2^{O(k)}$ and $p$ has only rational coefficients in the monomial basis with numerators and denominators of magnitude at most $2^{O(k)}$.

Theorem 4.1 is proven in Section 5. Our algorithm uses it as follows:

As discussed in Section 2.1, the following theorem immediately implies our main result (Theorem 1.3):

Note that the proof would have gone through even if the pseudo-distribution $\mu$ did not satisfy the condition that $u{v}{}^{\mkern-4.0mu\intercal}\in\mathcal{W}$ but merely that $\lVert\Pi_{\mathcal{W}^{\perp}}u{v}{}^{\mkern-4.0mu\intercal}\rVert\ll\lVert u_{0}{v_{0}}{}^{\mkern-4.0mu\intercal}\rVert$ where $\Pi_{V}$ is the projector to a subspace $V$. The proof of Theorem 4.1 actually guarantees that $\lVert u_{0}{v_{0}}{}^{\mkern-4.0mu\intercal}\rVert\geqslant k/n$ which means that it suffices that $\lVert\Pi_{W}u{v}{}^{\mkern-4.0mu\intercal}\rVert^{2}\geqslant 1-k^{2}/n^{2}$ hence implying that the proof works for the near perfect completeness case, as mentioned in Remark 1.4.

Structure Theorem

Furthermore, we can find the reweighting polynomial $p=\mu^{\prime}/\mu$ in time $2^{O(k)}$ and $p$ has only rational coefficients in the monomial basis with numerators and denominators of magnitude at most $2^{O(k)}$.

Our techniques extend to show similar structure theorem for pseudo-distributions over rank $r>1$. For e.g., in Section C of the Appendix, we give a higher-rank version of the structure theorem.

The following more general version (see Section A for a proof) will be useful for the analysis of our algorithm from the previous section. We note that the previous theorem suffices for the symmetric analog of Algorithm 4.1.

Theorem 5.3 directly implies Theorem 4.1. Indeed, if we write $u=u_{0}+u^{\prime}$ and $v=v_{0}+v^{\prime}$ where $u^{\prime},v^{\prime}$ are mean zero random variables, then we see that

We present the proof of Theorem 5.3 which is similar to that of Theorem 5.1 in Section A of the Appendix.

The proof of Theorem 5.1 is based on the following general results about existence of low-degree SoS reweighting schemes. We prove these results in the following sections.

Next, we show that for pseudo-distribution of degree at least $O(d)$ over the $d$-dimensional unit ball have $O(d)$-degree reweightings such that the resulting distribution is concentrated around a single vector. This result is related to previous results on using high-degree sum-of-squares relaxations for optimizing general polynomials over the unit sphere [DW12]. However, the previously known bounds are not strong enough for our purposes.

Further, the reweighting polynomial $p=\mu^{\prime}/\mu$ can be found in time $2^{O(k)}$, has all coefficients upper bounded by $2^{O(k)}$ in the monomial basis, and satisfies $p(x)\leqslant k^{O(k)}\lVert x\rVert^{k}$. The result extends to pseudo-distributions $\mu$ of degree at least $d=k+2$, in which case, the reweighted pseudo-distribution $\mu^{\prime}$ is of degree $d-k.$

2 Proof of Structure Theorem

We now prove Theorem 5.1 using Lemmas 5.4, 5.5.

The key tool will be the following direct corollary of Lemma 5.5 that allows us to argue that we make progress in every iteration of the Algorithm.

For any subspace $S$, we write $\Pi_{S}$ for the associated projector matrix.

Our proof of the structure theorem is algorithmic and uses Corollary 5.6 repeatedly. We describe the procedure below and then analyze it.

Our main claim is that if the pseudo-distribution that we begin with has degree $d>O(1/\varepsilon^{2})\sqrt{n}\log^{C+1}{(n)}$ then the procedure above terminates pseudo-distribution $\mu^{\prime}$ of degree at least 2 as required. Let $\mu=\mu_{0},\mu_{1},\ldots,\mu_{T}$ be the sequence of pseudo-distributions constructed when applying the procedure above with the final pseudo-distribution being $\mu_{T}.$

Fixing scalar-valued random variables

In this section, we prove Lemma 5.4. We begin by restating it.

It is instructive to derive intuition from a conditioning version of the lemma above for actual probability distributions. Given a random variable $x$ with distribution $\mu$ that has standard deviation $1$ and is bounded in $[-n,n]$, we know that with probability at least $\Theta(\frac{\delta}{n^{2}})$ that $x^{2}\geqslant 1-\delta.$ As a result, the probability of at least one of $x\geqslant 1-\Theta(\delta)$ or $x\leqslant-(1-\Theta(\delta))$, say the former, is also at least $\Theta(\frac{\delta}{n^{2}}).$ Next, we partition $[1-\delta,n]$ into $O(\log{(n)})$ intervals with end points differing by a multiplicative factor of, say $1.1$. Then, from the above calculation, there’s an interval in this partition such that $x$ is contained in it with probability at least $\Theta(\frac{\delta}{n^{2}\log{(n)}}).$ Thus, if we condition on $x$ lying in the above chosen interval to obtain $\mu^{\prime}$, then $KL(\mu||\mu^{\prime})\leqslant O(\log{(n)}+\log{(1/\delta)}).$

Our plan is to roughly implement the above conditioning argument for pseudo-distributions. This demands that instead of conditioning, we use reweightings by low-degree SoS polynomials and that further, all our arguments hold for low-degree pseudo-distributions with degree roughly matching the KL-divergence bound above.

Moreover, the claim holds also for pseudo-distributions $\mu$ of degree at least $5k$.

Observe the three statements above are claims about (pseudo-)expectations of degree at most $4k+2$ polynomials under $\mu_{0}=\mu$. Specifically, the three conditions have the following equivalent form:

Using Markov’s inequality along with (6.2) yields:

Let $y=\frac{x^{2}}{m}-1.$ Then, we have:

Now, since $k>4+\frac{2d}{\varepsilon}$, $y\leqslant\varepsilon\frac{k-4}{2d}y\leqslant\varepsilon(1+y)^{\frac{k-4}{2d}}.$ And thus, $\frac{y^{2d}}{(1+y)^{k/2-2}}\leqslant\varepsilon^{2d}$ for every $y\geqslant 1+(1+\varepsilon)^{4}.$ Thus, the expression in (6.4) is upper bounded by $\varepsilon^{2d}\int_{y\geqslant 1}\frac{1}{(1+y)^{2}}\leqslant\varepsilon^{2d}.$ This shows that the second term in (6.1) is upper bounded by $\varepsilon^{2d}.$

It is important to note that even though our arguments in the proof above require higher degree polynomials ($>5k$) - such as when we apply Holder’s inequality - the statements themselves are about non-negativity of polynomials of degree at most $4k+2$. Thus, an application of Fact 3.2 shows that these non-negativity statements, when true, hold for any pseudo-distribution of degree $\geqslant 4k+3$. In particular, in situations as in the proof above, we do not have to be judicious in the use of the degree.

The statement is about a pseudo-distribution $\mu$ that is subjected to some constraints - we cannot now apply Fact 3.2 directly. So instead 1) we prove a claim about actual distributions that are unconstrained, i.e. over the reals 2) apply Fact 3.2 to obtain the same claim for pseudo-distributions 3) Show that the claim implies the conclusion of the lemma for constrained pseudo-distributions.

We then apply Lemma 6.3 to every 3-tuple $\mu_{i-1},\mu_{i},\mu_{i+1}$ for $1\leqslant i\leqslant r-1.$ If conclusion 3) from the statement of Lemma 6.3 does not hold, then, then in every consecutive triple of reweightings $\mu_{i-1},\mu_{i},\mu_{i+1}$ as above, at least one of the consecutive pairs has a multiplicative gap of $(1+\varepsilon)$ in the means of $x^{2}.$

Fixing vector-valued random variables

We show that distributions over the $d$-dimensional unit ball have $O(d)$-degree reweightings such that the resulting distribution is concentrated around a single vector. Furthermore, the proof of this result also extends to pseudo-distribution of degree at least $O(d)$.

Further, the reweighting polynomial $p=\mu^{\prime}/\mu$ can be found in time $2^{O(k)}$, has all coefficients upper bounded by $2^{O(k)}$ in the monomial basis, and satisfies $p(x)\leqslant k^{O(k)}\lVert x\rVert^{k}$. Moreover, the result extends to pseudo-distributions $\mu$ of degree at least $d=k+2$, in which case, the reweighted pseudo-distribution $\mu^{\prime}$ is of degree $d-k.$

On a high level, the proof goes as follows: The final reweighting is a combination of three reweightings. The first reweighting approximately fixes the scalar variable $\lVert x\rVert^{2}$ as in the previous section. The second reweighting ensures that a single direction captures the expected norm in the sense that for some unit vector $v$ the variable $\langle v,x\rangle^{2}$ has expectation close the expectation of $\lVert x\rVert^{2}$ (which also means that the second moment is close to rank-1 in trace norm). This step is the key innovation of this section. The final step is to fix the variable $\langle v,x\rangle$ such that its expectation is approximately fixed to at least the square root of the expectation of $\langle v,x\rangle^{2}$, which ensures that the norm of the expectation of $v$ is large.

Using the bound $c_{k+1}\geqslant(1-\varepsilon)c_{k}$ and the fact that the variable $\lVert x\rVert^{2}$ is approximately fixed, it follows that

A standard Markov-like inequality (see for example [BKS15, Lemma 5.3]) shows that the following event over random unit vectors $v$ has probability at least $k^{-O(k)}$ (note that this probability is w.r.t. the distribution of the random variable $v$, which is an actual distribution),

Any unit vector that satisfies the above conditions yields a reweighting polynomial $p(x)\propto\langle v,x\rangle^{2k}$ that satisfies the conclusion of the theorem for $\varepsilon<\delta/10.$ ∎

Conclusions and further directions

Another interesting question is the following:

We do not know of a way to use a positive answer for Question 8.2 for an improved bound on the log rank conjecture, but (an appropriate sos-friendly version of) it does imply an improved algorithm for the problem of “$2$ vs $4$ provers QMA” where, in the completeness case (i.e., when the state $\rho$ is accepted by the measurement $\mathcal{M}$), there’s a quantum proof given by a 4-partite separable state (i.e, four non-entangled provers can certify that $\rho$ is accepted by $\mathcal{M}$) that the polynomial time quantum verifier accepts and in the soundness case (i.e, when $\textup{tr}(\mathcal{M}\rho)<1/3$), the verifier rejects any proof by four provers that can be split into two disjoint sets so that any shared entangled state is only between provers in the same set.

Acknowledgement

We thank the anonymous reviewers for suggestions on improved presentation of the paper. We thank Vijay Bhattiprolu, Bill Fefferman, Cedric Lin, Anand Natarajan for pointing out typos and inaccuracies in a previous version of the paper and many illuminating comments. We thank Madhur Tulsiani for pointing out bugs in previous versions of the paper and several suggestions for improved presentation.

References

Appendix A Proof of Theorem 5.3

In the first step, for each $1\leqslant i\leqslant 2$, we do the following:

We now track the potential function $\lVert m_{1}\rVert^{2}\lVert m_{2}\rVert^{2}.$ In any step, the second reweighting above implies that under any reweighting $\lVert m_{i}\rVert$ doesn’t decrease by a factor of more than $1-\varepsilon/10$. The first reweighting yields that at least one of $\lVert m_{1}\rVert^{2}$ or $\lVert m_{2}\rVert^{2}$ increases by a factor of $(1+\varepsilon/2)$. In effect, after each reweighting, the potential rises by a multiplicative $(1+\Theta(\varepsilon))$. Since $\lVert m_{1}\rVert^{2}\lVert m_{2}\rVert^{2}\leqslant 1$ and at least $\Theta(1/n)$ after the first step, the number of steps in the reweighting is upper bounded by $O(\log{(n)}/\varepsilon)$ giving the result. ∎

Appendix B Reduction Between Real and Complex Best Separable State Problems

Soundness: If there’s a $U\in\mathcal{Y}$ and $u_{0},v_{0}$ such that $\lVert u_{0}{v_{0}}{}^{\mkern-4.0mu\intercal}-U\rVert_{F}\leqslant\varepsilon\lVert u_{0}{v_{0}}{}^{\mkern-4.0mu\intercal}\rVert_{F}$, then there’s a $X\in\mathcal{W}$ and an $x_{0},y_{0}$ such that $\lVert x_{0}y_{0}^{*}-X\rVert_{F}\leqslant\varepsilon\lVert x_{0}y_{0}^{*}\rVert_{F}.$

It is easiest to describe the construction of the subspace $U$ from $\mathcal{W}$ in two steps. Let $\langle W^{j},X\rangle=0$ for $j\leqslant\operatorname{codim}(\mathcal{W})$ be the linear constraints that define $\mathcal{W}$. Write $X=A+iB$ for $i=\sqrt{-1}$ and $W^{j}=C^{j}+iD^{j}$. Then, $X\in\mathcal{W}$ iff for every $j\leqslant\operatorname{codim}(\mathcal{W})$,

We now claim that the subspace $\mathcal{Y}$ satisfies the requirements of the Lemma. First observe that if $Y\in\mathcal{Y}$, then by our construction, $(Y_{11}+Y_{22},Y_{21}-Y_{12})\in\mathcal{W}^{\prime}$ and consequently,

If $xy^{*}\in\mathcal{W}$ then, writing $x=u+iv$ and $y=u^{\prime}+iv^{\prime}$ and setting $A=u{u^{\prime}}{}^{\mkern-4.0mu\intercal}+v{v^{\prime}}{}^{\mkern-4.0mu\intercal}$ and $B=v{u^{\prime}}{}^{\mkern-4.0mu\intercal}-u{v^{\prime}}{}^{\mkern-4.0mu\intercal}$ yields that $(A,B)\in\mathcal{W}^{\prime}$ and thus, consequently, $Y=(u,v){(u^{\prime},v^{\prime})}{}^{\mkern-4.0mu\intercal}\in\mathcal{Y}.$

Soundness

Suppose $Y\in\mathcal{Y}$ and there’s $u,v$ such that $\lVert u{v}{}^{\mkern-4.0mu\intercal}-Y\rVert_{F}\leqslant\varepsilon\lVert u{v}{}^{\mkern-4.0mu\intercal}\rVert.$ Let $u_{1},u_{2}$ ($v_{1},v_{2}$) be the components of $u$ in the first and second column (row) blocks respectively. From (B.2), we know that $X=A+iB$ for $A=(Y_{11}+Y_{22})+i(Y_{21}-Y_{12})\in\mathcal{W}^{\prime}$. Let $U=u_{1}+iu_{2}$ and $V=v_{1}+iv_{2}$. Then, we can rewrite the above as:

Now, $\lVert(u_{1}+iu_{2})(v_{1}+iv_{2})^{*}\rVert^{2}=\lVert u_{1}\rVert^{2}+\lVert u_{2}\rVert^{2}+\lVert v_{1}\rVert^{2}+\lVert v_{2}\rVert^{2}.$

And by an application of triangle inequality,

Appendix C Higher Rank Structure Theorem

Let $\varepsilon>0$, let $\mu$ be a pseudo-distribution over $(u_{1},u_{2},\ldots,u_{r})$ such that $\sum_{i}\lVert u_{i}\rVert^{2}=1$. Let the degree of $\mu$ be at least $k+2$, where $k=\sqrt{rn}(\log n)^{C}/\varepsilon^{2}$ for an absolute constant $C\geqslant 1$. Then, $\mu$ has a degree-$k$ reweighting $\mu^{\prime}$ such that for each $1\leqslant j\leqslant r$