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.