# Self reducibility of QCMA problems

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?

• Are QMA problems self-reproducible? Is that a harder question than the same for QCMA? – Mark S Dec 4 '19 at 4:16
• Could you explain what is "search version of the problems"? Do you mean output a witness of an instance in a NP language? – Yupan Liu Dec 6 '19 at 6:39
• Yes, I mean outputting a witness. – BlackHat18 Dec 6 '19 at 21:28

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

• 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? – BlackHat18 Dec 8 '19 at 6:57
• 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\}^{*}$ – BlackHat18 Dec 8 '19 at 7:15
• @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? – Yupan Liu Dec 8 '19 at 8:25