Understanding statement about bounds of vector in the context of a RSDF ≤ₘ WOPT proof

Question

I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2010 [1], which, roughly, states that there is a many-one reduction from the problem of Robust Semidefinite Feasability (RSDF) and the problem of Weak Optimization (WOPT), for some particular conditions.

I believe this context is not very important (and I will try to give every necessary definition below), as my problem is with a specific step of the proof, stating that

$$\lVert \hat c \rVert_2 \in O(m^{1/2} \Delta)$$

(with these symbols to be defined).

The authors state that this follows from a previously given equation and the Cauchy–Schwarz inequality, but I don't see how these connect, and would appreciate help understanding so.

Definitions:

• $\DeclareMathOperator\Tr{Tr}$(d1) $k, l \in \mathbb{Z}^+$
• (d2) $M = k+1$, $N = l(l-1)/2 + 1$
• (d3) $B_j$ are $l \times l$ real and symmetrical matrices, with $j=1, \dotsc, k$
• (d4) $A_j$ are $N \times N$ matrices, where the top-left corner is set to $B_j$, and the rest of the entries are set to $0$,
• (d5) $C$ is an $(MN) \times (MN)$ block-matrix, defined as follows: $$\begin{pmatrix} 0 & A_1 & \cdots & A_{m-1} \\ A_1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ A_{m-1} & 0 & \cdots & 0 \end{pmatrix}$$
• (d6) $\Delta = \sqrt{2 \sum_{i=1}^k {\lVert B_i \rVert_2}^2 }$
• (d7) $\{\sigma_j\}_j$ are the Hermitian generators of $\operatorname{SU}(MN)$ such that $\Tr(\sigma_j \sigma_k) = 2\delta_{jk}$
• (d8) $\hat c$ is an $MN$-entry vector, where each component is given by $\hat c_j = 1/2 \Tr(C\sigma_j)$
• (d9) $r\in \mathbb{R}^{MN}$ is a Bloch vector for $\mathbb{C}^M \otimes \mathbb{C}^N$ (I don't expect this to play a large role, except maybe for the properties I've written below)
• (d10) $m = M^2N^2 - 1$

Identities

The following identities/properties are known:

• (i1) $\lVert r \rVert_2 \leq \sqrt{2 (MN - 1) / MN}$ (though not every $r$ satisfying this property is a Bloch vector)
• (i2) $\{r \; \vert \; \lVert r \rVert_2 \leq \sqrt{2/MN(MN - 1)}\}$ is a valid set of Bloch vectors
• (i3) $\lVert C \rVert_2 \equiv \Delta$
• (i4) $\frac{1}{2} \sum_{i=1}^{M^2N^2 - 1} r_i \cdot \Tr(C \sigma_i) = \hat c^T r$

Problem

The authors state that [1, end of paragraph following eq. 8]:

Since $\Tr(\sigma_i \sigma_j) = 2\delta_{ij}$, it follows from [identity i4] and the C.-S. inequality that $\lVert \hat c \rVert_2 \in O(m^{1/2} \Delta)$.

I don't understand how to arrive at this conclusion.

Answer 1

$\def\Tr{\mathop{\text{Tr}}}$ Let $\langle \cdot, \cdot \rangle_F$ be the Frobenius inner product.

$C$ is symmetric and real, so $C^\dagger \equiv C$, then writing out $\lVert \hat c \rVert_2$, and with $(\Tr C\sigma_i)^2 \equiv \lvert \Tr C \sigma_i\rvert^2$:

$$ \lVert \hat c \rVert_2 = \sqrt{\frac{1}{2} \sum_{i=1}^{M^2N^2-1} (\Tr C\sigma_i)^2} = \sqrt{\frac{1}{2} \sum_{i=1}^{M^2N^2-1} {\langle C, \sigma_i \rangle_F}^2} \overset{\text{C.-S.}}{\leq} \sqrt{\sum_{i=1}^{M^2N^2-1} \lVert C \rVert^2 \lVert \sigma_i \rVert^2} = \lVert C \rVert \sqrt{\sum_{i=1}^{M^2N^2-1} \lVert \sigma_i \rVert^2} = \Delta \sqrt{\sum_{i=1}^{M^2N^2-1} \lVert \sigma_i \rVert^2} $$

Thus remains to prove that $\sqrt{\sum_{i=1}^{M^2N^2-1} \lVert \sigma_i \rVert^2} = O(m^{1/2})$:

$\sigma_i$ are unitary, so $\lVert \sigma_i \rVert = \sqrt{\langle \sigma_i , \sigma_i \rangle_F} = \sqrt{\sum_{jk} (\sigma_i^\dagger \sigma_i)_{jk}} = \sqrt{\sum_{jk} (\mathbb{I}_{MN})_{jk}} = \sqrt{MN}$.

Now, recalling that $m := M^2N^2 - 1$, one easily finds that $ \sqrt{\sum_i^{M^2N^2-1} \lVert \sigma_i \rVert^2} = (m^2 + m)^{1/4} = O(m^{1/2})$.