Self reducibility is when search version of the problems in a language reduce to decision versions of the same problems. NP-complete problems are self reducible. Are QCMA complete problems self reducible?

  • $\begingroup$ Could you explain what is "search version of the problems"? Do you mean output a witness of an instance in a NP language? $\endgroup$
    – Yupan Liu
    Dec 6, 2019 at 6:39
  • $\begingroup$ Yes, I mean outputting a witness. $\endgroup$
    – BlackHat18
    Dec 6, 2019 at 21:28

1 Answer 1


self-reducible is a term regarding function class, such as $\mathsf{FNP}$, which is slightly different from what I am going to talk about, namely a witness-finding procedure for some quantum complexity classes.

For the question regarding whether we have a procedure of finding a witness of a $\mathsf{QCMA}$ instance or not. The short answer is not known. However, we did know that $\mathsf{PreciseQCMA}$ has such a witness-finding procedure! $\mathsf{PreciseQCMA}$ ($=\mathsf{NP^{PP}}$, see [MN17] and [GSSSY18]) is a variant of $\mathsf{QCMA}$ such that the gap between the acceptance probability of YES case and NO case is at least inverse-exponential.

Recall the witness-finding procedure for $\mathsf{NP}$, i.e. Claim 1.

Claim 1. There exists a $\sf P^{NP}$ protocol to find a witness of an instance in a $\sf NP$ language.

This $\mathsf{P^{NP}}$ protocol is as below:

  1. Given an instance $x$ in a language $\cal L\in \mathsf{NP}$, we can ask whether it is in YES case or not.
  2. If $x$ is indeed in YES case, then we can fix the first bit of the witness to be $w_1=0$, and write it as an instance $x\circ w_1$ in a new language $\cal L'$. Again, we can ask whether $x\circ w_1$ is in YES case or not.
  3. If $x\circ w_1$ is in YES case, then we know there exists a witness starting from $0$; otherwise, we know there exists a witness starting from $1$.
  4. Repeat Step 1 and Step 2 inductively, we can find a witness of an instance in $\cal L$ using $\mathrm{poly}(n)$ queries where $|x|=n$.

The language $\cal L'$ consists of all $x\circ w'$ where $w'$ is the prefix of a correct witness. Hence, if $\cal L' \subseteq \mathsf{C}$, then the procedure above is a $\mathsf{P^C}$ protocol. It is easy to see that $\cal L' \subseteq \mathsf{NP}$ since a $\mathsf{NP}$ verifier is powerful enough to reject a $x\circ w'$ instance if $x\circ w'\notin\cal L'$. We complete proof for the existence of a witness-finding procedure for $\sf NP$ with an explicit construction.

Now let us do the same thing for $\mathsf{QCMA}$. Note that there is a gap of acceptance probability between YES case and NO case, namely for a promise problem $(\cal L_{yes},\cal L_{no}) \in \sf QCMA$, we have $\cal L_{yes} \cup \cal L_{no} \subsetneq \{0,1\}^*$. Back to the witness-finding procedure of $\sf QCMA$, we obtain $(\cal L',\{0,1\}^* \setminus \cal L') \not\in \sf QCMA$ due to the gap issue just mentioned. Further details can be found in Remark 3.7 in [GSSSY18].

What about $\sf PreciseQCMA$? Fortunately, we can show Claim 2 below which is a lemma (proven in my paper with collaborators, see [GLK19]).

Claim 2. There exists a $\sf P^{PreciseQCMA}$ protocol to find a witness of an instance in a $\sf PreciseQCMA$ language.

Notice the acceptance probability of an instance in a language $\cal L$ in a $\sf QCMA$-type complexity class, such as $\sf QCMA$ and $\sf PreciseQCMA$, requires only inverse-exponential accuracy. The reason is that the total number of gates for preparing a witness and the verification circuit is at most ${\rm poly}(n)$. Also, the gap of acceptance probability between YES case and NO case is inverse-exponentially small, so it is not hard to conclude that $(\cal L', \{0,1\}^* \setminus \cal L') \in \sf PreciseQCMA$. It completes the proof of Claim 2.

Could we say anything more about complexity classes with a quantum witness? By the Solovay-Kitaev theorem, preparing any $n$-qubit quantum state with inverse-polynomial accuracy requires an exponentially long local gates sequence. Hence, a polynomial-time classical algorithm with the help of a $\sf QMA$-type class oracle cannot find a quantum witness naively.

Furthermore, the gap $c-s$ between YES case and NO case of such a $\sf QMA$-type class is also crucial. Otherwise, the oracle might not be able to decide whether $x\circ w'$ is in ${\sf QMA}(c,s)$ or not. With the help of quantum queries (such as superpositions) to an oracle, we might have a ${\sf BQP}^{{\sf QMA}(c,s)}$ protocol for finding a witness, but it requires non-trivial new ideas.

However, we still can say something now about ${\sf QMA}(c,s)$ with a very tiny $c-s$ gap. Let $\sf ExactQMA$ be a variant of ${\sf QMA}(c,s)$ with an inverse-doubly-exponential gap $c-s \geq 2^{-2^{{\rm poly}(n)}}$, also $\sf ExactQMA_1$ if $c=1$. Then by the same reasoning used in Claim 2, we obtain Claim 3:

Claim 3. There exists a $\sf ExactQMA_1$ protocol to find a witness of an instance in a $\sf ExactQMA_1$ language.

The protocol that we obtain essentially is a $\sf BQPSPACE^{ExactQMA_1}$ protocol, since an exponential-length local gates sequence (i.e. an exponential-length bit string) that acts on $n$ qubits is even enough to prepare any quantum state within inverse-doubly-exponential accuracy. Note that ${\sf ExactQMA_1} = {\sf PSPACE}$ [IKW10, FL16], ${\sf BQPSPACE} = {\sf PSPACE}$ [Wat99] and $\mathsf{PSPACE}^{\mathsf{PSPACE}}=\mathsf{PSPACE}$, we obtain ${\sf BQPSPACE^{ExactQMA_1}} \subseteq {\sf ExactQMA_1}$.

  • $\begingroup$ Can you explain more why the promise gap prevents $\cal{L'}$ to not belong in $QCMA$? Why does the same problem not appear in NP? $\endgroup$
    – BlackHat18
    Dec 8, 2019 at 6:57
  • $\begingroup$ Like, $NP$ can also be defined in terms of a promise problem $(L_{yes}, L_{no})$ such that the union of the yes and no instances is not $\{0, 1\}^{*}$ $\endgroup$
    – BlackHat18
    Dec 8, 2019 at 7:15
  • $\begingroup$ @BlackHat18 According to defintion of QCMA, $x\in\cal L_{yes}$ if ${\rm Pr}[V|x\rangle|0\rangle = |Acc\rangle] \geq 2/3$ and $x\in{\cal L}_{no}$ if ${\rm Pr}[V|x\rangle|0\rangle = |Acc\rangle] \leq 1/3$. What you can say about the condition of $x\not\in\cal L_{yes}$, i.e. $\bar{\cal L}_{yes}$? Comparing $\bar{\cal L}_{yes}$ with ${\cal L}_{no}$, what is the difference? Then do the same thing for NP, what is the difference between $\bar{\cal L}_{yes}$ and ${\cal L}_{no}$ now? $\endgroup$
    – Yupan Liu
    Dec 8, 2019 at 8:25

Your Answer

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

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