# Question regarding soundness bound in QMA versus QCMA separation

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.

• Can you choose a more descriptive title? Sep 12, 2020 at 18:53
• I edited inequality to "soundness" bound. Sep 13, 2020 at 5:10

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$$.

• In that case, is there any other way to get the soundness bound for Theorem 4, or a similar bound that puts the problem in QMA? Sep 11, 2020 at 14:08
• That's a separate question! You could certainly replace the incorrect bound with a slightly looser one which is correct. I don't know what impact that'll have later. Sep 11, 2020 at 15:28
• Aren't you rather entirely convinced that this statement is not true without further constraints? Sep 12, 2020 at 18:56
• @NorbertSchuch there’s always the possibility that I screwed up somewhere ;) Sep 13, 2020 at 19:03

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.