First of all, I'm kinda surprised that I couldn't find any paper/article defining such hierarchy.

It can be defined as follows:





Is this whole hierarchy known to be contained in some finite level of counting hierarchy like $\mathsf{PH}$ (which is contained in the second level of counting hierarchy, $\mathsf{P^{PP}}$)? If not, are there some expectations on it?


I was quite surprised as well to not find this hierarchy in the literature, so I wrote my graduate thesis about it. It will be available online soon, at which point I will update this answer with a link to it. I was able to prove some interesting theorems about it.

Theorem For every $i$, $\Sigma_i^{\mathsf{BQP}}\subseteq C_i^\mathsf{P}$, where $C_i^\mathsf{P}$ is the $i$-th level of the counting hierarchy. So the whole hierarchy is contained in the counting hierarchy.

Proof Trivially from $QMA\subseteq PP$. $\square$

Theorem If $\Delta_i^{BQP}=\Sigma_i^{BQP}$ then $BQPH=\Delta_i^{BQP}$.

Proof Excercise for the reader.

Theorem If $QMA=PP$ then $PH\subseteq QMA$ and indeed $PH^{PP}=QMA$.

The first part of this theorem was originally by Vyalyi [4], but his proof is six pages of algebra, whereas new ideas that originated from thinking about your hierarchy allow me to get there in just a few lines:

Proof I prove a new theorem: $QMA\cap coQMA=P^{QMA\cap coQMA}$. This gives us $QMA=P^{QMA}=P^{PP}\supseteq PH$ by Toda. $\square$

For the new part, $PH^{PP}=QMA$, you will have to read my thesis. There's no obvious analogue of Toda's theorem. The reason is that the critical ingredient $QMA\subseteq BPP^{\oplus P}$ seems hard in the quantum case, whereas classically $NP\subseteq BPP^{\oplus P}$ follows trivially from Valiant-Vazirani, because here we don't have a way to "count" solutions. Even if you take $QCMA$ instead of $QMA$, there's the inconvenience that a QCMA protocol can behave arbitrarily on bad certificates to yes-instances. To see what I mean, start with [1].

There's also no obvious analogue of a Karp-Lipton collapse, or Kannan-type circuit lower bounds. Recall that in the classical case, we have

Theorem [3] For every $k\in\mathbb{N}$, there is a language in $\Sigma_4^{P}$ that requires circuits of size $\Omega(n^k)$.

The reason there's no(t yet) a theorem replacing every $P$ in this theorem with $BQP$ is that a critical ingredient in his proof is that he is able to (non-deterministically) guess a circuit and then evaluate that circuit, i.e. compute the circuit's output on an input. Sure, we can guess a (description of a) quantum circuit, but we can only say that we evaluate it if it is a bounded-error circuit, and verifying this is a $\# P$-Hard problem.

Scott Aaronson and Andy Drucker prove something along the lines of a "quantum PH", going only to the second level:

Theorem [2] If $NP\subset BQP_{/qpoly}$ then $\Pi_2^P\subseteq QMA^{PromiseQMA}$.

When I asked Scott Aaronson, he said that people had been thinking about this hierarchy for 15+ years, but nobody had published it because nobody had proved anything non-trivial about it. Here's to hoping you or I change that.

Bonus Theorem! If $QMA=coQMA$ then $PH\subseteq QMA$. Just for you, because you made it all the way to the end of a long answer.

[1] Aharonov, Dorit, et al. "The pursuit for uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings." arXiv preprint arXiv:0810.4840 (2008).

[2] Aaronson, Scott, and Andrew Drucker. "A full characterization of quantum advice." Proceedings of the forty-second ACM symposium on Theory of computing. ACM, 2010.

[3] Kannan, Ravi. "Circuit-size lower bounds and non-reducibility to sparse sets." Information and Control 55.1-3 (1982): 40-56.

[4] Vyalyi, Mikhail N. "Qma= pp implies that pp contains ph." In ECCCTR: Electronic Colloquium on Computational Complexity, technical reports. 2003.

  • $\begingroup$ First two theorems are pretty obvious, but third is interesting one! $\endgroup$ – rus9384 Oct 10 '17 at 11:52
  • $\begingroup$ @rus9384 Thank you, I'm quite proud of it myself. In the third theorem, you can replace "QMA" with "QCMA" or "QAM" and the resulting theorems will still be true. Interestingly, those theorems are proved using ideas from the quantum PH, even though it is not obvious what the relation is between QAM and the quantum PH. $\endgroup$ – Lieuwe Vinkhuijzen Oct 10 '17 at 12:02
  • 2
    $\begingroup$ "I was quite surprised as well to not find this hierarchy in the literature, so I wrote my graduate thesis about it" is perhaps my new favorite start to a SE answer. $\endgroup$ – Huck Bennett Oct 11 '17 at 2:59
  • $\begingroup$ @LieuweVinkhuijzen, maybe quantum analogue of symmetric hierarchy? $\endgroup$ – rus9384 Oct 11 '17 at 3:47

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.