1
$\begingroup$

$\text{PreciseBQP}$ is defined as $\text{BQP}$ with inverse exponentially close completeness and soundness bounds (for a better definition, see Section 3.1 here, in the paper by Gharibian et al). Similarly, $\text{PreciseQMA}$ is $\text{QMA}$ with inverse exponentially close completeness and soundness gaps (for more details, see Remark 5 here, in the paper by Fefferman and Lin). It is known that \begin{equation} \text{PreciseBQP} = \text{PP}, \\ \text{PreciseQMA} = \text{PSPACE}. \end{equation}

For more details, see Figure 1 here (paper by Deshpande et al). However, it seems obvious to me that \begin{equation} \text{PreciseQMA} \subseteq \text{PreciseBQP}. \end{equation} This is because one can simply replace the quantum witness given by the prover by the maximally mixed state, similar to the trick in Theorem 3.6 here, in the Marriott. We take an inverse exponential hit in the completeness and soundness bounds, but since the completeness and soundness bounds are inverse exponentially close in $\text{PreciseBQP}$, to begin with, we do not care.

However, if this is true, then it implies $\text{PP} = \text{PSPACE}$.

What am I missing?

$\endgroup$
0
3
$\begingroup$

I guess a similar argument used

  • in $\big[$ Marriot, Watrous $\big] $ [1] to prove QMA$_{log}$ $\subseteq$ BQP

and

  • in $\big[$ Fefferman, Lin $\big]$ [2] to prove QMA$_{exp}$ $\subseteq$ PSPACE

does not carry over since for L $\in $ QMA$_{exp}$ = PreciseQMA you get

  • $ x \in $ L $ \implies \text{tr}[Q_x] \geq c $
  • $ x \notin $ L $ \implies \text{tr}[Q_x] \leq 2^m s $

for $ c - s = \frac{1}{exp} $ and so using the totally mixed state $2^{-m} \mathbb{I}_m $ you accept with probability $ \text{tr}[2^{-m} Q_x] $ but does not yield any meaningful bound.

Both papers essentially apply an amplification procedure before the argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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