Question regarding soundness bound in QMA versus QCMA separation

Question

I am trying to understand the soundness bound reached in Theorem 4 of this paper, which deals with separating $QMA$ and $QCMA$ with respect to an in-place oracle. To state just the part I am confused with:

For some fixed integer $n$, let $N = 2^{{n}}$. Let $S \subseteq [N^{2}]$ be a set such that $|S| = N$. Let

$$A = \frac{1}{2^{n}}~~ \Big| \sum_{i \in S} \beta_{i} \Big|^{2}$$

and

$$B = \sum_{i \in Z_{even} \cap S} | \beta_{i} |^{2}.$$

where each $\beta_{i}$ is a complex number, $[n] = \{1, 2, \ldots, n \}$ and

$$\sum_{i \in [N^{2}]} | \beta_{i} |^{2} = 1.$$

$Z_{even}$ is the set of all even integers, where we know that $|Z_{even} \cap S| = \frac{1}{3} |S|$. I am trying to prove that

$$1 \geq \frac{\sqrt{3A} +(\sqrt{2} - 1)B}{\sqrt{2}}.$$

As per the paper, I am using the triangle and Cauchy Schwarz inequalities but I get stuck after a point. Here is my incomplete attempt at a solution:

$$A \leq \frac{1}{2^{n}}~ \Bigg(\sum_{i \in S} |\beta_{i}|\Bigg)^{2} \leq ~ \sum_{i \in S} |\beta_{i}|^{2} = B + \sum_{i \in Z_{odd} \cap S} | \beta_{i} |^{2}.$$

I am stuck after this.

Answer 1

I'm not entirely convinced that this statement is true without further constraints.

Let me set $$\beta_i=\left\{\begin{array}{cc} \sqrt\frac{3x}{2^n} & i\in Z_\text{even}\cap S \\ \sqrt\frac{3(1-x)}{2^{n+1}} & i\in Z_\text{odd}\cap S \\ 0 & \text{otherwise} \end{array}\right. $$ These must satisfy the inequality for all $0\leq x\leq 1$. This inequality states $$ \sqrt{2}\geq \sqrt{x}+\sqrt{2(1-x)}+(\sqrt{2}-1)x. $$ This is exactly satisfied for $x=0,1$, but for any $x$ in between, it doesn't work. For example, $x=1/2$ gives the value $\sqrt{2}+1/2$.

Answer 2

The correct inequality should be: $$ \sqrt{3A} \leq \sqrt{B} + \sqrt{2(1-B)} $$ The proof is the following: \begin{align*} \big| \sum_{i \in S} \beta_i \big| &\leq \big| \sum_{i \in S \cap \mathbb{Z}_{even}} \beta_i \big| + \big| \sum_{i \in S \cap \mathbb{Z}_{odd}} \beta_i \big| \\ & \leq \sqrt{|S \cap \mathbb{Z}_{even}|} \cdot \sqrt{\sum_{i \in S \cap \mathbb{Z}_{even}} |\beta_i|^2} + \sqrt{|S \cap \mathbb{Z}_{odd}|} \cdot \sqrt{\sum_{i \in S \cap \mathbb{Z}_{odd}} |\beta_i|^2} \\ & \leq \sqrt{|S \cap \mathbb{Z}_{even}|} \cdot \sqrt{\sum_{i \in S \cap \mathbb{Z}_{even}} |\beta_i|^2} + \sqrt{|S \cap \mathbb{Z}_{odd}|} \cdot \sqrt{\sum_{i \in S} |\beta_i|^2 - \sum_{i \in S \cap \mathbb{Z}_{even}} |\beta_i|^2} \\ & \leq \sqrt{\frac{|S|}{3}} \cdot \sqrt{B} + \sqrt{\frac{2|S|}{3}} \cdot \sqrt{1-B} \end{align*} where triangle inequality and the fact that $ ||x||_1 \leq \sqrt{n} ||x||_2 $ were used in the first two lines.

The inequality is tight (see previous answer for an example).

Coming back to the original paper, the probability bound in the 'soundness' argument should be: $$ \frac{1}{2}(p_{(i)} + p_{(ii)}) \leq \frac{1}{2}\cdot \Big( \frac{\big(\sqrt{p_{(ii)}} + \sqrt{2(1-p_{(ii)})}\big)^2}{3} + p_{(ii)} \Big) $$ with maximum value $ \frac{1}{2} (1 + \frac{1}{\sqrt{3}}) \approx 0,788 $ and the general argument still holds.