6

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?

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83
BlackHat18
  • 1,527
  • 9
  • 22

1 Answers1

6

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

Yupan Liu
  • 508
  • 2
  • 12