Return to Question

I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2018 [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.

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.

I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2018 [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:

• $\def\Tr{\mathop{\text{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, \ldots, 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 $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.

Thanks in advance for your help.

I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2018 [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.

I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2018 [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:

• $\def\Tr{\mathop{\text{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, \ldots, 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 $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.

What I've tried

From (i1) and (i4), I can use the Cauchy-Schwarz equation to say that $$\lVert \hat c \rVert \geq \sqrt{\frac{MN}{2 (MN-1)}} \lvert \langle \hat c, r \rangle \rvert,$$ but this is a lower bound, not an upper bound. Also, it does not use the orthogonality of the $\sigma$s.

On the other hand, writing out $\lVert \hat c \rVert$ explicitly yields something that looks similar to the definition of $\Delta$, but, again, I don't understand where the C.-S. inequality or the orthogonality can be applied. At most one can write the following (again) lower bound:

$$ \lVert \hat c \rVert = \sqrt{\sum_{j=1}^{M^2N^2-1} (\Tr C \sigma_i )^2} \cdot \frac{1}{2} \geq \bigg\lvert \sum_{j=1}^{M^2N^2-1} \frac{1}{2} \Tr(C \sigma_j) \bigg\rvert $$

The most promising direction so far is taking the trace as a 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$. This means that

$$ \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} = \lVert C \rVert \sqrt{\sum_{i=1}^{M^2N^2-1} \lVert \sigma_i \rVert^2} $$

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

Thanks in advance for your help.

I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2018 [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:

• $\def\Tr{\mathop{\text{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, \ldots, 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 $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.

Thanks in advance for your help.