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.


  • $\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$


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$


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.

  • $\begingroup$ You are using the physicist's convention where "generators of $\operatorname{SU}(MN)$" really means "elements of a[n implicit, fixed] basis of $\mathfrak{su}(MN)$", right? $\endgroup$
    – LSpice
    Commented Jan 6, 2022 at 22:44
  • 1
    $\begingroup$ @LSpice My lack of awareness means probably, yes. I think I have an answer but I still haven't used orthogonality (at least explicitly). Please see below. By the way of your edit: are thanks against the rules? $\endgroup$
    – MikeEVMM
    Commented Jan 6, 2022 at 22:50
  • $\begingroup$ I'd say that it's not universal, but that there is some consensus that one should not have "thanks" in one's posts. However, it is just a general "house style"; as with all edits, if you disagree with it, then feel free to restore it. $\endgroup$
    – LSpice
    Commented Jan 6, 2022 at 22:57
  • 1
    $\begingroup$ I'm fine with it :) It was just for future reference. (Also thanks for the LaTeX fixes.) $\endgroup$
    – MikeEVMM
    Commented Jan 6, 2022 at 22:58

1 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})$.

  • $\begingroup$ (Part of this answer was given by ddb in tilde.chat's #math channel, thanks to him.) $\endgroup$
    – MikeEVMM
    Commented Jan 6, 2022 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.