<p>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.</p>

<p><strong>Theorem</strong> 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.</p>

<p><strong>Proof</strong> Trivially from $QMA\subseteq PP$. $\square$</p>

<p><strong>Theorem</strong> If $\Delta_i^{BQP}=\Sigma_i^{BQP}$ then $BQPH=\Delta_i^{BQP}$.</p>

<p><strong>Proof</strong> Excercise for the reader.</p>

<p><strong>Theorem</strong> If $QMA=PP$ then $PH\subseteq QMA$ and indeed $PH^{PP}=QMA$.</p>

<p>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:</p>

<p><strong>Proof</strong> 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$</p>

<p>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].</p>

<p>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</p>

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

<p>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.</p>

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

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

<p>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.</p>

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

<p>[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).</p>

<p>[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.</p>

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

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

CC BY-SA 3.0
2017-10-10T11:52:07.170Z
First two theorems are pretty obvious, but third is interesting one!
rus9384
CC BY-SA 3.0
2017-10-10T12:02:39.483Z
@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.
Lieuwe Vinkhuijzen
CC BY-SA 3.0
2017-10-11T02:59:21.820Z
"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.
Huck Bennett
CC BY-SA 3.0
2017-10-11T03:47:19.697Z
@LieuweVinkhuijzen, maybe quantum analogue of symmetric hierarchy?
rus9384
CC BY-SA 3.0
2017-10-10T11:43:43.740Z
2017-10-11T13:21:42.853Z
2017-10-11T13:21:42.853Z
Lieuwe Vinkhuijzen
<p>First of all, I'm kinda surprised that I couldn't find any paper/article defining such hierarchy.</p>

<p>It can be defined as follows:</p>

<p>$\Delta_0^{\mathsf{BQP}}=\Sigma_0^{\mathsf{BQP}}=\Pi_0^{\mathsf{BQP}}=\Delta_1^{\mathsf{BQP}}\mathsf{=BQP}$</p>

<p>$\Delta_k^{\mathsf{BQP}}=\mathsf{BQP}^{\Sigma_{k-1}^{\mathsf{BQP}}}$</p>

<p>$\Sigma_k^{\mathsf{BQP}}=\mathsf{QMA}^{\Sigma_{k-1}^{\mathsf{BQP}}}$</p>

<p>$\Pi_k^{\mathsf{BQP}}=\mathsf{coQMA}^{\Sigma_{k-1}^{\mathsf{BQP}}}$</p>

<p>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?</p>

<cc.complexity-theory><quantum-computing><time-complexity>
Quantum polynomial hierarchy vs counting hierarchy
rus9384
# Quantum polynomial hierarchy vs counting hierarchy

(Asked by: username_0 on 2017-10-10)

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

It can be defined as follows:

$\Delta\_0^{\mathsf{BQP}}=\Sigma\_0^{\mathsf{BQP}}=\Pi\_0^{\mathsf{BQP}}=\Delta\_1^{\mathsf{BQP}}\mathsf{=BQP}$

$\Delta\_k^{\mathsf{BQP}}=\mathsf{BQP}^{\Sigma\_{k-1}^{\mathsf{BQP}}}$

$\Sigma\_k^{\mathsf{BQP}}=\mathsf{QMA}^{\Sigma\_{k-1}^{\mathsf{BQP}}}$

$\Pi\_k^{\mathsf{BQP}}=\mathsf{coQMA}^{\Sigma\_{k-1}^{\mathsf{BQP}}}$

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?

**Tags:** cc.complexity-theory, quantum-computing, time-complexity


---

## 1 answers

### Answer by username_1 on 2017-10-10. Score: 10

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.

> **Comments:**
> **username_0**: First two theorems are pretty obvious, but third is interesting one!  
> **username_1**: @username_0 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.  
> **username_2**: "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.  
> **username_0**: @LieuweVinkhuijzen, maybe quantum analogue of symmetric hierarchy?  

---

