1
$\begingroup$

$\mathsf{PostQMA}$ can be defined as the following (see Morimae-Nishimura and Usher-Hoban-Browne):

A promise problem $\mathcal{L}=(\mathcal{L_{yes},L_{no}})$ is in $\mathsf{PostQMA(c,s)}$ if there exists a polynomially bounded function $m:\mathbb{Z}^+\rightarrow \mathbb{N}$ and a polynomial time quantum verifier $V$, which is a polynomial time uniformly generated family of quantum circuits $\{V_{x}\}_{x\in\{0,1\}^n}$ on $n+m$ qubits such that for every input $x$ and $(\langle \psi|\otimes\langle0|^{\otimes m}) V_x^{\dagger} (|0\rangle\langle0|\otimes I_{n+m-1}) V_x(|\psi\rangle\otimes |0\rangle^{\otimes m}) > 2^{-p(n)}$ for some polynomial $p$:

  • Completeness: if $x \in \mathcal{L}_{yes}$, there exists a witness $|\psi\rangle$ such that $$\frac{(\langle \psi|\otimes\langle0|^{\otimes m}) V_x^{\dagger} (|00\rangle\langle00|\otimes I_{n+m-2}) V_x(|\psi\rangle\otimes |0\rangle^{\otimes m})}{(\langle \psi|\otimes\langle0|^{\otimes m}) V_x^{\dagger} (|0\rangle\langle0|\otimes I_{n+m-1}) V_x(|\psi\rangle\otimes |0\rangle^{\otimes m})} \geq c.$$
  • Soundness: if $x \in \mathcal{L}_{no}$, for any witness $|\psi'\rangle$ such that $$\frac{(\langle \psi|\otimes\langle0|^{\otimes m}) V_x^{\dagger} (|00\rangle\langle00|\otimes I_{n+m-2}) V_x(|\psi\rangle\otimes |0\rangle^{\otimes m})}{(\langle \psi|\otimes\langle0|^{\otimes m}) V_x^{\dagger} (|0\rangle\langle0|\otimes I_{n+m-1}) V_x(|\psi\rangle\otimes |0\rangle^{\otimes m})} \leq s.$$

Namely, we do the postselection such that if the first output qubit is $0$, then we consider the second output qubit. Usually, $\mathsf{PostQMA}:=\mathsf{PostQMA(2/3,1/3)}$. As mentioned in Morimae-Nishimura, the error bound can be amplified from $(2/3,1/3)$ to $(1-2^{-r(n)},2^{-r(n)})$ for any polynomial $r$.


The naive approach is requiring polynomially many copies of the witness and using the standard Chernoff bound on indicators which indicate whether $x \in \mathcal{L}_{yes}$ or $\mathcal{L}_{no}$ and repeat such trials. As mentioned in Aaronson's paper on $\mathsf{PostBQP}$.


A little-advanced approach is requiring two copies of the witness. Using the proposition 2.9 in Kuperberg's paper, the $\mathsf{PostBQP}$ verifier $\mathcal{V}$ can be thought as two quantum polynomial-time algorithms run by Alice and Bob that report "yes" with probabikity $a$ and $b$ respectively. For some constant $c>1$, postselection guarantee the free-to-retry property: - $\mathcal{V}$ reports "yes" if $a > cb$; - $\mathcal{V}$ reports "no" if $a < cb$.

And Alice and Bob are free to retry if $(a,b)$ is not in either above ranges. Hence, we can do something similar to the Marriott-Watrous gap amplification (or the phase estimation variant), consider the following projections: $$\begin{aligned} \Pi_0 &= I_n\otimes |0\rangle\langle 0|^{\otimes m},\\ \Pi_1^A &= V_x^{\dagger} (|00\rangle\langle 00|\otimes I_{n+m-2}) V_x,\\ \Pi_1^B &= V_x^{\dagger} (|01\rangle\langle 01|\otimes I_{n+m-2}) V_x.\\ \end{aligned}$$ Invoking Marriott-Watrous procedure for $\Pi_0\Pi_1^A\Pi_0$ and $\Pi_0\Pi_1^B\Pi_0$ and using the free-to-retry property, then we can do the same thing with the standard Chernoff bound.


Therefore, the final question is that could we do the promise gap amplification using only one copy of the witness (i.e. strong error reduction) for $\mathsf{PostQMA}$?

Historically, such strong error reduction usually will have complexity-theoretic consequences, such as showing that $\mathsf{QMA}\subseteq \mathsf{PP}$ or $\mathsf{PreciseQMA}\subseteq \mathsf{PSPACE}$ (see space-efficient strong error reduction). So such strong error reduction for $\mathsf{PostQMA}$ might give us a direct proof for $\mathsf{PostQMA}\subseteq\mathsf{PSPACE}$.

Two facts might be helpful:

  • Morimae-Nishimura proved that $\mathsf{PostQMA}=\mathsf{PreciseQMA}$ where $\mathsf{PreciseQMA}$ is a $\mathsf{QMA}$-type class with exponentially small completeness-soundness gap. And $\mathsf{PreciseQMA}$ have such strong error reduction (but it needs exponential time) -- so even such strong error reduction for $\mathsf{PostQMA}$ exists, it might need exponential time to amplify.
  • Aaronson proved that $\mathsf{PostBQP}$ machine can do efficiently generated uniformly polynomial-size bounded-error quantum circuits, where the circuits can consist of arbitrary $1$- and $2$-qubit invertible linear transformations. It is not clear to me whether such Marriott-Watrous type error reduction exists for invertible gates complexity class or not.
$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.