I'm trying to follow the proof of [Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2010](https://arxiv.org/abs/0810.4507) [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](https://arxiv.org/abs/quant-ph/0301152) 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.



Understanding statement about bounds of vector in the context of a RSDF ≤ₘ WOPT proof
$\def\Tr{\mathop{\text{Tr}}}$ Let $\langle \cdot, \cdot \rangle\_F$ be the [Frobenius inner product](https://en.wikipedia.org/wiki/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})$.


