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


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

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

2 Answers 2


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

  • $\begingroup$ 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? $\endgroup$
    – BlackHat18
    Sep 11, 2020 at 14:08
  • $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Sep 11, 2020 at 15:28
  • $\begingroup$ Aren't you rather entirely convinced that this statement is not true without further constraints? $\endgroup$ Sep 12, 2020 at 18:56
  • $\begingroup$ @NorbertSchuch there’s always the possibility that I screwed up somewhere ;) $\endgroup$
    – DaftWullie
    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.


Your Answer

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

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