# Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds

Avantika Agarwal111David R. Cheriton School of Computer Science and Institute
for Quantum Computing, University of Waterloo, Canada. Email:
<EMAIL_ADDRESS> Sevag Gharibian222Department of Computer Science
and Institute for Photonic Quantum Systems (PhoQS), Paderborn University,
Germany. Email: {sevag.gharibian<EMAIL_ADDRESS>Venkata
Koppula333Department of Computer Science and Engineering, Indian Institute of
Technology Delhi, India. Email<EMAIL_ADDRESS>Dorian
Rudolph22footnotemark: 2

###### Abstract

The Polynomial-Time Hierarchy ($\mathsf{PH}$) is a staple of classical
complexity theory, with applications spanning randomized computation to
circuit lower bounds to “quantum advantage” analyses for near-term quantum
computers. Quantumly, however, despite the fact that at least _four_
definitions of quantum $\mathsf{PH}$ exist, it has been challenging to prove
analogues for these of even basic facts from $\mathsf{PH}$. This work studies
three quantum-verifier based generalizations of PH, two of which are from
[Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings
($\mathsf{QCPH}$) and quantum mixed states ($\mathsf{QPH}$) as proofs, and one
of which is new to this work, utilizing quantum pure states
($\mathsf{pureQPH}$) as proofs. We first resolve several open problems from
[GSSSY22], including a collapse theorem and a Karp-Lipton theorem for
$\mathsf{QCPH}$. Then, for our new class $\mathsf{pureQPH}$, we show one-sided
error reduction $\mathsf{pureQPH}$, as well as the first bounds relating these
quantum variants of PH, namely
$\mathsf{QCPH}\subseteq\mathsf{pureQPH}\subseteq\mathsf{EXP}^{\mathsf{PP}}$.

##  1 Introduction

Introduced by Stockmeyer in 1976 [Sto76], the Polynomial-Time Hierarchy (PH)
is one of the foundation stones of classical complexity theory. Intuitively,
the levels of $\mathsf{PH}$, denoted $\Sigma^{p}_{i}$ (respectively,
$\Pi^{p}_{i}$) for $i\geq 1$, yield progressively harder, yet natural, “steps
up” from $\mathsf{NP}$ (respectively, $\mathsf{coNP}$). Specifically, a
$\Sigma^{p}_{i}$ verifier is a deterministic poly-time Turing Machine $M$
which, given input $x\in{\left\\{0,1\right\\}}^{n}$, takes in $i$ proofs
$y_{i}\in{\left\\{0,1\right\\}}^{\operatorname{poly}(n)}$, and satisfies:

$\displaystyle\text{if $x$ is a YES input:}\qquad\exists y_{1}\forall
y_{2}\exists y_{3}\cdots Q_{i}y_{i}\text{ s.t. }M(x,y_{1},\ldots,y_{i})=1$ (1)
$\displaystyle\text{if $x$ is a NO input:}\qquad\forall y_{1}\exists
y_{2}\forall y_{3}\cdots\overline{Q_{i}}y_{i}\text{ s.t.
}M(x,y_{1},\ldots,y_{i})=0.$ (2)

Above, $Q_{i}$ is $\forall$ ($\exists$) if $i$ is even (odd). $\mathsf{PH}$
has played a prominent (and often surprising!) role in capturing the
complexity of various computing setups, including the power of BPP [Sip83,
Lau83], low-depth classical circuits [FSS84], counting classes [Tod91], and
even near-term quantum computers [BJS10, AA11, BFNV19].

In contrast, the role of _quantum_ analogues of $\mathsf{PH}$ in quantum
complexity theory remains embarrassingly unknown. So, where is the bottleneck?
_Defining_ “quantum PH” is not the problem — indeed, Yamakami [Yam02],
Lockhart and González-Guillén [JC17], and Gharibian, Santha, Sikora, Sundaram
and Yirka [GSSSY22] all gave different definitions of quantum PH. Instead, the
difficulty lies in proving even basic properties of quantum PH, which often
runs up against difficult phenomena lurking about open problems such as
$\exists\boldsymbol{\cdot}\mathsf{BPP}\stackrel{{\scriptstyle?}}{{=}}\mathsf{MA}$
and $\mathsf{QMA}\stackrel{{\scriptstyle?}}{{=}}\mathsf{QMA}(2)$.

In this work, we resolve open questions regarding some fundamental properties
of quantum PH. We focus on three definitions of quantum PH, chosen because
they naturally generalize444$\mathsf{QCMA}$ and $\mathsf{QMA}$ are quantum
generalizations of Merlin-Arthur ($\mathsf{MA}$), with a classical proof and
quantum verifier and a quantum proof and quantum verifier, respectively.
$\mathsf{QCMA}$ and $\mathsf{QMA}$. The first two definitions are from
[GSSSY22] (formal definitions in Section 2), and the third is new to this
work. The definitions all use a poly-time uniformly generated quantum verifier
$V$, and are given as follows (for brevity, here we only state the YES case
definitions):

  * •

$\mathsf{QCPH}$: $\exists y_{1}\forall y_{2}\exists y_{3}\cdots Q_{i}y_{i}$
s.t. $V(x,y_{1},\ldots,y_{i})$ outputs $1$ with probability $\geq 2/3$.

  * •

$\mathsf{QPH}$: $\exists\rho_{1}\forall\rho_{2}\exists\rho_{3}\cdots
Q_{i}\rho_{i}$ s.t. $V(x,\rho_{1},\ldots,\rho_{i})$ outputs $1$ with
probability $\geq 2/3$.

  * •

$\mathsf{pureQPH}$:
$\exists\lvert\psi_{1}\rangle\forall\lvert\psi_{2}\rangle\exists\lvert\psi_{3}\rangle\cdots
Q_{i}\lvert\psi_{i}\rangle$ s.t.
$V(x,\lvert\psi_{1}\rangle,\ldots,\lvert\psi_{i}\rangle)$ outputs $1$ with
probability $\geq 2/3$.

In words, $\mathsf{QCPH}$, $\mathsf{QPH}$, and $\mathsf{pureQPH}$ utilize
poly-size quantum verifiers taking in classical, mixed quantum, and pure
quantum proofs, respectively. It is immediate from the definitions that
$\mathsf{QCMA}\subseteq\mathsf{QCPH}$, $\mathsf{QMA}\subseteq\mathsf{QPH}$,
and $\mathsf{QMA}\subseteq\mathsf{pureQPH}$. Beyond this, not much is clear.
For example, a standard use of PH is via its collapse theorem — if for any
$i$, $\Sigma_{i}^{p}=\Pi_{i}^{p}$, then $\mathsf{PH}=\Sigma_{i}^{p}$. Do any
of $\mathsf{QCPH}$, $\mathsf{QPH}$, or $\mathsf{pureQPH}$ satisfy such a
collapse theorem? Does error reduction hold for $\mathsf{QPH}$ or
$\mathsf{pureQPH}$? What is the relationship between $\mathsf{QCPH}$,
$\mathsf{QPH}$, and $\mathsf{pureQPH}$? Note that standard convexity arguments
(as used for e.g. $\mathsf{QMA}$) cannot be used to argue
$\mathsf{QPH}=\mathsf{pureQPH}$, due to the presence of alternating
quantifiers (which make the verification non-convex in the proofs). Can one
recover celebrated results for these hierarchies analogous to the Karp-Lipton
[KL80] Theorem for PH?

##### Our results.

We prove the following properties of quantum PH.

_1\. Collapse Theorem for $\mathsf{QCPH}$._ We first resolve an open question
of [GSSSY22] by giving a collapse theorem for $\mathsf{QCPH}$.

######  Theorem 1.1.

If for any $k\geq 1$, $\mathsf{QC\Sigma}_{k}=\mathsf{QC\Pi}_{k}$, then
$\mathsf{QCPH}=\mathsf{QC\Sigma}_{k}$.

This is in contrast to $\mathsf{QPH}$, for which a collapse theorem is
believed difficult to show, as it would imply a subsequent
collapse555$\mathsf{QMA}(2)$ is QMA with two proofs in tensor product. Since
its introduction in 2001 by Kobayashi, Matsumoto, and Yamakami [KMY01], its
complexity remains stubbornly open. The current best bounds are
$\mathsf{QMA}\subseteq\mathsf{QMA}(2)\subseteq\mathsf{Q\Sigma}_{3}\subseteq\mathsf{NEXP}$,
where the second and third containments are from[GSSSY22].
$\mathsf{QMA}(2)\subseteq\mathsf{PSPACE}$. Theorem 1.1 immediately resolves a
second open question of [GSSSY22], recovering a
“precise”666Precise-$\mathsf{QCMA}$ is $\mathsf{QCMA}$ but with exponentially
small completeness-soundness gap. quantum version of the Karp-Lipton Theorem:

######  Corollary 1.2.

If
$\textup{Precise}\text{-}\mathsf{QCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$,
then $\mathsf{QCPH}=\mathsf{QC\Sigma}_{2}$.

Actually, we will do better in this work — we next leverage Theorem 1.1 and
other techniques to obtain a _genuine_ (i.e. non-precise) analogue of Karp-
Lipton.

_2\. Quantum-Classical Karp-Lipton Theorem for $\mathsf{QCPH}$._ The
celebrated Karp-Lipton theorem [KL80] states that if SAT can be solved by
polynomial-size circuits, then PH collapses to $\Sigma_{2}^{p}$. Here, we show
a quantum analogue for $\mathsf{QCPH}$:

######  Theorem 1.3.

(Karp-Lipton for $\mathsf{QCPH}$) If
$\mathsf{QCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$, then
$\mathsf{QCPH}=\mathsf{QC\Sigma}_{2}=\mathsf{QC\Pi}_{2}$.

Here, BQP${}_{/\textup{mpoly}}$ is $\mathsf{BQP}$ with poly-size classical
advice (Definition 2.11). In words, Theorem 1.3 says $\mathsf{QCMA}$ cannot be
solved by (even non-uniformly generated) poly-size quantum circuits, unless
$\mathsf{QCPH}$ collapses to its second level.

_3\. Error reduction for $\mathsf{pureQPH}$._ While error reduction for
$\mathsf{QCPH}$ follows from parallel repetition (due to its classical
proofs), achieving it for $\mathsf{pureQPH}$ is non-trivial for the same
reason it is non-trivial for $\mathsf{QMA}(2)$ — the tensor product structure
between proofs is not necessarily preserved when postselecting on measurements
across proof copies in the NO case. Here, we show _one-sided_ error reduction
for $\mathsf{pureQPH}$ (e.g. _exponentially_ small soundness):

######  Theorem 1.4.

For all $i>0$ and $c-s\geq 1/p(n)$ for some polynomial $p$,

  1. 1.

For even $i>0$:

    1. (a)

$\mathsf{pureQ\Sigma}_{i}(c,s)\subseteq\mathsf{pureQ\Sigma}^{\mathsf{SEP}}_{i}(1/np(n)^{2},1/e^{n})$

    2. (b)

$\mathsf{pureQ\Pi}_{i}(c,s)\subseteq\mathsf{pureQ\Pi}^{\mathsf{SEP}}_{i}(1-1/e^{n},1-1/np(n)^{2})$

  2. 2.

For odd $i>0$:

    1. (a)

$\mathsf{pureQ\Sigma}_{i}(c,s)\subseteq\mathsf{pureQ\Sigma}^{\mathsf{SEP}}_{i}(1-1/e^{n},1-1/np(n)^{2})$

    2. (b)

$\mathsf{pureQ\Pi}_{i}(c,s)\subseteq\mathsf{pureQ\Pi}^{\mathsf{SEP}}_{i}(1/np(n)^{2},1/e^{n})$

Above, $\mathsf{pureQ\Sigma}^{\mathsf{SEP}}_{i}$ and
$\mathsf{pureQ\Pi}^{\mathsf{SEP}}_{i}$ have the promise that in the YES case,
the verifier’s acceptance measurement is separable (see Section 4.2). We
remark the proof of this uses a new _asymmetric_ version of the Harrow-
Montanaro [HM13] Product Test, which may be of independent interest (see Lemma
4.1). The reason we are unable to recover exponentially small error
simultaneously for both completeness and soundness is because our approach
requires the final quantifier to be $\exists$.

_4\. Upper and lower bounds on $\mathsf{pureQPH}$._ Having introduced
$\mathsf{pureQPH}$ in this work, we next give bounds on its power.

######  Theorem 1.5.

$\mathsf{QCPH}\subseteq\mathsf{pureQPH}\subseteq\mathsf{EXP}^{\mathsf{PP}}$.

While the upper bound above is not difficult to show (Theorem 5.3; this may be
viewed as an “exponential analogue” of Toda’s theorem), the lower bound is
surprisingly subtle. The naive strategy of replacing each proof $y_{i}$ of
$\mathsf{QCPH}$ with pure state proof $\lvert\psi_{i}\rangle$, which is then
measured in the standard basis, does not work, as the measurement gives rise
to mixed states. Mixed states, in turn, are difficult to handle in
$\mathsf{QPH}$, as the latter is not a convex optimization due to alternating
quantifiers. We remark that while $\mathsf{QPH}\subseteq\mathsf{pureQPH}$
follows easily via purification of proofs, we do _not_ know how to show the
analogous lower bound $\mathsf{QCPH}\subseteq\mathsf{QPH}$ (our approach uses
our asymmetric product test, which requires pure states).

##### Related work.

Yamakami[Yam02] gave the first definition of a quantum PH, which takes quantum
inputs (in contrast, we use classical inputs). Gharibian and Kempe [GK12]
defined and obtained hardness of approximation results for
$\mathsf{QC\Sigma}_{2}$, obtaining the first hardness of approximation results
for a quantum complexity class. (See [BGK23] for a recent extension to QCMA-
hardness of approximation results.) Lockhart and González-Guillén[JC17]
defined a class $\mathsf{QCPH}^{\prime}$ similar to $\mathsf{QCPH}$, except
using existential and universal _operators_. Thus, in [JC17]
$\mathsf{QC\Sigma}^{\prime}_{1}=\exists\cdot\mathsf{BQP}$, which is not known
to equal $\mathsf{QCMA}$ (for the same reason
$\exists\cdot\mathsf{BPP}\stackrel{{\scriptstyle?}}{{=}}\mathsf{MA}$ remains
open). In exchange for not capturing $\mathsf{QCMA}$, however, the benefit of
$\mathsf{QCPH}^{\prime}$ is that its properties are easier to prove than
$\mathsf{QCPH}$. Gharibian, Santha, Sikora, Sundaram and Yirka [GSSSY22]
defined $\mathsf{QCPH}$ and $\mathsf{QPH}$, and showed weaker variants of the
Karp-Lipton theorem
($\textup{Precise}\text{-}\mathsf{QCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$
implies $\mathsf{QC\Sigma}_{2}=\mathsf{QC\Pi}_{2}$) and Toda’s theorem [Tod91]
($\mathsf{QCPH}\subseteq\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}$). They also
showed $\mathsf{QMA}(2)\subseteq\mathsf{Q\Sigma}_{3}\subseteq\mathsf{NEXP}$,
giving the first class sitting between $\mathsf{QMA}(2)$ and $\mathsf{NEXP}$,
and observed that
$\mathsf{Q\Sigma}_{2}=\mathsf{Q\Pi}_{2}=\textup{QRG}(1)\subseteq\mathsf{PSPACE}$
(due to work of Jain and Watrous [JW09]). Finally, Aaronson, Ingram and
Kretschmer [AIK22] showed that relative to a random oracle, $\mathsf{PP}$ is
not in the “$\mathsf{QMA}$ hierarchy”, i.e. in
$\mathsf{QMA}^{\mathsf{QMA}^{\iddots}}$. The relationship between this
$\mathsf{QMA}$ hierarchy and any of $\mathsf{QCPH}$, $\mathsf{QPH}$, or
$\mathsf{pureQPH}$ remains open.

The Karp-Lipton theorem has been studied in the setting of quantum advice.
Prior works by Aaronson and Drucker [AD14], and Aaronson, Cojocaru, Gheorghiu,
and Kashefi [ACGK17] studied the consequences of solving NP-complete problems
using polynomial-sized quantum circuits with polynomial quantum advice.

Finally, the Product Test was first introduced by Mintert, Kus̀ and
Buchleitner [MKB05], and rigorously analyzed and strikingly leveraged by
Harrow and Montanaro[HM13] to show $\mathsf{QMA}(k)=\mathsf{QMA}(2)$ for
polynomial $k$, as well as error reduction for $\mathsf{QMA}(2)$. (See also
Soleimanifar and Wright [SW22].)

##### Concurrent Work.

We mention two concurrent works on quantum variants of the polynomial
hierarchy. First, our collapse theorem for $\mathsf{QCPH}$ (Theorem 1.1 and
Corollary 1.2) was proven concurrently by Falor, Ge, and Natarajan [FGN23].
Second, we upper bound $\mathsf{QCPH}$ by showing that for all $k$,
$\mathsf{QC\Pi}_{k}\subseteq\mathsf{pureQ\Sigma}_{k}\subseteq\mathsf{pureQ\Sigma}_{i}\subseteq\mathsf{NEXP}^{\mathsf{NP}^{i-1}}$,
implying
$\mathsf{QCPH}\subseteq\mathsf{pureQPH}\subseteq\mathsf{EXP}^{\mathsf{PP}}$
(Theorem 1.5 and Theorem 5.3). Grewal and Yirka [GY23] show the stronger bound
$\mathsf{QCPH}\subseteq\mathsf{QPH}$, at the expense of the minor caveat that
their proof does not obtain level-wise containment for all $k$, but rather
requires constant factor blowup in level. Beyond this, our papers diverge. We
show a Quantum-Classical Karp-Lipton Theorem for QCPH and error reduction for
$\mathsf{pureQPH}$. Grewal and Yirka [GY23] define a new quantum polynomial
hierarchy called the _entangled quantum polynomial hierarchy_
($\mathsf{QEPH}$), which allows entanglement across alternatively quantified
quantum proofs. They show that $\mathsf{QEPH}$ collapses to its second level
(even with polynomially many proofs), and is equal to $\mathsf{QRG(1)}$, the
class of one round quantum-refereed games. They also define a generalization
of QCPH, denoted DistributionQCPH, in which proofs are not strings but
_distributions_ over strings. They show QCPH$=$DistributionQCPH.

##### Techniques.

We sketch our approach for each result mentioned above.

_1\. Collapse Theorem for $\mathsf{QCPH}$._ Collapse theorems for PH are shown
via inductive argument — by fixing an arbitrary proof for the first quantifier
of $\Sigma_{i}^{p}$, one obtains an instance of $\Pi_{i-1}^{p}$. Reference
[GSSSY22] noted this approach does not obviously work for $\mathsf{QCPH}$, as
fixing the first proof of $\mathsf{QC\Sigma}_{i}$ does _not_ necessarily yield
a valid $\mathsf{QC\Pi}_{i-1}$ instance (i.e. the latter might not satisfy the
desired promise gap). We bypass this obstacle by observing that even if most
choices for existentially quantified proofs are problematic, there always
exists _at least one_ “good” choice, for which the recursion works. Formally,
we are implicitly using a _promise_ version of NP which is
robustly777Formally, let $M$ be a deterministic machine with access to a
promise oracle O. We say $M$ is robust [Gol06] if, regardless of how any
invalid queries to $O$ (i.e. queries violating the promise gap of $O$) are
answered, $M$ returns the same answer. One can define “PromiseNP” for non-
deterministic $M$ with access to $O$ similarly: In the YES case, $M$ has at
least one robust accepting branch, and in the NO case, all branches of $M$ are
robust and rejecting. For clarity, we do not formally define and use PromiseNP
in this work, but the viewpoint sketched here is equivalent to our approach
for Theorem 1.1. defined relative to any promise oracle.

_2\. Quantum-Classical Karp-Lipton Theorem._ The classical Karp-Lipton theorem
crucially uses the search-to-decision reduction for SAT. Given a (non-uniform)
circuit family that can decide a SAT instance, we can use the circuit family
to find a witness for a SAT instance. However, this search-to-decision
reduction does not work in the quantum-classical setting since we are working
with promise problems instead of languages. As a result, we cannot replicate
the classical proof in the quantum-classical setting. Instead, we first
convert the $\mathsf{QCMA}$ problem (obtained by fixing the universally
quantified proof) to a UniqueQCMA ($\mathsf{UQCMA}$) problem. For this, we use
the quantum-classical analogue of Valiant-Vazirani’s isolation lemma [VV86]
given by Aharonov, Ben-Or, Brandão, and Sattath [ABBS22]. We then use a
single-query (quantum) search-to-decision reduction for $\mathsf{UQCMA}$ that
was presented in a recent work by Irani, Natarajan, Nirkhe, Rao and Yuen
[INNRY22].

More formally, let
$L=({L}_{\mathrm{yes}},{L}_{\mathrm{no}},{L}_{\mathrm{inv}})\in\mathsf{QC\Pi}_{2}$,
and let $V$ be the corresponding (quantum) verifier. Since the proofs are
classical, we assume $V$ has small error. We show that
$L\in\mathsf{QC\Sigma}_{2}$ by using the following (quantum) verifier
$V^{\prime}$: it takes as input an instance $x$, a quantum circuit $C$, a
string $y_{1}$. The verifier $V^{\prime}$ runs the circuit $C$ on input
$(x,y_{1})$ and receives a string $y_{2}$. It then accepts $x$ if $V$ accepts
$(x,y_{1},y_{2})$. If $x\in{L}_{\mathrm{no}}$, then there exists a $y_{1}$
such that for all $y_{2}$, $V(x,y_{1},y_{2})$ accepts with negligible
probability. Therefore, for any circuit $C$, there exists a $y_{1}$ such that
$V^{\prime}(x,C,y_{1})=V(x,y_{1},C(x,y_{1}))$ is $1$ with very low
probability.

For any $x\in{L}_{\mathrm{yes}}$, we have that for all $y_{1}$, the pair
$(x,y_{1})$ is a YES-instance of a $\mathsf{QCMA}$ problem. Using the [ABBS22]
isolation procedure, we obtain an instance $\phi_{(x,y_{1})}$ such that with
non-negligible probability $\phi_{(x,y_{1})}$ has a unique witness. Next,
using the assumption that
$\mathsf{QCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$, we get that there
exists a circuit $\tilde{C}$ that can decide $\phi_{(x,y_{1})}$. Finally,
using the $\mathsf{UQCMA}$ search-to-decision procedure of [INNRY22], we can
use $C$ to find the unique witness for $\phi_{(x,y_{1})}$. Let $C$ be the
circuit that, on input, $(x,y_{1})$, first performs the witness isolation from
[ABBS22], followed by the $\mathsf{UQCMA}$ search-to-decision reduction from
[INNRY22]. Putting these together, we get that there exists a circuit $C$
that, for any $y_{1}$, finds a $y_{2}$ with non-negligible probability such
that $V(x,y_{1},y_{2})=1$. Therefore, there exists $C$ such that for any
$y_{1}$, $V^{\prime}(x,C,y_{1})=1$ with non-negligible probability.

_3\. Error reduction for $\mathsf{pureQPH}$._ As with $\mathsf{QMA}(2)$, the
challenge with error reduction via parallel repetition for $\mathsf{pureQPH}$
is the following: Given proof
$\lvert\psi\rangle_{A_{1},B_{1}}\otimes\lvert\phi\rangle_{A_{2},B_{2}}$,
postselecting on a joint measurement outcome on registers
${\left\\{A_{1},B_{1}\right\\}}$ may entangle registers
${\left\\{A_{2},B_{2}\right\\}}$. To overcome this, we give an asymmetric
version of the Product Test [HM13], denoted APT. The APT takes in an
$n$-system state $\lvert\psi\rangle$ in register $A$, and (ideally) $m$ copies
of $\lvert\psi\rangle$ in register $B$. It picks a random subsystem $i$ of
$A$, as well as a random copy $j$ of $i$ in $B$, and applies the SWAP test
(Figure 1) between them. We prove (Lemma 4.1) that if this test passes with
high probability, then
$\lvert\psi\rangle_{A}\approx\lvert\psi_{1}\rangle\otimes\cdots\otimes\lvert\psi_{n}\rangle$
for some ${\left\\{\lvert\psi_{i}\rangle\right\\}}_{i=1}^{n}$, i.e.
$\lvert\psi\rangle_{A}$ was of tensor product form.

With the APT in hand, we can show error reduction for (e.g.)
$\mathsf{pureQ\Pi}_{i}$. Here, the aim of an honest $i$th (existentially
quantified) prover is to send many copies of proofs $1$ through $i-1$. With
probability $1/2$, the verifier runs the APT with register $A$ being proofs
$1$ to $i-1$ and register $B$ being all their copies bundled with the $i$th
proof, and with probability $1/2$, the verifier runs parallel repetition on
all copies of proofs bundled with the $i$th proof. This crucially leverages
the fact that the $i$th proof is existential in the YES case, and thus can be
assumed to be of this ideal form. In the NO case, however, the $i$th proof is
universally quantified — thus, we cannot assume anything about its structure,
which is why we do not get error reduction for the soundness parameter (in
this case).

_4\. Upper and lower bounds on $\mathsf{pureQPH}$._ We focus on the more
difficult direction, $\mathsf{QCPH}\subseteq\mathsf{pureQPH}$, for which we
actually show that for all even $k\geq 2$,
$\mathsf{QC\Pi}_{k}\subseteq\mathsf{pureQPH}_{k}$ (Lemma 5.2). When simulating
$\mathsf{QCPH}$, the challenge is again how to deal with universally
quantified proofs, denoted by index set $U\subseteq[k]$. Unlike existentially
quantified proofs, which can be assumed to be set honestly to some optimal
string $y_{i}$, for any index $j\in U$ the proof $\lvert\psi_{j}\rangle$ can
be any pure quantum state. This causes two problems: (1) Measuring
$\lvert\psi_{j}\rangle$ in the standard basis yields a _distribution_ $D_{j}$
over strings, and due to non-convexity of $\mathsf{pureQPH}$, it is not clear
if this can help a cheating prover succeed with higher probability that having
sent a string. (2) Conditioned on distribution $D_{j}$, what should the next,
existentially quantified, prover $j+1$ set its optimal proof/string to? We
overcome these obstacles as follows. The initial setup is similar to Theorem
1.4 — prover $k$ (which is existentially quantified in the YES case) send
copies of all previous proofs $1$ to $k-1$, and with probability $1/2$, we run
the APT. However, now with probability $1/2$, we measure _all_ proofs in the
standard basis. The key step is to immediately _accept_ if for any universally
quantified proof index $i\in U$, measuring proof $\lvert\psi_{i}\rangle$ does
_not_ match all of its copies bundled in proof $k$. In contrast, for
existentially quantified proofs, we _reject_ if a mismatch occurs. Finally,
assuming no mismatches occur, we simply run the original $\mathsf{QCPH}$
verifier on the corresponding strings obtained via measurement. Showing
correctness is subtle, and requires a careful analysis for both YES and NO
cases, since recall the location of universally quantified proofs changes
between cases.

##### Discussion and open questions.

Many questions remain open for $\mathsf{QCPH}$, $\mathsf{QPH}$, and
$\mathsf{pureQPH}$. Perhaps the most frustrating for $\mathsf{QCPH}$ is a lack
of a genuine Toda’s theorem — [GSSSY22] shows
$\mathsf{QCPH}\subseteq\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}$, but what one
really wants is containment in $\mathsf{P}^{\mathsf{PP}}$. Is this possible?
And if not, can one show an oracle separation between $\mathsf{QCPH}$ and
$\mathsf{P}^{\mathsf{PP}}$? Moving to $\mathsf{QPH}$, its role in this mess
remains rather murky. Is $\mathsf{pureQPH}\subseteq\mathsf{QPH}$ (recall the
converse direction follows via purification)? For this, our proof technique
for $\mathsf{QCPH}\subseteq\mathsf{pureQPH}$ appears not to apply, as it
requires pure states for the SWAP test. $\mathsf{QPH}$ _does_ have one
advantage over $\mathsf{pureQPH}$, however — while the third level of both
contains $\mathsf{QMA}(2)$, only $\mathsf{Q\Sigma}_{3}$ is known to be in
$\mathsf{NEXP}$ [GSSSY22], providing a class “between” $\mathsf{QMA}(2)$ and
$\mathsf{NEXP}$. Reference [GSSSY22]’s proof breaks down for
$\mathsf{pureQPH}$, as its semidefinite-programming approach requires _mixed_
state proofs888Briefly, in $\mathsf{NEXP}$ one can guess the first
existentially quantified proof of $\mathsf{Q\Sigma}_{3}$, leaving a
$\mathsf{Q\Pi}_{2}$ computation. Since we are using mixed states, via duality
theory one can rephrase this via an exponential-side SDP, which can be solved
in exponential time. Note this “convexification” does not seem to apply for
larger values of $k$.. Finally, for $\mathsf{pureQPH}$, can one show two-sided
error reduction? Is there a collapse theorem for $\mathsf{pureQPH}$? Can one
improve our bound $\mathsf{pureQPH}\subseteq\mathsf{EXP}^{\mathsf{PP}}$? As a
first step, is $\mathsf{pureQ\Sigma}_{2}\subseteq\mathsf{NEXP}$? If not, this
would suggest the combination of “unentanglement” across proofs and
alternating quantifiers yields a surprisingly powerful proof system, as it
trivially holds that $\mathsf{QMA}(2)\subseteq\mathsf{NEXP}$.

##### Organization.

Section 2 begins with notation and definitions. Section 3.1 and Section 3.2
give our collapse theorem and quantum Karp-Lipton theorem for $\mathsf{QCPH}$,
respectively. Section 4 shows error reduction for $\mathsf{pureQPH}$. Section
5 gives upper and lower bounds for $\mathsf{pureQPH}$.

##  2 Preliminaries

##### Notation.

Let $\operatorname{conv}(S)$ denote the convex hull of set $S$. Then, the set
of separable operators acting on
$\mathbb{C}^{d_{1}}\otimes\cdots\otimes\mathbb{C}^{d_{i}}$ is

$\displaystyle\operatorname{conv}\left(\lvert\psi_{1}\rangle\langle\psi_{1}\rvert\otimes\cdots\otimes\lvert\psi_{i}\rangle\langle\psi_{i}\rvert\mid\forall
j\in[i]\text{, }\lvert\psi_{j}\rangle\in\mathbb{C}^{d_{j}}\text{ is a unit
vector}\right).$ (3)

######  Definition 2.1 (Poly-time uniform family of quantum circuits).

A family of quantum circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ is said to be
uniformly generated in polynomial time if there exists a polynomially bounded
function $t:\mathbb{N}\mapsto\mathbb{N}$ and a deterministic Turing machine
$M$ acting as follows. For every $n$-bit input $x$, $M$ outputs in time $t(n)$
a description of a quantum circuit $V_{n}$ (consisting of $1$-and $2$-qubit
gates) that takes the all-zeros state as ancilla and outputs a single qubit.
We say $V_{n}$ _accepts_ (_rejects_) if measuring its output qubit in the
computational basis yields $1$ ($0$).

Throughout this paper, we study _promise problems_. A promise problem is a
pair $A=(A_{\textup{yes}},A_{\textup{no}})$ such that
$A_{\textup{yes}},A_{\textup{no}}\subseteq{\left\\{0,1\right\\}}^{\ast}$ and
$A_{\textup{yes}}\cap A_{\textup{no}}=\emptyset$, but $A_{\textup{yes}}\cup
A_{\textup{no}}={\left\\{0,1\right\\}}^{*}$ does not necessarily hold.

###  2.1 Quantum-Classical Polynomial Hierarchy (QCPH)

We first recall the quantum analogue of $\mathsf{PH}$ that generalizes
$\mathsf{QCMA}$, i.e. has classical proofs [GSSSY22].

######  Definition 2.2 ($\mathsf{QC\Sigma}_{i}$).

Let $A=(A_{\textup{yes}},A_{\textup{no}})$ be a promise problem. We say that
$A$ is in $\mathsf{QC\Sigma}_{i}(c,s)$ for poly-time computable functions
$c,s:\mathbb{N}\mapsto[0,1]$ if there exists a poly-bounded function
$p:\mathbb{N}\mapsto\mathbb{N}$ and a poly-time uniform family of quantum
circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ such that for every $n$-bit input $x$,
$V_{n}$ takes in classical proofs
${y_{1}}\in{\left\\{0,1\right\\}}^{p(n)},\ldots,{y_{i}}\in{\left\\{0,1\right\\}}^{p(n)}$
and outputs a single qubit, such that:

  * •

Completeness: $x\in A_{\textup{yes}}$ $\Rightarrow$ $\exists y_{1}\forall
y_{2}\ldots Q_{i}y_{i}$ s.t. $\operatorname{Prob}[V_{n}\text{ accepts
}(y_{1},\ldots,y_{i})]\geq c$.

  * •

Soundness: $x\in A_{\textup{no}}$ $\Rightarrow$ $\forall y_{1}\exists
y_{2}\ldots\overline{Q}_{i}y_{i}$ s.t. $\operatorname{Prob}[V_{n}\text{
accepts }(y_{1},\ldots,y_{i})]\leq s$.

Here, $Q_{i}$ equals $\exists$ when $m$ is odd and equals $\forall$ otherwise
and $\overline{Q}_{i}$ is the complementary quantifier to $Q_{i}$. Finally,
define

$\mathsf{QC\Sigma}_{i}:=\bigcup_{{c-s\in\Omega(1/\operatorname{poly}(n))}}\mathsf{QC\Sigma}_{i}(c,s).$
(4)

Comments: Note that the first level of this hierarchy corresponds to
$\mathsf{QCMA}$. The complement of the $i^{\mathrm{th}}$ level of the
hierarchy, $\mathsf{QC\Sigma}_{i}$, is the class $\mathsf{QC\Pi}_{i}$ defined
next.

######  Definition 2.3 ($\mathsf{QC\Pi}_{i}$).

Let $A=(A_{\textup{yes}},A_{\textup{no}})$ be a promise problem. We say that
$A\in\mathsf{QC\Pi}_{i}(c,s)$ for poly-time computable functions
$c,s:\mathbb{N}\mapsto[0,1]$ if there exists a polynomially bounded function
$p:\mathbb{N}\mapsto\mathbb{N}$ and a poly-time uniform family of quantum
circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ such that for every $n$-bit input $x$,
$V_{n}$ takes in classical proofs
${y_{1}}\in{\left\\{0,1\right\\}}^{p(n)},\ldots,{y_{i}}\in{\left\\{0,1\right\\}}^{p(n)}$
and outputs a single qubit, such that:

  * •

Completeness: $x\in A_{\textup{yes}}$ $\Rightarrow$ $\forall y_{1}\exists
y_{2}\ldots Q_{i}y_{i}$ s.t. $\operatorname{Prob}[V_{n}\text{ accepts
}(y_{1},\ldots,y_{i})]\geq c$.

  * •

Soundness: $x\in A_{\textup{no}}$ $\Rightarrow$ $\exists y_{1}\forall
y_{2}\ldots\overline{Q}_{i}y_{i}$ s.t. s.t. $\operatorname{Prob}[V_{n}\text{
accepts }(y_{1},\ldots,y_{i})]\leq s$.

Here, $Q_{i}$ equals $\forall$ when $m$ is odd and equals $\exists$ otherwise,
and $\overline{Q}_{i}$ is the complementary quantifier to $Q_{i}$. Finally,
define

$\mathsf{QC\Pi}_{i}:=\bigcup_{{c-s\in\Omega(1/\operatorname{poly}(n))}}\mathsf{QC\Pi}_{i}(c,s).$
(5)

Now the corresponding quantum-classical polynomial hierarchy is defined as
follows.

######  Definition 2.4 (Quantum-Classical Polynomial Hierarchy
($\mathsf{QCPH}$)).

$\mathsf{QCPH}=\bigcup_{m\in\mathbb{N}}\;\mathsf{QC\Sigma}_{i}=\bigcup_{m\in\mathbb{N}}\;\mathsf{QC\Pi}_{i}.$
(6)

###  2.2 (Mixed-State) Quantum Polynomial Hierarchy (QPH)

We next define the quantum hierarchy with _mixed state_ proofs, as in
[GSSSY22]. In contrast to $\mathsf{QCPH}$, this hierarchy generalizes
$\mathsf{QMA}$.

######  Definition 2.5 ($\mathsf{Q\Sigma}_{i}$).

A promise problem $A=(A_{\textup{yes}},A_{\textup{no}})$ is in
$\mathsf{Q\Sigma}_{i}(c,s)$ for poly-time computable functions
$c,s:\mathbb{N}\mapsto[0,1]$ if there exists a polynomially bounded function
$p:\mathbb{N}\mapsto\mathbb{N}$ and a poly-time uniform family of quantum
circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ such that for every $n$-bit input $x$,
$V_{n}$ takes $p(n)$-qubit density operators $\rho_{1},\ldots,\rho_{i}$ as
quantum proofs and outputs a single qubit, then:

  * •

Completeness: $x\in A_{\textup{yes}}$ $\Rightarrow$
$\exists\rho_{1}\forall\rho_{2}\ldots Q_{i}\rho_{i}$ s.t.
$\operatorname{Prob}[V_{n}\text{ accepts
}({\rho_{1}\otimes\rho_{2}\otimes\cdots\otimes\rho_{i}})]\geq c$.

  * •

Soundness: If $x\in A_{\textup{no}}$ $\Rightarrow$
$\forall\rho_{1}\exists\rho_{2}\ldots\overline{Q}_{i}\rho_{i}$,
$\operatorname{Prob}[V_{n}\text{ accepts
}({\rho_{1}\otimes\rho_{2}\otimes\cdots\otimes\rho_{i}})]\leq s$.

As before, $Q_{i}$ equals $\forall$ when $m$ is even and equals $\exists$
otherwise, and $\overline{Q}_{i}$ is the complementary quantifier to $Q_{i}$.
Define

$\mathsf{Q\Sigma}_{i}=\bigcup_{\begin{subarray}{c}c-s\in\Omega(1/\operatorname{poly}(n))\end{subarray}}\mathsf{Q\Sigma}_{i}(c,s).$
(7)

_Comments:_ (1) In contrast to the standard quantum circuit model, here we
allow _mixed_ states as inputs to $V_{n}$; this can be formally modelled via
the mixed state framework of [AKN98]. (2) Clearly,
$\mathsf{Q\Sigma}_{1}=\mathsf{QMA}$. (3) We recover the definition of
$\mathsf{QMA}(k)$ by ignoring all proofs $\rho_{i}$ proofs with $i$ even in
the definition of $\mathsf{Q\Sigma}_{2k}$.

######  Definition 2.6 ($\mathsf{Q\Pi}_{i}$).

A promise problem $A=(A_{\textup{yes}},A_{\textup{no}})$ is in
$\mathsf{Q\Pi}_{i}(c,s)$ for poly-time computable functions
$c,s:\mathbb{N}\mapsto[0,1]$ if there exists a polynomially bounded function
$p:\mathbb{N}\mapsto\mathbb{N}$ and a poly-time uniform family of quantum
circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ such that for every $n$-bit input $x$,
$V_{n}$ takes $p(n)$-qubit density operators $\rho_{1},\ldots,\rho_{i}$ as
quantum proofs and outputs a single qubit, then:

  * •

Completeness: $x\in A_{\textup{yes}}$ $\Rightarrow$
$\forall\rho_{1}\exists\rho_{2}\ldots\overline{Q}_{i}\rho_{i}$,
$\operatorname{Prob}[V_{n}\text{ accepts
}({\rho_{1}\otimes\rho_{2}\otimes\cdots\otimes\rho_{i}})]\geq c$.

  * •

Soundness: $x\in A_{\textup{no}}$ $\Rightarrow$
$\exists\rho_{1}\forall\rho_{2}\ldots Q_{i}\rho_{i}$ s.t.
$\operatorname{Prob}[V_{n}\text{ accepts
}({\rho_{1}\otimes\rho_{2}\otimes\cdots\otimes\rho_{i}})]\leq s$.

Again, $Q_{i}$ equals $\exists$ when $m$ is even and equals $\forall$
otherwise, and $\overline{Q}_{i}$ is the complementary quantifier to $Q_{i}$.
Define

$\mathsf{Q\Pi}_{i}=\bigcup_{c-s\in\Omega(1/\operatorname{poly}(n))}\mathsf{Q\Pi}_{i}(c,s).$
(8)

######  Definition 2.7 (Quantum Polynomial-Hierarchy ($\mathsf{QPH}$)).

$\mathsf{QPH}=\bigcup_{m\in\mathbb{N}}\;\mathsf{Q\Sigma}_{i}=\bigcup_{m\in\mathbb{N}}\;\mathsf{Q\Pi}_{i}.$
(9)

###  2.3 (Pure-State) Quantum Polynomial Hierarchy ($\mathsf{pureQPH}$)

Above, $\mathsf{QPH}$ was defined using mixed-state quantum proofs. This is in
contrast to $\mathsf{QMA}$ or $\mathsf{QMA}(2)$, where without loss of
generality, one may argue due to convexity that pure states suffice. As it is
not clear how to extend such convexity arguments to alternating quantifiers,
below we introduce Quantum PH with pure-state proofs (for clarity, the
definition below is new to this work).

######  Definition 2.8 ($\mathsf{pureQ\Sigma}_{i}$).

A promise problem $A=(A_{\textup{yes}},A_{\textup{no}})$ is in
$\mathsf{pureQ\Sigma}_{i}(c,s)$ for poly-time computable functions
$c,s:\mathbb{N}\mapsto[0,1]$ if there exists a polynomially bounded function
$p:\mathbb{N}\mapsto\mathbb{N}$ and a poly-time uniform family of quantum
circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ such that for every $n$-bit input $x$,
$V_{n}$ takes $p(n)$-qubit states
$\lvert\psi_{1}\rangle,\ldots,\lvert\psi_{i}\rangle$ as quantum proofs and
outputs a single qubit, then:

  * •

Completeness: If $x\in A_{\textup{yes}}$, then
$\exists\lvert\psi_{1}\rangle\forall\lvert\psi_{2}\rangle\ldots
Q_{i}\lvert\psi_{i}\rangle$ such that $V_{n}$ accepts
$({\lvert\psi_{1}\rangle\otimes\lvert\psi_{2}\rangle\otimes\cdots\otimes\lvert\psi_{i}\rangle})$
with probability $\geq c$.

  * •

Soundness: If $x\in A_{\textup{no}}$, then
$\forall\lvert\psi_{1}\rangle\exists\lvert\psi_{2}\rangle\ldots\overline{Q}_{i}\lvert\psi_{i}\rangle$
such that $V_{n}$ accepts
$({\lvert\psi_{1}\rangle\otimes\lvert\psi_{2}\rangle\otimes\cdots\otimes\lvert\psi_{i}\rangle})$
with probability $\leq s$.

Here, $Q_{i}$ equals $\forall$ when $m$ is even and equals $\exists$
otherwise, and $\overline{Q}_{i}$ is the complementary quantifier to $Q_{i}$.
Define

$\mathsf{pureQ\Sigma}_{i}=\bigcup_{\begin{subarray}{c}c-s\in\Omega(1/\operatorname{poly}(n))\end{subarray}}\mathsf{pureQ\Sigma}_{i}(c,s).$
(10)

######  Definition 2.9 ($\mathsf{pureQ\Pi}_{i}$).

A promise problem $A=(A_{\textup{yes}},A_{\textup{no}})$ is in
$\mathsf{pureQ\Pi}_{i}(c,s)$ for poly-time computable functions
$c,s:\mathbb{N}\mapsto[0,1]$ if there exists a polynomially bounded function
$p:\mathbb{N}\mapsto\mathbb{N}$ and a poly-time uniform family of quantum
circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ such that for every $n$-bit input $x$,
$V_{n}$ takes $p(n)$-qubit states
$\lvert\psi_{1}\rangle,\ldots,\lvert\psi_{i}\rangle$ as quantum proofs and
outputs a single qubit, then:

  * •

Completeness: If $x\in A_{\textup{yes}}$, then
$\forall\lvert\psi_{1}\rangle\exists\lvert\psi_{2}\rangle\ldots
Q_{i}\lvert\psi_{i}\rangle$ such that $V_{n}$ accepts
$({\lvert\psi_{1}\rangle\otimes\lvert\psi_{2}\rangle\otimes\cdots\otimes\lvert\psi_{i}\rangle})$
with probability $\geq c$.

  * •

Soundness: If $x\in A_{\textup{no}}$, then
$\exists\lvert\psi_{1}\rangle\forall\lvert\psi_{2}\rangle\ldots\overline{Q}_{i}\lvert\psi_{i}\rangle$
such that $V_{n}$ accepts
$({\lvert\psi_{1}\rangle\otimes\lvert\psi_{2}\rangle\otimes\cdots\otimes\lvert\psi_{i}\rangle})$
with probability $\leq s$.

Here, $Q_{i}$ equals $\exists$ when $m$ is even and equals $\forall$
otherwise, and $\overline{Q}_{i}$ is the complementary quantifier to $Q_{i}$.
Define

$\mathsf{pureQ\Pi}_{i}=\bigcup_{c-s\in\Omega(1/\operatorname{poly}(n))}\mathsf{pureQ\Pi}_{i}(c,s).$
(11)

The Quantum Polynomial Hierarchy with pure-state proofs can now be defined as
follows.

######  Definition 2.10 (Pure Quantum Poly-Hierarchy ($\mathsf{pureQPH}$)).

$\mathsf{pureQPH}=\bigcup_{m\in\mathbb{N}}\;\mathsf{pureQ\Sigma}_{i}=\bigcup_{m\in\mathbb{N}}\;\mathsf{pureQ\Pi}_{i}.$

###  2.4 Other complexity classes

Next, we define $\textup{Precise}\text{-}\mathsf{QCMA}$ and
BQP${}_{/\textup{mpoly}}$.

######  Definition 2.11 (BQP${}_{/\textup{mpoly}}$).

A promise problem $\Pi=(A_{\textup{yes}},A_{\textup{no}})$ is in
BQP${}_{/\textup{mpoly}}$ if there exists a poly-sized family of quantum
circuits $\\{C_{n}\\}_{n\in\mathbb{N}}$ and a collection of binary advice
strings $\\{a_{n}\\}_{n\in\mathbb{N}}$ with $|a_{n}|=\operatorname{poly}(n)$,
such that for all $n\in\mathbb{N}$ and all strings
$x\in{\left\\{0,1\right\\}}^{n}$,

$\Pr[C_{n}(\lvert x\rangle,\lvert a_{n}\rangle)=1]\geq 2/3\text{ if }x\in
A_{\textup{yes}}\quad\text{ and }\quad\Pr[C_{n}(\lvert x\rangle,\lvert
a_{n}\rangle)=1]\leq 1/3\text{ if }x\in A_{\textup{no}}.$

######  Definition 2.12 ($\textup{Precise}\text{-}\mathsf{QCMA}$).

A promise problem $A=(A_{\textup{yes}},A_{\textup{no}})$ is in
$\textup{Precise}\text{-}\mathsf{QCMA}(c,s)$ for poly-time computable
functions $c,s:\mathbb{N}\mapsto[0,1]$ if there exists poly-bounded functions
$p,q:\mathbb{N}\mapsto\mathbb{N}$ such that $\forall\ell\in\mathbb{N},\
c(\ell)-s(\ell)\geq 2^{-q(\ell)}$, and there exists a poly-time uniform family
of quantum circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ that takes a classical
proof ${y}\in{\left\\{0,1\right\\}}^{p(n)}$ and outputs a single qubit.
Moreover, for an $n$-bit input $x$:

  * •

Completeness: If $x\in A_{\textup{yes}}$, then $\exists\ y$ such that $V_{n}$
accepts $y$ with probability at least $c(n)$.

  * •

Soundness: If $x\in A_{\textup{no}}$, then $\forall\ y$, ${V_{x}}$ accepts $y$
with probability at most $s(n)$.

Define
$\textup{Precise}\text{-}\mathsf{QCMA}=\bigcup_{c,s}\textup{Precise}\text{-}\mathsf{QCMA}(c,s)$.

######  Definition 2.13 ($\mathsf{PP}$).

A language $L$ is in $\mathsf{PP}$ if there exists a probabilistic polynomial
time Turing machine $M$ such that $x\in L\iff\Pr[M(x)=1]>1/2$.

##  3 Collapse theorems and Quantum Karp-Lipton

###  3.1 Collapse Theorem for QCPH

For the quantum-classical hierarchy, $\mathsf{QCPH}$, we now show a quantum
analogue of the standard collapse theorem for classical PH, i.e.
$\mathsf{\Sigma}_{2}^{p}=\mathsf{\Pi}_{2}^{p}$ implies
$\mathsf{PH}=\mathsf{\Sigma}_{2}^{p}$, resolving an open question of
[GSSSY22].

######  Lemma 3.1.

If for any $k\geq 1$, $\mathsf{QC\Sigma}_{k}=\mathsf{QC\Pi}_{k}$, then for all
$i\geq k$, $\mathsf{QC\Sigma}_{i}=\mathsf{QC\Pi}_{i}=\mathsf{QC\Sigma}_{k}$.

###### Proof.

We proceed by induction. For $j\geq k$, define
$P(j):=\mathsf{QC\Sigma}_{j}=\mathsf{QC\Pi}_{j}=\mathsf{QC\Sigma}_{k}$. The
base case $P(k)$ holds by the assumption of the lemma. For the inductive case,
assume $P(j)$ holds for all $k\leq j\leq i-1$. We show $P(j)$ holds for $j=i$.
Consider arbitrary promise problem
$L=({L}_{\mathrm{yes}},{L}_{\mathrm{no}},{L}_{\mathrm{inv}})\in\mathsf{QC\Sigma}_{i}$
and let ${\left\\{V_{n}\right\\}}$ be the verifier circuits for the promise
problem. Define new promise problem
$L^{\prime}=({L}_{\mathrm{yes}}^{\prime},{L}_{\mathrm{no}}^{\prime},{L}_{\mathrm{inv}}^{\prime})$:

$\displaystyle{L}_{\mathrm{yes}}^{\prime}$
$\displaystyle=\left\\{(x,y_{1})\mid\forall y_{2}\exists y_{3}\ldots
Q_{i}y_{i}\;\Pr[V(x,y_{1},y_{2},\ldots,y_{i})=1]\geq\frac{2}{3}\right\\}$ (12)
$\displaystyle{L}_{\mathrm{no}}^{\prime}$
$\displaystyle=\left\\{(x,y_{1})\mid\exists y_{2}\forall
y_{3}\ldots\overline{Q}_{i}y_{i}\;\Pr[V(x,y_{1},y_{2},\ldots,y_{i})=1]\leq\frac{1}{3}\right\\}$
(13) $\displaystyle{L}_{\mathrm{inv}}^{\prime}$
$\displaystyle={\left\\{0,1\right\\}}^{*}\setminus({L}_{\mathrm{yes}}^{\prime}\cup{L}_{\mathrm{no}}^{\prime}).$
(14)

Clearly,
${L}_{\mathrm{yes}}^{\prime}\cap{L}_{\mathrm{no}}^{\prime}=\emptyset$, and so
$({L}_{\mathrm{yes}}^{\prime},{L}_{\mathrm{no}}^{\prime},{L}_{\mathrm{inv}}^{\prime})\in\mathsf{QC\Pi}_{i-1}$.
By the induction hypothesis, there exists promise problem
$L^{\prime\prime}=({L}_{\mathrm{yes}}^{\prime\prime},{L}_{\mathrm{no}}^{\prime\prime},{L}_{\mathrm{inv}}^{\prime\prime})\in\mathsf{QC\Sigma}_{i-1}$
such that
${L}_{\mathrm{no}}^{\prime}\subseteq{L}_{\mathrm{no}}^{\prime\prime}$ and
${L}_{\mathrm{yes}}^{\prime}\subseteq{L}_{\mathrm{yes}}^{\prime\prime}$.
Letting ${\left\\{V^{\prime\prime}_{n}\right\\}}$ denote the verification
circuits for $L^{\prime\prime}$, we have

$\displaystyle(x,y_{1})\in{L}_{\mathrm{yes}}^{\prime}$
$\displaystyle\Rightarrow$
$\displaystyle(x,y_{1})\in{L}_{\mathrm{yes}}^{\prime\prime}$
$\displaystyle\Rightarrow$ $\displaystyle\exists y_{2}\forall y_{3}\ldots
Q_{i}y_{i}\;\Pr[V^{\prime\prime}(x,y_{1},y_{2},\ldots,y_{i})=1]\geq\frac{2}{3}$
(15) $\displaystyle(x,y_{1})\in{L}_{\mathrm{no}}^{\prime}$
$\displaystyle\Rightarrow$
$\displaystyle(x,y_{1})\in{L}_{\mathrm{no}}^{\prime\prime}$
$\displaystyle\Rightarrow$ $\displaystyle\forall y_{2}\exists
y_{3}\ldots\overline{Q}_{i}y_{i}\;\Pr[V^{\prime\prime}(x,y_{1},y_{2},\ldots,y_{i})=1]\leq\frac{1}{3}.$
(16)

Now considering again $L=(L_{yes},{L}_{\mathrm{no}},{L}_{\mathrm{inv}})$, we
have

$\displaystyle x\in{L}_{\mathrm{yes}}$ $\displaystyle\Rightarrow$
$\displaystyle\exists y_{1}\text{ s.t.
}(x,y_{1})\in{L}_{\mathrm{yes}}^{\prime}$ $\displaystyle\Rightarrow$
$\displaystyle\exists y_{1}\exists y_{2}\forall y_{3}\ldots
Q_{i-1}y_{i}\Pr[V^{\prime}(x,y_{1},y_{2},\ldots,y_{i})=1]\geq\frac{2}{3}$ (17)
$\displaystyle x\in{L}_{\mathrm{no}}$ $\displaystyle\Rightarrow$
$\displaystyle\forall y_{1}\text{ s.t.
}(x,y_{1})\in{L}_{\mathrm{no}}^{\prime}$ $\displaystyle\Rightarrow$
$\displaystyle\forall y_{1}\forall y_{2}\exists
y_{3}\ldots\overline{Q}_{i-1}y_{i}\Pr[V^{\prime}(x,y_{1},y_{2},\ldots,y_{i})=1]\leq\frac{1}{3}.$
(18)

We conclude $L\in\mathsf{QC\Sigma}_{i-1}=\mathsf{QC\Sigma}_{i}$. So
$\mathsf{QC\Sigma}_{j}=\mathsf{QC\Sigma}_{k}$. Similarly,
$\mathsf{QC\Pi}_{i}\subseteq\mathsf{QC\Pi}_{i-1}=\mathsf{QC\Sigma}_{k}$. Thus,
$P(i)$ holds, as claimed. ∎

See 1.1

###### Proof.

Immediate from Lemma 3.1. ∎

Theorem 1.1, in turn, immediately resolves a second open question of
[GSSSY22], which showed that if
$\textup{Precise}\text{-}\mathsf{QCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$,
then $\mathsf{QC\Sigma}_{2}=\mathsf{QC\Pi}_{2}$: Theorem 1.1 immediately
yields that the latter collapses $\mathsf{QCPH}$.

See 1.2 Recall, however, that later in Section 3.2 we will show a stronger
version of this result which gives a true quantum-classical analogue of the
classical Karp-Lipton Theorem.

###  3.2 Quantum-Classical Karp-Lipton Theorem

We will show that if there exists a polynomial size circuit family
${\left\\{C_{n}\right\\}}_{n\in\mathbb{N}}$ that can decide a $\mathsf{QCMA}$
complete problem, then $\mathsf{QC\Pi}_{2}\subseteq\mathsf{QC\Sigma}_{2}$.
Using Theorem 1.1, it follows that if
$\mathsf{QCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$, then the quantum-
classical polynomial hierarchy collapses to the second level.

Let $L$ be any promise problem in $\mathsf{QC\Pi}_{2}$, and let
$\\{V_{n}\\}_{n\in\mathbb{N}}$ be the corresponding (quantum) verifier. In
order to show $L\in\mathsf{QC\Sigma}_{2}$, we need to construct a verifier
$V^{\prime}$ such that if $x\in{L}_{\mathrm{yes}}$, then there exists a
$y^{\prime}_{1}$ such that for all $y^{\prime}_{2}$,
$V^{\prime}(x,y_{1},y_{2})$ accepts with some probability $\alpha$, and if
$x\in{L}_{\mathrm{no}}$, then for all $y^{\prime}_{1}$, there exists a
$y^{\prime}_{2}$ such that the acceptance probability of
$V^{\prime}(x,y^{\prime}_{1},y^{\prime}_{2})$ is noticeably smaller than
$\alpha$. As discussed in the introduction, we require two key ingredients for
this result. The first is an isolation-lemma for $\mathsf{QCMA}$, which was
given by [ABBS22]. This ensures that a $\mathsf{QCMA}$ instance is converted
to a $\mathsf{UQCMA}$ instance. Next, we use the search-to-decision reduction
for $\mathsf{UQCMA}$, given by [INNRY22]. We first discuss some preliminaries
relevant to these two works.

##### Quantum-Classical Isolation Lemma and related preliminaries:

The first step in our proof involves a randomized reduction from
$\mathsf{QCMA}$ to $\mathsf{UQCMA}$ ($\mathsf{QCMA}$ but with the additional
promise that every ‘yes’ instance has exactly one accepting witness). We
recall trivial complete problems for $\mathsf{QCMA}$ and $\mathsf{UQCMA}$, as
defined in [ABBS22], and the randomized reduction from $\mathsf{QCMA}$ to
$\mathsf{UQCMA}$.

######  Definition 3.2 ($\mathsf{UQCMA}$).

Let $A=(A_{\textup{yes}},A_{\textup{no}})$ be a promise problem. We say that
$A\in\mathsf{UQCMA}(c,s)$ for polynomial-time computable functions
$c,s:\mathbb{N}\mapsto[0,1]$ if there exists a polynomially bounded function
$p:\mathbb{N}\mapsto\mathbb{N}$ and a polynomial-time uniform family of
quantum circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ such that for every $n$-bit
input $x$, $V_{n}$ takes in classical proof
${y_{1}}\in{\left\\{0,1\right\\}}^{p(n)}$ and outputs a single qubit, such
that:

  * •

Completeness: $x\in A_{\textup{yes}}$ $\Rightarrow$ $\exists y_{1}$ s.t.
$\Pr[V_{n}(x,y_{1})=1]\geq c$ and $\forall y_{1}^{\prime}\neq
y_{1}\Pr[V_{n}(x,y_{1})=1]\leq s$.

  * •

Soundness: $x\in A_{\textup{no}}$ $\Rightarrow$ $\forall y_{1}$ s.t.
$\Pr[V_{n}(x,y_{1})=1]\leq s$.

$\text{Define
}\;\mathsf{UQCMA}:=\bigcup_{{c-s\in\Omega(1/\operatorname{poly}(n))}}\mathsf{UQCMA}(c,s).$
(19)

######  Definition 3.3 ($\mathsf{TQCMAPP}$: Trivial complete problem for
$\mathsf{QCMA}$).

Let $\mathsf{TQCMAPP}$ = $(\mathsf{TQCMAPP}_{\mathrm{yes}}$,
$\mathsf{TQCMAPP}_{\mathrm{no}})$ denote the ‘trivial’ complete problem for
$\mathsf{QCMA}$ defined as follows. Every instance consists of a quantum
circuit $U$, instance $x$, probabilities $p_{1},p_{2}$, witness length $\ell$
(probabilities and witness length expressed in unary999We assume the
probabilities are rationals, and the numerator and denominator are expressed
in unary).

  * •

$(U,x,p_{1},p_{2},\ell)\in\mathsf{TQCMAPP}_{\mathrm{yes}}$ $\implies$ $\exists
d\in\left\\{0,1\right\\}^{\ell}$ s.t. $\Pr\left[U\left(\lvert x\rangle,\lvert
d\rangle\right)=1\right]\geq p_{2}$

  * •

$(U,x,p_{1},p_{2},\ell)\in\mathsf{TQCMAPP}_{\mathrm{no}}$ $\implies$ $\forall
d\in\left\\{0,1\right\\}^{\ell}$, $\Pr\left[U\left(\lvert x\rangle,\lvert
d\rangle\right)=1\right]\leq p_{1}$

######  Definition 3.4 ($\mathsf{UQCMAPP}$: Trivial complete problem for
$\mathsf{UQCMA}$).

Let $\mathsf{UQCMAPP}$ = $(\mathsf{UQCMAPP}_{\mathrm{yes}}$,
$\mathsf{UQCMAPP}_{\mathrm{no}})$ denote the ‘trivial’ complete problem for
$\mathsf{UQCMA}$ defined as follows. Every instance consists of a quantum
circuit $U$, instance $x$, probabilities $p_{1},p_{2}$, witness length $\ell$
(probabilities and witness length expressed in unary).

  * •

$(U,x,p_{1},p_{2},\ell)\in\mathsf{UQCMAPP}_{\mathrm{yes}}$ $\implies$ $\exists
d\in\left\\{0,1\right\\}^{\ell}$ s.t. $\Pr\left[U\left(\lvert x\rangle,\lvert
d\rangle\right)=1\right]\geq p_{2}$ and for all $d^{\prime}\neq d$,
$\Pr\left[U\left(\lvert x\rangle,\lvert d^{\prime}\rangle\right)=1\right]\leq
p_{1}$

  * •

$(U,x,p_{1},p_{2},\ell)\in\mathsf{UQCMAPP}_{\mathrm{no}}$ $\implies$ $\forall
d\in\left\\{0,1\right\\}^{\ell}$, $\Pr\left[U\left(\lvert x\rangle,\lvert
d\rangle\right)=1\right]\leq p_{1}$

######  Theorem 3.5 (Randomized reduction from $\mathsf{QCMA}$ to
$\mathsf{UQCMA}$: Corollary 40 from [ABBS22]).

There is a probabilistic polynomial time reduction $f$ from $\mathsf{TQCMAPP}$
to $\mathsf{UQCMAPP}$ such that

  * •

$\phi=(U,x,p_{1},p_{2},\ell)\in\mathsf{TQCMAPP}_{\mathrm{yes}}\implies\Pr\left[f(\phi)\in\mathsf{UQCMAPP}_{\mathrm{yes}}\right]\geq
1/32\ell^{2}$.

  * •

$\phi=(U,x,p_{1},p_{2},\ell)\in\mathsf{TQCMAPP}_{\mathrm{no}}\implies\Pr\left[f(\phi)\in\mathsf{UQCMAPP}_{\mathrm{no}}\right]=1$

Here the probabilities are over the random coins used by reduction $f$.

##### Search-to-decision Reduction for $\mathsf{UQCMA}$ and related
preliminaries:

Next, we consider some preliminary results needed for search-to-decision
reduction for $\mathsf{UQCMA}$. Since these results were proven either
explicitly or implicitly in prior works, we only state the lemma/theorem
statements here.

######  Lemma 3.6.

Let $\Pi$ be a measurement projector. If
$\lVert\lvert\psi\rangle-\lvert\phi\rangle\rVert\leq\varepsilon$, then
$\lVert{\Pi\lvert\psi\rangle\langle\psi\rvert}-{\Pi\lvert\phi\rangle\langle\phi\rvert}\rVert_{\mathrm{tr}}\leq
2\varepsilon$.

######  Lemma 3.7 (Approximate Bernstein-Vazirani).

Consider the function families
$f=\\{f_{n}:\left\\{0,1\right\\}^{n}\rightarrow\left\\{0,1\right\\}\\}$,
$g=\\{g_{n}:\left\\{0,1\right\\}^{n}\rightarrow\left\\{0,1\right\\}^{t(n)}\\}$
and $h=\\{h_{n}:\left\\{0,1\right\\}^{n}\rightarrow\left\\{0,1\right\\}\\}$.
Let the function $f^{s}_{n}(x)=\langle x|s\rangle\bmod\leavevmode\nobreak\ 2$
and $g,h$ be such that $f^{s}_{n}(x)=1\Leftrightarrow h_{t(n)}(g_{n}(x))=1$.
Given a non-uniform quantum circuit family $\\{C_{n}\\}$ such that
$\\{C_{t(n)}\\}$ computes $h_{t(n)}$ with probability $1-1/2^{n}$, there is a
non-uniform circuit family $\\{C^{\prime}_{n}\\}$ that takes $\\{C_{t(n)}\\}$
as advice and outputs $s$ with probability $1-\sqrt{1/2^{n-4}}$.

A recent work by Irani et al. [INNRY22] uses the above approximate Bernstein-
Vazirani for a randomized search-to-decision reduction for $\mathsf{QCMA}$.

See 1.3

###### Proof.

Let $L=({L}_{\mathrm{yes}},{L}_{\mathrm{no}})\in\mathsf{QC\Pi}_{2}$. Then
there exists a polynomial $p_{L}:\mathbb{N}\mapsto\mathbb{N}$ and polynomial-
time uniform family of quantum circuits
${\left\\{V_{n}\right\\}}_{n\in\mathbb{N}}$ such that each $V_{n}$ takes as
input an instance $x\in\left\\{0,1\right\\}^{n}$, two proofs
$y_{1},y_{2}\in\left\\{0,1\right\\}^{p_{L}(n)}$, and the following
completeness and soundness guarantees hold:

  * •

(Completeness)

$x\in{L}_{\mathrm{yes}}\Rightarrow\forall y_{1}$ $\exists y_{2}$,
$\Pr\left[V_{n}(x,y_{1},y_{2})=1\right]\geq 1-\frac{1}{p_{L}(n)^{4}}$ (where
$n=|x|$)

  * •

(Soundness)

$x\in{L}_{\mathrm{no}}\Rightarrow\exists y_{1}$ $\forall y_{2}$,
$\Pr\left[V_{n}(x,y_{1},y_{2})=1\right]\leq\frac{1}{p_{L}(n)^{4}}$ (where
$n=|x|$)

Consider the following promise language
$L^{\prime}=({L}_{\mathrm{yes}}^{\prime},{L}_{\mathrm{no}}^{\prime})$, which
is also characterized by the polynomial $p_{L}$ and family of quantum circuits
${\left\\{V_{n}\right\\}}_{n\in\mathbb{N}}$ with the following completeness
and soundness guarantees:

  * •

(Completeness)

$(x,y_{1})\in{L}_{\mathrm{yes}}^{\prime}\Rightarrow|y_{1}|=p_{L}(n)\text{ and
}\exists y_{2}$ s.t. $\Pr\left[V_{n}(x,y_{1},y_{2})=1\right]\geq
1-\frac{1}{p_{L}(n)^{4}}$ (where $n=|x|$)

  * •

(Soundness)

$(x,y_{1})\in{L}_{\mathrm{no}}^{\prime}\Rightarrow|y_{1}|=p_{L}(n)\text{ and
}\forall y_{2}\in\left\\{0,1\right\\}^{p_{L}(n)}$
$\Pr\left[V_{n}(x,y_{1},y_{2})=1\right]\leq\frac{1}{p_{L}(n)^{4}}$ (where
$n=|x|$)

The promise language $L^{\prime}$ is in $\mathsf{QCMA}$. Therefore, using the
(trivial) reduction from $L^{\prime}$ to $\mathsf{TQCMAPP}$, we get the
following ‘yes’ and ‘no’ instances for $\mathsf{TQCMAPP}$:

  * •

$(x,y_{1})\in{L}_{\mathrm{yes}}^{\prime}\Rightarrow\left(V_{|x|},(x,y_{1}),1/p_{L}(|x|)^{4},1-1/p_{L}(|x|)^{4},p_{L}(|x|)\right)\in\mathsf{TQCMAPP}_{\mathrm{yes}}$

  * •

$(x,y_{1})\in{L}_{\mathrm{no}}^{\prime}\Rightarrow\left(V_{|x|},(x,y_{1}),1/p_{L}(|x|)^{4},1-1/p_{L}(|x|)^{4},p_{L}(|x|)\right)\in\mathsf{TQCMAPP}_{\mathrm{no}}$

Next, using the randomized reduction from $\mathsf{QCMA}$ to $\mathsf{UQCMA}$
(Theorem 3.5), we get a family of verification circuits
$V^{\mathrm{uq}}_{|x|}$ and probability thresholds $p_{1},p_{2}$ with the
following guarantees:

  * •

$(x,y_{1})\in{L}_{\mathrm{yes}}^{\prime}\Rightarrow\Pr\left[\left(V^{\mathrm{uq}}_{|x|},(x,y_{1}),p_{1},p_{2},p_{L}(|x|)\right)\in\mathsf{UQCMAPP}_{\mathrm{yes}}\right]\geq
1/32p_{L}(|x|)^{2}$

  * •

$(x,y_{1})\in{L}_{\mathrm{no}}^{\prime}\Rightarrow\Pr\left[\left(V^{\mathrm{uq}}_{|x|},(x,y_{1}),p_{1},p_{2},p_{L}(|x|)\right)\in\mathsf{UQCMAPP}_{\mathrm{no}}\right]=1$

Here, the circuit $V^{\mathrm{uq}}_{|x|}$ is a ‘random refinement’ of
$V_{|x|}$, and $p_{1},p_{2}$ are chosen from an appropriate distribution over
$[1/p_{L}(|x|),1-1/p_{L}(|x|)]$.

Suppose $\mathsf{QCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$, then there
exists a family of polynomial-sized circuits
${\left\\{C_{n}\right\\}}_{n\in\mathbb{N}}$ and a sequence of (classical)
advice strings ${\left\\{\alpha_{n}\right\\}}_{n\in\mathbb{N}}$ such that they
can decide any yes/no instance of $\mathsf{TQCMAPP}/\mathsf{UQCMAPP}$ with
high accuracy. More formally, the following holds:

  * •

If $\phi=(U,x,p_{1},p_{2},\ell)\in\mathsf{UQCMAPP}_{\mathrm{yes}}$, then
$\Pr\left[C_{n}\left(\lvert\alpha_{n}\rangle,\lvert\phi\rangle\right)=1\right]\geq
1-1/2^{\ell}$

  * •

If $\phi=(U,x,p_{1},p_{2},\ell)\in\mathsf{UQCMAPP}_{\mathrm{no}}$, then
$\Pr\left[C_{n}\left(\lvert\alpha_{n}\rangle,\lvert\phi\rangle\right)=1\right]\leq
1/2^{\ell}$

Following the single query search-to-decision reduction of Irani et al.
[INNRY22], we will use ${\left\\{C_{n}\right\\}}_{n}$ to find a witness for
$\mathsf{UQCMAPP}$ instances as follows.

Let $\phi=(U,x,p_{1},p_{2},\ell)\in\mathsf{UQCMAPP}_{\mathrm{yes}}$ whose
(unique) witness $d_{\phi}\in\left\\{0,1\right\\}^{\ell}$ we wish to find.
Consider the function
$f_{\phi}:\left\\{0,1\right\\}^{\ell}\mapsto\left\\{0,1\right\\}$ where
$f_{\phi}(z)=\langle z|d_{\phi}\rangle(\bmod\leavevmode\nobreak\ 2)$. We will
use ${\left\\{C_{n}\right\\}}$ to approximate $f_{\phi}(\cdot)$, and then use
$\mathsf{ApproxBV}$ to compute $d_{\phi}$.

Using $\phi$, for every $z\in\left\\{0,1\right\\}^{\ell}$ we can define a new
$\mathsf{UQCMAPP}$ instance $\phi_{z}=(U_{z},x,p_{1},p_{2},\ell)$, where

$U_{z}\left(\lvert x\rangle,\lvert d\rangle\right)=U\left(\lvert
x\rangle,\lvert d\rangle\right)\wedge\left(\langle
z|d\rangle(\bmod\leavevmode\nobreak\ 2)\right)$

Since $\phi\in\mathsf{UQCMAPP}_{\mathrm{yes}}$ with unique witness $d_{\phi}$,
for any $z\in\left\\{0,1\right\\}^{\ell}$,

$f_{\phi}(z)=1\iff\phi_{z}\in\mathsf{UQCMAPP}_{\mathrm{yes}}(\text{with unique
witness }d_{\phi})$

If $f_{\phi}(z)=1$, then
$\Pr\left[C_{|\phi_{z}|}\left(\phi_{z}\right)=1\right]\geq 1-1/2^{|z|}$, and
if $f_{\phi}(z)=0$, then
$\Pr\left[C_{|\phi_{z}|}\left(\phi_{z}\right)=1\right]\leq 1/2^{|z|}$. Hence
we can use $\mathsf{ApproxBV}$ (as defined in Lemma 3.7) to compute the unique
witness if it exists (after running $\mathsf{ApproxBV}$, we will also check
that the output is indeed a witness of $\phi$).

Using the above observations, we can show that $L\in\mathsf{QC\Sigma}_{2}$.
The verifier $V_{|x|}^{\prime}$ takes as input the instance $x$, a circuit
$C$, string $y_{1}\in\left\\{0,1\right\\}^{p_{L}(|x|)}$ and works as follows:

  1. 1.

Consider the $\mathsf{TQCMAPP}$ instance
$\left(V_{|x|},(x,y_{1}),1/p_{L}(|x|)^{4},1-1/p_{L}(|x|)^{4},p_{L}(|x|)\right)$.
The verifier $V_{|x|}^{\prime}$ first computes the $\mathsf{UQCMAPP}$ instance
$\phi=\left(V^{\mathrm{uq}}_{|x|},(x,y_{1}),p_{1},p_{2},p_{L}(|x|)\right)$.
This instance is in $\mathsf{UQCMAPP}_{\mathrm{yes}}$ with probability at
least $1/32p_{L}(|x|)^{2}$.

  2. 2.

Next, it uses the circuit $C$ and $\phi$ to run $\mathsf{ApproxBV}$. In
particular, set $f^{s}_{|x|}$ as $f_{\phi}$ defined previously, $g_{|x|}$ as
the trivial reduction from $z$ to $\phi_{z}$ and $h_{|\phi_{z}|}(\psi)=1$ if
$\psi\in\mathsf{UQCMAPP}_{\mathrm{yes}}$, $0$ if
$\psi\in\mathsf{UQCMAPP}_{\mathrm{no}}$ and undefined otherwise. The circuit
$C$ takes as advice the non-uniform circuit family for $\mathsf{UQCMAPP}$ and
runs $\mathsf{ApproxBV}$. This results in a string $y_{2}$.

  3. 3.

Finally, it simulates $V_{|x|}(x,y_{1},y_{2})$ and outputs $1$ iff $V_{|x|}$
does.

For any $x\in{L}_{\mathrm{yes}}$, there exists a circuit $C$ such that for all
$y_{1}\in\left\\{0,1\right\\}^{p_{L}(|x|)}$,

$\Pr\left[V_{|x|}^{\prime}(x,C,y_{1})=1\right]\geq\frac{1}{32p_{L}(|x|)^{2}}\left(1-\frac{4}{2^{p_{L}(|x|)/2}}\right)\left(1-\frac{1}{p_{L}(|x|)^{4}}\right).$

On the other hand, if $x\in{L}_{\mathrm{no}}$, then there exists a string
$y_{1}$ such that for any string $y_{2}$ computed in Step 2,
$V_{|x|}^{\prime}$ outputs $1$ with probability at most $1/p_{L}(|x|)^{4}$. ∎

####  3.2.1 Immediate Implications of Theorem 1.3

We now discuss some immediate implications of the quantum-classical variant of
Karp-Lipton Theorem.

#####
$\mathsf{UQCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}\implies\mathsf{QCPH}$
collapse

Notice in the proof of Theorem 1.3 that the search-to-decision reduction only
uses the non-uniform circuit for deciding $\mathsf{UQCMAPP}$ as advice. In
particular this means that we only need the assumption
$\mathsf{UQCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$ for the above
proof to work. This leads to the following corollary:

######  Corollary 3.8.

If $\mathsf{UQCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$, then
$\mathsf{QC\Pi}_{2}\subseteq\mathsf{QC\Sigma}_{2}$, and therefore the quantum-
classical polynomial hierarchy collapses to the second level.

##### A stronger collapse

In the classical setting, Sengupta observed that if
$\mathsf{NP}\subseteq\mathsf{P}/\operatorname{poly}$, then $\mathsf{PH}$
collapses to $\mathsf{S}^{p}_{2}$ (this observation is first mentioned in the
work of Cai [Cai01]). The complexity class $\mathsf{S}^{p}_{2}$ [RS98, Can96]
is contained in $\Sigma_{2}\cap\Pi_{2}$, and therefore gives a ‘stronger’
Karp-Lipton theorem in the classical setting. Following our proof above, we
get a similar result for the quantum-classical setting — $\mathsf{QCPH}$
collapses to $\mathsf{QCS}^{p}_{2}$ if
$\mathsf{QCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$. Below, we define
the complexity class $\mathsf{QCS}^{p}_{2}$, and state the result.

######  Definition 3.9 (Quantum-Classical $\mathsf{S}^{p}_{2}$).

Let $A=(A_{\textup{yes}},A_{\textup{no}})$ be a promise problem. We say that
$A$ is in $\mathsf{QCS}^{p}_{2}(c,s)$ for polynomial-time computable functions
$c,s:\mathbb{N}\mapsto[0,1]$ if there exists a polynomially bounded function
$p:\mathbb{N}\mapsto\mathbb{N}$ and a polynomial-time uniform family of
quantum circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ such that for every $n$-bit
instance $x$, $V_{n}$ takes in classical proofs
${y_{1}}\in{\left\\{0,1\right\\}}^{p(n)},{y_{2}}\in{\left\\{0,1\right\\}}^{p(n)}$
and outputs a single qubit, such that:

  * •

Completeness: $x\in A_{\textup{yes}}$ $\Rightarrow$ $\exists y_{1}\forall
y_{2}$, $\Pr[V_{n}(x,y_{1},y_{2})=1]\geq c$.

  * •

Soundness: $x\in A_{\textup{no}}$ $\Rightarrow$ $\exists y_{2}\forall y_{1}$,
$\Pr[V_{n}(x,y_{1},y_{2})=1]\leq s$.

$\text{Define
}\;\mathsf{QCS}^{p}_{2}:=\bigcup_{{c-s\in\Omega(1/\operatorname{poly}(n))}}\mathsf{QCS}^{p}_{2}(c,s).$
(20)

######  Theorem 3.10.

If $\mathsf{UQCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$, then
$\mathsf{QCPH}\subseteq\mathsf{QCS}^{p}_{2}$.

In the classical setting, the Karp-Lipton collapse was improved to
$\mathsf{ZPP}^{\mathsf{NP}}$ [BCGKT95, KW98]. Later, Cai showed that
$\mathsf{S}^{p}_{2}\subseteq\mathsf{ZPP}^{\mathsf{NP}}$, and the collapse was
further improved to ‘oblivious’ $\mathsf{S}^{p}_{2}$
($\mathsf{OS}^{p}_{2}$)[CR06].

In the quantum setting, we don’t have an analogue for Cai’s result, and the
following are some open questions:

  * •

Does $\mathsf{QCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$ imply that
$\mathsf{QCPH}\subseteq\mathsf{ZPP}^{\mathsf{QCMA}}$?

  * •

Is $\mathsf{QCS}^{p}_{2}$ contained in $\mathsf{ZPP}^{\mathsf{QCMA}}$?

##### Implications for $\mathsf{QCMA}$ and $\mathsf{QCAM}$

Arvind et al. [AKSS95] showed that if $\mathsf{NP}$ languages can be decided
using polynomial sized circuits, then $\mathsf{AM}=\mathsf{MA}$. Using our
techniques, one can obtain a similar implication for $\mathsf{QCMA}$ and
$\mathsf{QCAM}$. This proof does not follow directly by combining the
classical result with our $\mathsf{QCPH}$ collapse result. However, our
approach for the quantum-classical Karp-Lipton theorem can be modified to get
this result. Since this proof is very similar, we state the result here.

First, we define the complexity class $\mathsf{QCAM}$.

######  Definition 3.11 ($\mathsf{QCAM}$).

Let $A=(A_{\textup{yes}},A_{\textup{no}})$ be a promise problem. We say that
$A\in\mathsf{QCAM}(c,s)$ for polynomial-time computable functions
$c,s:\mathbb{N}\mapsto[0,1]$ if there exists a polynomially bounded function
$p:\mathbb{N}\mapsto\mathbb{N}$ and a polynomial-time uniform family of
quantum circuits $\\{V_{n}\\}_{n\in\mathbb{N}}$ such that for every $n$-bit
input $x$, $V_{n}$ takes in classical proof
${y}\in{\left\\{0,1\right\\}}^{p(n)}$ and a random string
$z\in{\left\\{0,1\right\\}}^{p(n)}$ and outputs a single qubit, such that:

  * •

Completeness: $x\in A_{\textup{yes}}$ $\Rightarrow$ $\Pr_{z}[\exists
y_{1}\text{ s.t. }\Pr[V_{n}(x,z,y_{1})=1]\geq 1-\frac{1}{2^{n}}]\geq c$.

  * •

Soundness: $x\in A_{\textup{no}}$ $\Rightarrow$ $\Pr_{z}[\exists y_{1}\text{
s.t. }\Pr[V_{n}(x,z,y_{1})=1]\geq 1-\frac{1}{2^{n}}]\leq s$.

$\text{Define
}\;\mathsf{QCAM}:=\bigcup_{{c^{\prime}-s^{\prime}\in\Omega(1/\operatorname{poly}(n))}}\mathsf{QCAM}(c,s).$
(21)

######  Theorem 3.12 (Quantum-Classical analogue of [AKSS95]).

If $\mathsf{UQCMA}\subseteq\textup{BQP${}_{/\textup{mpoly}}$}$, then
$\mathsf{QCMA}=\mathsf{QCAM}$.

##  4 Error reduction for $\mathsf{pureQPH}$

We next study (weak) error reduction for $\mathsf{pureQPH}$ (pure proofs). For
this, we first require an asymmetric generalization of the Product Test
[MKB05, HM13], given in Section 4.1. We then give one-sided error reduction
results in Section 4.2.

###  4.1 Asymmetric product test

$\Qcircuit<EMAIL_ADDRESS>0\rangle}&\gate{H}\ctrl{1}\gate{H}\meter\\\
\lstick{\lvert\psi\rangle}\qw\multigate{1}{\textup{SWAP}}\qw\qw\\\
\lstick{\lvert\phi\rangle}\qw\ghost{\textup{SWAP}}\qw\qw\\\ }$ Figure 1: The
SWAP test, whose output is the measurement result on the first wire.

We first give a generalization of the Product Test [MKB05, HM13], which we
denote the Asymmetric Product Test (APT), stated as follows:

  1. 1.

The input is
$\lvert\psi\rangle\in\mathbb{C}^{d_{1}}\otimes\cdots\otimes\mathbb{C}^{d_{n}}$
in register $A$, and $\lvert\phi\rangle\in\mathbb{C}^{d^{m}}$ in register $B$,
where for brevity $d:=d_{1}\cdots d_{n}$. We think of $B$ as encoding $m$
copies of $A$.

  2. 2.

Choose $(i,j)\in[n]\times[m]$ uniformly at random.

  3. 3.

Run the SWAP Test (Figure 1) between the $i$th register of $A$, and in $B$,
the $i$th register of the $j$th copy of $A$.

  4. 4.

Accept if the SWAP Test outputs $0$, reject otherwise.

In fact, above, one can also assume that $\lvert\phi\rangle$ in the APT is
potentially entangled across two registers $B$ and $C$, as we do for the main
lemma of this section, given below.

######  Lemma 4.1 (Asymmetric Product Test (APT)).

Define $d=d_{1}\cdots d_{n}$. Consider
$\lvert\phi\rangle_{BC}\in\mathbb{C}^{d^{m}}\otimes\mathbb{C}^{d^{\prime}}$
for some $d^{\prime}>0$. Suppose

$\max_{\lvert\psi\rangle:=\lvert\psi_{1}\rangle\otimes\cdots\otimes\lvert\psi_{n}\rangle\in\mathbb{C}^{d}}\quad\langle\phi\rvert_{BC}[(\lvert\psi\rangle\langle\psi\rvert^{\otimes
m})_{B}\otimes I_{C}]\lvert\phi\rangle_{BC}=1-\varepsilon$ (22)

for $\varepsilon\geq 0$. Then, given the state
$\lvert\eta\rangle_{ABC}:=\lvert\psi\rangle_{A}\otimes\lvert\phi\rangle_{BC}$,
the APT accepts with probability at most $1-\varepsilon/2mn$.

###### Proof.

Let $\\{\lvert\alpha_{ik}\rangle\\}_{k\in[d_{i}]}$ be an orthonormal basis of
$\mathbb{C}^{d_{i}}$ with $\lvert\alpha_{i1}\rangle:=\lvert\psi_{i}\rangle$,
and define index set

$X=\\{(x_{ij})_{i\in[n],j\in[m]}\mid\forall ij:x_{ij}\in[d_{i}]\\}.$ (23)

Then, rewrite $\lvert\phi\rangle_{BC}$ in the
${\left\\{\lvert\alpha_{ik}\rangle\right\\}}_{k}$ bases to obtain:

$\lvert\phi\rangle=\sum_{x\in
X}a_{x}\left(\bigotimes_{ij}\lvert\alpha_{i,x_{ij}}\rangle\right)_{B}\lvert\gamma_{x}\rangle_{C}$
(24)

for some states $\lvert\gamma_{x}\rangle_{C}$. Without loss of generality,
consider the swap test between the first register of $A$, $\mathbb{C}^{d_{1}}$
(which contains $\lvert\psi_{1}\rangle$), and the first copy of
$\mathbb{C}^{d_{1}}$ in $B$. Just prior to the final measurement in the test,
we have the state $\lvert\eta^{\prime}\rangle_{SABC}$ given by (where $S$
encodes the control qubit for SWAP in the SWAP test)

$\displaystyle\sum_{x\in X}a_{x}\left(\frac{1}{2}\lvert
0\rangle_{S}\bigl{(}\lvert\psi_{1}\rangle\lvert\alpha_{1,x_{11}}\rangle+\lvert\alpha_{1,x_{11}}\rangle\lvert\psi_{1}\rangle\bigr{)}+\frac{1}{2}\lvert
1\rangle_{S}\bigl{(}\lvert\psi_{1}\rangle\lvert\alpha_{1,x_{11}}\rangle-\lvert\alpha_{1,x_{11}}\rangle\lvert\psi_{1}\rangle\bigr{)}\right)\otimes\bigotimes_{i\neq
1\text{ or }j\neq 1}\lvert\alpha_{i,x_{ij}}\rangle\lvert\gamma_{x}\rangle.$
$\displaystyle=:\sum_{x\in X}a_{x}\lvert\eta^{\prime}_{x}\rangle_{SABC}.$ (25)

We now show that the cross terms of
$\langle\eta^{\prime}|\eta^{\prime}\rangle$ vanish, as
$\langle\eta^{\prime}_{x}|\eta^{\prime}_{y}\rangle=0$ with $x\neq y$, where
$x,y\in X$: (1) If $x_{ij}\neq y_{ij}$ for $(i,j)\neq(1,1)$, this follows
immediately from orthonormality of the basis sets
$\\{\lvert\alpha_{ik}\rangle\\}_{k\in[d_{i}]}$. (2) The only remaining case is
$x_{11}\neq y_{11}$. Without loss of generality, $y_{11}\neq 1$. Then
$\lvert\alpha_{1,y_{11}}\rangle$ is orthogonal to $\lvert\psi_{1}\rangle$,
again by choice of our basis set. Hence,
$\langle\psi_{1},\alpha_{1,x_{11}}|\alpha_{1,y_{11}},\psi_{1}\rangle=0$. Since
trivially
$\langle\psi_{1},\alpha_{1,x_{11}}|\psi_{1},\alpha_{1,y_{11}}\rangle=0$, we
again have $\langle\eta^{\prime}_{x}|\eta^{\prime}_{y}\rangle=0$.

As for the non-cross-terms, we first have again from our basis choice that for
any $x\in X$,

$\langle\eta^{\prime}_{x}\rvert(\lvert 0\rangle\langle
0\rvert_{S})\lvert\eta^{\prime}_{x}\rangle=\begin{cases}1,&\text{if
}x_{11}=1\\\ \frac{1}{2},&\text{if }x_{11}\neq 1\end{cases}.$ (26)

Recall now that the APT selects $i\in[n]$ and $j\in[m]$ uniformly at random
and does a SWAP test between $\lvert\psi_{i}\rangle$ (the $i$th register of
$A$) and the $j$th copy of the $i$ register of $B$. Thus, conditioned on the
APT randomly choosing $(i,j)=(1,1)$, we may bound its acceptance probability
as

$\Pr[\mathrm{APT}(\lvert\eta\rangle)=1\mid
i=1,j=1]=\langle\eta^{\prime}\rvert(\lvert 0\rangle\langle
0\rvert_{S})\lvert\eta^{\prime}\rangle=\sum_{\begin{subarray}{c}x\in X\\\
\text{s.t. }x_{11}=1\end{subarray}}\lvert
a_{x}\rvert^{2}+\frac{1}{2}\sum_{\begin{subarray}{c}x\in X\\\ \text{s.t.
}x_{11}\neq 1\end{subarray}}\lvert a_{x}\rvert^{2}.$ (27)

By symmetry, an identical argument holds for any pair $(i,j)$, and so

$\displaystyle\Pr[\mathrm{APT}(\lvert\eta\rangle)=1]$
$\displaystyle=\frac{1}{mn}\sum_{ij}\left(\sum_{\begin{subarray}{c}x\in X\\\
\text{s.t. }x_{ij}=1\end{subarray}}\lvert
a_{x}\rvert^{2}+\frac{1}{2}\sum_{\begin{subarray}{c}x\in X\\\ \text{s.t.
}x_{ij}\neq 1\end{subarray}}\lvert a_{x}\rvert^{2}\right)$ (28)
$\displaystyle\leq\lvert a_{1^{mn}}\rvert^{2}+\frac{2mn-1}{2mn}\sum_{x\in
X\setminus\\{1^{mn}\\}}\lvert a_{x}\rvert^{2}$ (29)
$\displaystyle=1-\frac{\varepsilon}{2mn}.$ (30)

∎

###  4.2 One-sided error reduction

With Lemma 4.1 (APT) in hand, we now show one-sided error reduction for
$\mathsf{pureQ\Pi}_{i}$, which suffices to obtain statements for all desired
classes subsequently in Theorem 1.4. For this, we define classes
$\mathsf{pureQ\Sigma}^{\mathsf{SEP}}_{i}$ and
$\mathsf{pureQ\Pi}^{\mathsf{SEP}}_{i}$ as identical to $\mathsf{pureQ\Sigma}$
and $\mathsf{pureQ\Pi}$, respectively, except the measurement POVM of the
verifier in the YES case must additionally be a separable operator relative to
the cuts between each of the $i$ proofs $\lvert\psi_{1}\rangle$ to
$\lvert\psi_{i}\rangle$. (This is analogous to $\mathsf{QMA}(2)$ versus
$\mathsf{QMA}^{\mathsf{SEP}}(2)$ [HM13].)

######  Lemma 4.2 (One-sided $\mathsf{pureQ\Pi}_{i}$ amplification).

If $i$ is even, then

$\mathsf{pureQ\Pi}_{i}(c,s)\subseteq\mathsf{pureQ\Pi}^{\mathsf{SEP}}_{i}\left(1-\frac{1}{e^{n}},1-\frac{1}{np(n)^{2}}\right),$
(31)

for all functions $c$ and $s$ such that $c-s\geq$ 1/p(n) for some polynomial
$p$.

###### Proof.

Let L =
$(L_{yes},{L}_{\mathrm{no}},{L}_{\mathrm{inv}})\in\mathsf{pureQ\Pi}_{i}(c,s)$,
with verifier $V$ taking in $i$ proofs denoted
$\lvert\psi_{1}\rangle,\ldots\lvert\psi_{i}\rangle$. Since $i$ is even, the
last proof, $\lvert\psi_{i}\rangle$, is existentially quantified. We define a
new verifier $V^{\prime}$ to decide $L$ in
$\mathsf{pureQ\Pi}_{i}(1-1/\exp,1-1/\operatorname{poly})$ as follows.
$V^{\prime}$ receives the following proofs from an honest prover:

$\displaystyle\left(\lvert\psi_{1}^{\prime}\rangle\otimes\cdots\otimes\lvert\psi_{i-1}^{\prime}\rangle\right)_{A}$
$\displaystyle=\left(\lvert\psi_{1}\rangle\otimes\cdots\otimes\lvert\psi_{i-1}\rangle\right)_{A}$
(32) $\displaystyle\lvert\psi_{i}^{\prime}\rangle_{BC}$
$\displaystyle=\left(\bigotimes_{j=1}^{i-1}\lvert\psi_{j}\rangle\right)_{B}^{\otimes
m}\otimes\lvert\psi_{i}\rangle_{C}^{\otimes m}$ (33)

for $m\in\Theta(n(c-s)^{-2})$, and where $A$, $B$ and $C$ are used to align
with the notation of Lemma 4.1 (which we use shortly). In words, the last
prover sends $m$ copies of the first $i-1$ proofs in register $B$, and $m$
copies of the last proof $\lvert\psi_{i}\rangle$ in register $C$. Then,
$V^{\prime}$ acts as follows:

  1. 1.

With probability 1/2, apply the APT (Lemma 4.1) between registers $A$ and $B$.
Accept iff the test accepts.

  2. 2.

With probability 1/2, apply verifier V $m$ times, taking one proof
$\lvert\psi_{i}\rangle$ from each respective subregister of $B$. Accept iff at
least $(c+s)/2$ measurements accept.

##### Correctness.

We now argue correctness.

_YES case._ Since the $i^{\mathrm{th}}$ prover is existentially quantified, it
sends the state in Equation 33. Thus, the APT accepts with certainty.
Similarly, for parallel repetition of V, each repetition is independent, hence
the overall verifier accepts with probability at least
$1-\exp(-(c-s)^{2}m/2)$, as desired.

_NO case._ Now the $i^{\mathrm{th}}$ prover is universally quantified, hence
it can send us a state entangled across $BC$.
Suppose the APT accepts with probability $1-\varepsilon$. By Lemma 4.1,

$\displaystyle\lvert\psi_{i}^{\prime}\rangle_{BC}=\alpha\left(\bigotimes_{j=1}^{i-1}\lvert\psi_{j}\rangle\right)_{B}^{\otimes
m}\lvert\phi\rangle_{C}+\beta\lvert\gamma\rangle_{BC}=:\alpha\lvert\eta\rangle_{B}\lvert\phi\rangle_{C}+\beta\lvert\gamma\rangle_{BC}\quad\text{
for }\quad\lvert\alpha\rvert^{2}\geq 1-2m(i-1)\varepsilon,$ (34)

for arbitrary states $\lvert\phi\rangle$ and $\lvert\gamma\rangle$ satisfying
that $\lvert\eta\rangle_{A}\lvert\phi\rangle_{B}$ is orthogonal to
$\lvert\gamma\rangle_{C}$. We have

$\displaystyle Pr[\text{parallel repetition of $V$ accepts
}\lvert\eta\rangle_{A}\lvert\phi\rangle_{B}]\leq e^{\frac{-(c-s)^{2}m}{2}}.$
(35)

We conclude the acceptance probability of $V^{\prime}$ is at most

$\displaystyle\frac{1}{2}\left((1-\varepsilon)+(1-2m(i-1)\varepsilon)e^{-(c-s)^{2}m/2}+2m(i-1)\varepsilon+2\sqrt{2m(i-1)\varepsilon+(2m(i-1))^{2}\varepsilon}\right)\leq
1-\frac{\varepsilon}{2}$ (36)

where the maximum is attained when $\varepsilon=\Theta(1/m(i-1))$.

Finally, that the measurement operator for the YES case is separable follows
via the argument of Harrow and Montanaro for $\mathsf{QMA}(2)$ amplification
[HM13], since our use of the APT is agnostic to whether proofs are universally
or existentially quantified. ∎

Lemma 4.2 now easily generalizes to cover all classies regarding
$\mathsf{pureQPH}$ we are concerned with: See 1.4

###### Proof.

Statement $1b$ is from Lemma 4.2, and $1a$ follows from $1b$ since we can get
a $\mathsf{pureQ\Sigma}_{i}$ verifier by flipping the answer of a
$\mathsf{pureQ\Pi}_{i}$ verifier corresponding to the complement of our
promise problem. The remaining cases are analogous: $2a$ follows from $1b$,
and $2b$ from $1a$. ∎

##  5 Upper and lower bounds on $\mathsf{pureQPH}$

###  5.1 Lower bound: $\mathsf{QCPH}$ versus $\mathsf{QPH}$

We first give a lower bound on $\mathsf{pureQPH}$, by showing that
alternatingly-quantified classical proofs can be replaced by pure-state
quantum proofs.

######  Theorem 5.1.

$\mathsf{QCPH}\subseteq\mathsf{pureQPH}$.

This follows immediately from the following lemma.

######  Lemma 5.2.

For all even $k\geq 2$, $\mathsf{QC\Pi}_{k}\subseteq\mathsf{pureQ\Sigma}_{k}$.

###### Proof.

That $k$ is even implies the $k$th proof is existentially quantified in the
YES case, a fact we will leverage. To begin, Let $V$ be a verifier for
$\mathsf{QC\Pi}_{k}$, so that in the YES case
$\forall_{1}x_{1}\dots\exists_{k}x_{k}:\Pr[V(x_{1},\dots,x_{k})=1]\geq c$ and
in the NO case $\exists x_{1}\dots\forall
x_{k}:\Pr[V(x_{1},\dots,x_{k})=1]\leq s$, where we may assume without loss of
generality that $c$ and $s$ are exponentially close to $1$ and $0$,
respectively. We construct a $\mathsf{pureQPH}$ verifier $V^{\prime}$ as
follows:

  * •

$V^{\prime}$ receives $k$ proofs,
$\lvert\psi_{1}\rangle\otimes\cdots\otimes\lvert\psi_{k}\rangle$.

  * •

The last proof $\lvert\psi_{k}\rangle$ consists of two registers denoted $A$
and $B$. We think of $A$ as containing $m$ copies of proofs $1,\dots,k-1$ (as
in the APT, Lemma 4.1), and $B$ as containing the $k$th proof for $V$,
$x_{k}$.

  * •

$V^{\prime}$ acts as follows:

    1. 1.

With probability $1/2$, run the APT (Lemma 4.1), and accept if and only if the
APT accepts.

    2. 2.

With probability $1/2$, measure proofs
$\lvert\psi_{1}\rangle\otimes\cdots\otimes\lvert\psi_{k-1}\rangle$ in the
standard basis to obtain strings $x_{1},\ldots,x_{k-1}$, respectively,
similarly measure all copies of these proofs in $A$, and finally measure $B$
in the standard basis to obtain $x_{k,B}$. Let
$U={\left\\{1,3\ldots,k-1\right\\}}$ denote the indices of universally
quantified proofs (in the YES case). Then:

      1. (a)

If there exists an $i\in[k-1]$ such that the strings obtained by measuring all
copies of $\lvert\psi_{i}\rangle$ did _not_ equal $x_{i}$, let $i$ denote the
minimal such index. Accept if $i\in U$, and reject otherwise.

      2. (b)

Otherwise, simulate $V(x_{1},\dots,x_{k-1},x_{k,B})$.

##### Correctness strategy.

Since we are trying to simulate $\mathsf{QC\Pi}_{k}$, ideally we want all
proofs to be strings. This can be assumed without loss of generality for
existentially quantified proofs, but not for universally quantified proofs,
which can be set to any pure state by definition of $\mathsf{pureQ\Pi}_{k}$.
So, for any $i\in U$, write $\lvert\psi_{i}\rangle=\sum_{x}\alpha_{i,x}\lvert
x\rangle$, where we view $\lvert\alpha_{i,x}\rvert^{2}$ as a distribution over
strings $x$ for proof $i$. Denote for any $i\in U$ by $x^{*}_{i}$ the
amplitude of highest weight, i.e.
$x^{*}_{i}=\operatorname*{arg\,max}_{x}{\lvert\alpha_{i,x}\rvert}$ (ties
broken arbitrarily). The key idea is that the existentially quantified proof
at index $i+1$ will now send string $y_{i+1}^{*}$, where $y_{i+1}^{*}$ is the
same string that a prover for the _original_ $\mathsf{QC\Pi}_{k}$ verifier $V$
would have sent in response to $x^{*}_{i}$ on proof $i$. (For clarity, if
$i+1=k$, then $y_{i+1}^{*}$ is sent in register $B$.)

_YES case._ Since the $k$th proof is existentially quantified, for Step 1
(APT), we may assume all copies in $\lvert\psi_{k,A}\rangle$ (the state in
register $A$) are correctly set, so the APT accepts with probability $1$,
leaving all proofs invariant. As for Step 2, for each $i\in U$, let $X_{i}$ be
the random variable resulting from measuring $\lvert\psi_{i}\rangle$ in the
standard basis, and likewise $X_{ij}$ the random variables for the $j$th copy
of $\lvert\psi_{i}\rangle$ in register $A$. The verification can now fail in
one of two ways:

  1. 1.

There exists an $i\in U$ such that we did not measure the “right” result, i.e.
$X_{i}\neq x_{i}^{*}$, but that all measured copies of $\lvert\psi_{i}\rangle$
returned the same string, i.e. $\forall j$ $X_{ij}=X_{i}$. In this case, our
strategy for setting the existentially quantified proof $i+1$ is not
necessarily the correct response to $X_{i}$. Thus, when Step $2(b)$ is run, we
have no guarantee for the acceptance probability of $V$.

  2. 2.

Measuring all $i\in U$ yields the desired outcomes $x_{i}^{*}$ (as well as
$\forall j$ $X_{ij}=X_{i}$), but $V$ nevertheless rejects due to imperfect
completeness, i.e. $c<1$.

Combining these, via the union bound we thus have for Step 2 that

$\displaystyle\Pr[\text{reject}]$ $\displaystyle\leq\Pr[\;\exists i\in
U:X_{i}\neq x^{*}_{i}\text{ AND }\forall ij:X_{i}=X_{ij}\;]+(1-c)$ (37)
$\displaystyle\leq\min\\{p,1-p\\}^{m}+1-c$ (38) $\displaystyle\leq
2^{-m}+1-c,$ (39)

where $p:=\max_{i}\lvert\alpha_{i,x_{i}}\rvert^{2}$, since $\Pr[X_{i}\neq
x^{*}_{i}]=\Pr[X_{ij}\neq x^{*}_{i}]\leq\max{\left\\{p,1-p\right\\}}$ because
$\lvert\alpha_{i,y}\rvert^{2}\leq 1-p$ for $y\neq x^{*}_{i}$. Since we assumed
the APT accepts with perfect probability, we conclude $V^{\prime}$ accepts
with probability $\geq\frac{1}{2}+\frac{1}{2}(c-2^{-m})=:c^{\prime}$. (As an
aside, recall $c$ is exponentially close to $1$.)

_NO case._ The analysis is more subtle in this case, as the set of indices
$U={\left\\{1,3,\ldots,k-1\right\\}}$ now refers to _existentially_ quantified
proofs. Thus, in Step 2(a) when $V^{\prime}$ accepts iff $i\in U$, this now
means it accepts on existentially quantified proofs. This is because
$V^{\prime}$ does not know whether it is in a YES or NO case. For the same
reason, the actions and role of the final proof $\lvert\psi_{k}\rangle$ on
registers $A$ and $B$ remain the same, even though it is now universally
quantified. Finally, the strategy of any existential prover $i\in U$ is the
same as the YES case: Prover $i$ sends the optimal response $y_{i}^{*}$ to
universally quantified proof $x_{i-1}^{*}$. (If $i=1$, then there is no
universal proof to condition on for $\lvert\psi_{1}\rangle$.)

To proceed, assume for now that the APT would have succeeded in Step 1 with
certainty. In Step 2, define again for all $i\in U$, $X_{i}$ the random
variable resulting from measuring $\lvert\psi_{i}\rangle$ in the standard
basis, and $X_{ij}$ the random variables for the $j$th copy of
$\lvert\psi_{i}\rangle$ in register $A$. The verifier can now fail in one of
two ways, the first of which differs significantly from the YES case:

  1. 1.

There exists $i\in U$ such that $X_{i}$ mismatched one of its copies in $A$,
i.e. $\exists j$ such that $X_{i}\neq X_{ij}$. _A priori_ , this seems like a
problem — since $\lvert\psi_{k}\rangle$ is universally quantified, most
choices of $\lvert\psi_{k}\rangle$ will cause a mismatch with $X_{i}$ with
high probability, causing $V^{\prime}$ to accept with high probability. The
crucial insight is that, in order for
$\lvert\psi_{1}\rangle\otimes\cdots\otimes\lvert\psi_{k}\rangle$ to pass the
APT, it must essentially set each copy of $\lvert\psi_{i}\rangle$ to string
$y_{i}^{*}$. Thus, measuring the $A$ register is highly unlikely to produce
mismatches on existentially quantified proofs!

  2. 2.

Measuring all $i\in U$ will yield the desired outcomes $y_{i}^{*}$, since $U$
is existentially quantified. If in addition $\forall j$ $X_{ij}=X_{i}$,
running $V$ may nevertheless accept due to imperfect soundness, i.e. $s>0$.

Then, by a similar argument as for the YES case that in Step 2, in which we
first assume the APT passes with certainty, $\Pr[\text{accept}]\leq 2^{-m}+s.$
Now, let us factor in the probability of the APT of Step 1 passing. Assume the
APT accepts with probability $\geq 1-\varepsilon/2mn$. By Lemma 4.1,

$\langle\psi_{k}\rvert(\lvert\psi_{1},\dots,\psi_{k-1}\rangle\langle\psi_{1},\dots,\psi_{k-1}\rvert_{A}\otimes
I_{B})\lvert\psi_{k}\rangle\geq 1-\varepsilon.$ (40)

Let $\\{\lvert\beta_{i}\rangle\\}$ be an orthonormal basis of register $A$
with $\lvert\beta_{1}\rangle=\lvert\psi_{1},\dots,\psi_{n-1}\rangle$. Then we
can write
$\lvert\psi_{n}\rangle=\sum_{i}\alpha_{i}\lvert\beta_{i}\rangle_{A}\lvert\gamma_{i}\rangle_{B}$
with $\lvert\alpha_{1}\rvert^{2}\geq 1-\varepsilon$. Hence, $V^{\prime}$
accepts with probability at most

$\frac{1}{2}\left(1-\frac{\varepsilon}{2mn}\right)+\frac{1}{2}\left(\varepsilon+(1-\varepsilon)s\right)\leq
1-\frac{1}{4mn}+s=:s^{\prime},$ (41)

where the first inequality follows because, without loss of generality, we may
assume $\varepsilon\leq 1/2$, as otherwise the prover cannot hope to succeed
make $V^{\prime}$ accept with probability greater than $3/4$ (whereas
$c^{\prime}\approx 1$). Finally, we can choose $c,s,m$ such that
$c^{\prime}-s^{\prime}\geq 1/\operatorname{poly}$. ∎

###  5.2 Upper bound

To complement Section 5.1, we next give a simple but non-trivial upper bound
on $\mathsf{pureQPH}$, which may be viewed as an “exponential analogue” of
Toda’s theorem. For this, let $\mathsf{NP}^{k}$ denote a tower of
$\mathsf{NP}$ oracles of height $k$. (For example,
$\mathsf{NP}^{1}=\mathsf{NP}$ and
$\mathsf{NP}^{2}=\mathsf{NP}^{\mathsf{NP}}$.) Define $\mathsf{NEXP}^{k}$
analogously, by for a tower of $\mathsf{NEXP}$ oracles. In [GSSSY22], it was
observed that $\mathsf{Q\Sigma}_{i}\subseteq\mathsf{NEXP}^{i}$. Here, we show
a sharper bound.

######  Theorem 5.3.

$\mathsf{pureQPH}\subseteq\mathsf{EXP}^{\mathsf{PP}}$.

We prove this using a sequence of statements.

######  Observation 5.4.

$\mathsf{pureQ\Sigma}_{i}\subseteq\mathsf{NEXP}^{\mathsf{NP}^{i-1}}$.

###### Proof.

Replace all proofs by by their exponential-size classical description (up to
additive additive inverse exponential additive error in the entries), and
simulate the verifier’s action on the proofs via exponential-time matrix
multiplication. The standard proof technique for showing
$\Sigma_{i}^{p}\subseteq\mathsf{NP}^{i}$ now applies, except we only require
$\mathsf{NEXP}$ at the base level of the oracle tower, i.e.
$\mathsf{NEXP}^{\mathsf{NP}^{i-1}}$, since an exponential time base can
“inflate” or pad the instance size for its oracle exponentially. ∎

For comparison, the onbserved bound in [GSSSY22] of
$\mathsf{Q\Sigma}_{i}\subseteq\mathsf{NEXP}^{i}$ is overkill, since it allows
the first NEXP oracle can use _double_ exponential time to process its
exponetial size input.

######  Observation 5.5.

$\mathsf{NEXP}\subseteq\mathsf{EXP}^{\mathsf{NP}}$.

###### Proof.

Since using an exponential time machine we can “inflate” the instance size to
exponential, an $\mathsf{NP}$ machine can thereafter simulate the
$\mathsf{NEXP}$ computation on the inflated instance size. The $\mathsf{EXP}$
machine just returns the answer of the $\mathsf{NP}$ oracle. ∎

######  Observation 5.6.

$\mathsf{NEXP}^{O}\subseteq\mathsf{EXP}^{\mathsf{NP}^{O}}$ for an oracle to
any language $O$.

###### Proof.

It is easy to see that the argument in Observation 5.5 relativizes, since the
$\mathsf{NP}$ oracle to the $\mathsf{EXP}$ machine can make the
$\mathsf{NEXP}$ queries directly to the oracle $O$. ∎

######  Observation 5.7.

$\mathsf{EXP}^{\mathsf{P}^{\mathsf{PP}}}\subseteq\mathsf{EXP}^{\mathsf{PP}}$.

###### Proof.

The $\mathsf{EXP}$ machine can make at most exponentially many queries to the
its oracle, each of which can be of size at most exponential in the size of
the input. Therefore an $\mathsf{EXP}$ machine can simulate the action of a
$\mathsf{P}^{\mathsf{PP}}$ machine (even on an exponential sized query) by
making queries to a $\mathsf{PP}$ oracle while simulating the action of a
$\mathsf{P}$ machine (which will only take time polynomial in size of the
query). ∎

######  Theorem 5.8.

For all $i\geq 1$, $\mathsf{Q\Sigma}_{i}\subseteq\mathsf{EXP}^{\mathsf{PP}}$.

###### Proof.

By Observation 5.4, Observation 5.6 and Toda’s Theorem [Tod91],

$\displaystyle\mathsf{Q\Sigma}_{i}\subseteq\mathsf{NEXP}^{\mathsf{NP}^{i-1}}\subseteq\mathsf{EXP}^{\mathsf{NP}^{i}}\subseteq\mathsf{EXP}^{\mathsf{P}^{\mathsf{PP}}}.$
(42)

The claim now follows from Observation 5.7. ∎

Theorem 5.3 now follows immediately from Theorem 5.8.

## Acknowledgements

We thank Chirag Falor, Shu Ge, Anand Natarajan, Sabee Grewal, and Justin Yirka
for the pleasure of productive discussions during the concurrent development
of our works. This work was completed in part while AA was a student at Indian
Institute of Technology Delhi and in part while visiting Paderborn University.
SG was supported by the DFG under grant numbers 450041824 and 432788384, the
BMBF within the funding program “Quantum Technologies - from Basic Research to
Market” via project PhoQuant (grant number 13N16103), and the project “PhoQC”
from the programme “Profilbildung 2020”, an initiative of the Ministry of
Culture and Science of the State of Northrhine Westphalia. VK was supported by
the Pankaj Gupta Fellowship at IIT Delhi.

## References

  * [AA11] Scott Aaronson and Alex Arkhipov  “The Computational Complexity of Linear Optics”  In _Forty-Third Annual ACM Symposium on Theory of Computing_ , STOC ’11  New York, NY, USA: ACM, 2011, pp. 333–342  DOI: 10.1145/1993636.1993682
  * [ABBS22] Dorit Aharonov, Michael Ben-Or, Fernando G.S.L. Brandão and Or Sattath  “The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings”  In _Quantum_ 6 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2022, pp. 668  DOI: 10.22331/q-2022-03-17-668
  * [ACGK17] Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu and Elham Kashefi  “On the implausibility of classical client blind quantum computing”  In _CoRR_ abs/1704.08482, 2017  arXiv: http://arxiv.org/abs/1704.08482
  * [AD14] Scott Aaronson and Andrew Drucker  “A Full Characterization of Quantum Advice”  In _SIAM J. Comput._ 43.3, 2014, pp. 1131–1183  DOI: 10.1137/110856939
  * [AIK22] Scott Aaronson, DeVon Ingram and William Kretschmer  “The Acrobatics of BQP”  In _37th Computational Complexity Conference (CCC 2022)_ 234, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 20:1–20:17  DOI: 10.4230/LIPIcs.CCC.2022.20
  * [AKN98] Dorit Aharonov, Alexei Kitaev and Noam Nisan  “Quantum Circuits with Mixed States”  In _Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing_ , STOC ’98  New York, NY, USA: Association for Computing Machinery, 1998, pp. 20–30  DOI: 10.1145/276698.276708
  * [AKSS95] Vikraman Arvind, Johannes Köbler, Uwe Schöning and Rainer Schuler  “If NP has polynomial-size circuits, then MA = AM”  In _Theoretical Computer Science_ 137.2, 1995, pp. 279–282  DOI: https://doi.org/10.1016/0304-3975(95)91133-B
  * [BCGKT95] Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan and Christino Tamon  “Oracles and Queries That Are Sufficient for Exact Learning”  In _Electron. Colloquium Comput. Complex._ TR95-015, 1995  ECCC: https://eccc.weizmann.ac.il/eccc-reports/1995/TR95-015/index.html
  * [BFNV19] Adam Bouland, Bill Fefferman, Chinmay Nirkhe and Umesh Vazirani  “On the Complexity and Verification of Quantum Random Circuit Sampling”  In _Nature Physics_ 15.2 Nature Publishing Group, 2019, pp. 159–163  DOI: 10.1038/s41567-018-0318-2
  * [BGK23] Lennart Bittel, Sevag Gharibian and Martin Kliesch  “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate”  In _38th Computational Complexity Conference (CCC 2023)_ 264, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, pp. 34:1–34:24  DOI: 10.4230/LIPIcs.CCC.2023.34
  * [BJS10] Michael J. Bremner, Richard Jozsa and Dan J. Shepherd  “Classical Simulation of Commuting Quantum Computations Implies Collapse of the Polynomial Hierarchy”  In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 467.2126 Royal Society, 2010, pp. 459–472  DOI: 10.1098/rspa.2010.0301
  * [Cai01] Jin-yi Cai  “$S^{\mbox{p}}_{\mbox{2}}\subseteq ZPP^{\mbox{NP}}$”  In _42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA_ IEEE Computer Society, 2001, pp. 620–629  DOI: 10.1109/SFCS.2001.959938
  * [Can96] Ran Canetti  “More on BPP and the Polynomial-Time Hierarchy”  In _Inf. Process. Lett._ 57.5, 1996, pp. 237–241  DOI: 10.1016/0020-0190(96)00016-6
  * [CR06] Venkatesan T. Chakaravarthy and Sambuddha Roy  “Oblivious Symmetric Alternation”, STACS’06  Marseille, France: Springer-Verlag, 2006, pp. 230–241  DOI: 10.1007/11672142˙18
  * [FGN23] Chirag Falor, Shu Ge and Anand Natarajan  “A Collapsible Polynomial Hierarchy for Promise Problems”  In _CoRR_ abs/2311.12228, 2023  DOI: 10.48550/ARXIV.2311.12228
  * [FSS84] Merrick Furst, James B. Saxe and Michael Sipser  “Parity, Circuits, and the Polynomial-Time Hierarchy”  In _Mathematical systems theory_ 17.1, 1984, pp. 13–27  DOI: 10.1007/BF01744431
  * [GK12] Sevag Gharibian and Julia Kempe  “Hardness of Approximation for Quantum Problems”  In _Automata, Languages, and Programming_ , Lecture Notes in Computer Science  Berlin, Heidelberg: Springer, 2012, pp. 387–398  DOI: 10.1007/978-3-642-31594-7˙33
  * [Gol06] Oded Goldreich  “On Promise Problems: A Survey”  In _Theoretical Computer Science: Essays in Memory of Shimon Even_ , Lecture Notes in Computer Science  Berlin, Heidelberg: Springer, 2006, pp. 254–290  DOI: 10.1007/11685654˙12
  * [GSSSY22] Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram and Justin Yirka  “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)”  In _computational complexity_ 31.2, 2022, pp. 13  DOI: 10.1007/s00037-022-00231-8
  * [GY23] Sabee Grewal and Justin Yirka  “The Entangled Quantum Polynomial Hierarchy Collapses”  In _CoRR_ , 2023
  * [HM13] Aram W. Harrow and Ashley Montanaro  “Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization”  In _Journal of the ACM_ 60.1, 2013, pp. 3:1–3:43  DOI: 10.1145/2432622.2432625
  * [INNRY22] Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao and Henry Yuen  “Quantum Search-To-Decision Reductions and the State Synthesis Problem”  In _37th Computational Complexity Conference (CCC 2022)_ 234, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 5:1–5:19  DOI: 10.4230/LIPIcs.CCC.2022.5
  * [JC17] J. Lockhart and C. E. González-Guillén  “Quantum State Isomorphism”  In _arXiv preprint arXiv:1709.09622_ , 2017  arXiv:1709.09622
  * [JW09] Rahul Jain and John Watrous  “Parallel Approximation of Non-interactive Zero-sum Quantum Games”  In _Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009_ IEEE Computer Society, 2009, pp. 243–253  DOI: 10.1109/CCC.2009.26
  * [KL80] Richard M. Karp and Richard J. Lipton  “Some Connections Between Nonuniform and Uniform Complexity Classes”  In _Twelfth Annual ACM Symposium on Theory of Computing_ , STOC ’80  New York, NY, USA: ACM, 1980, pp. 302–309  DOI: 10.1145/800141.804678
  * [KMY01] Hirotada Kobayashi, Keiji Matsumoto and Tomoyuki Yamakami  “Quantum Certificate Verification: Single versus Multiple Quantum Certificates”  arXiv, 2001  DOI: 10.48550/arXiv.quant-ph/0110006
  * [KW98] Johannes Köbler and Osamu Watanabe  “New Collapse Consequences of NP Having Small Circuits”  In _SIAM J. Comput._ 28.1, 1998, pp. 311–324  DOI: 10.1137/S0097539795296206
  * [Lau83] Clemens Lautemann  “BPP and the Polynomial Hierarchy”  In _Information Processing Letters_ 17.4, 1983, pp. 215–217  DOI: 10.1016/0020-0190(83)90044-3
  * [MKB05] Florian Mintert, Marek Kuś and Andreas Buchleitner  “Concurrence of Mixed Multipartite Quantum States”  In _Physical Review Letters_ 95.26 American Physical Society, 2005, pp. 260502  DOI: 10.1103/PhysRevLett.95.260502
  * [RS98] Alexander Russell and Ravi Sundaram  “Symmetric Alternation Captures BPP”  In _Comput. Complex._ 7.2, 1998, pp. 152–162  DOI: 10.1007/S000370050007
  * [Sip83] Michael Sipser  “A Complexity Theoretic Approach to Randomness”  In _Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing_ , STOC ’83  New York, NY, USA: Association for Computing Machinery, 1983, pp. 330–335  DOI: 10.1145/800061.808762
  * [Sto76] Larry J. Stockmeyer  “The Polynomial-Time Hierarchy”  In _Theoretical Computer Science_ 3.1, 1976, pp. 1–22  DOI: http://dx.doi.org/10.1016/0304-3975(76)90061-X
  * [SW22] Mehdi Soleimanifar and John Wright  “Testing Matrix Product States”  arXiv, 2022  DOI: 10.48550/arXiv.2201.01824
  * [Tod91] Seinosuke Toda  “PP Is as Hard as the Polynomial-Time Hierarchy”  In _SIAM Journal on Computing_ 20.5 Society for Industrial and Applied Mathematics, 1991, pp. 865–877  DOI: 10.1137/0220053
  * [VV86] L.. Valiant and V.. Vazirani  “NP Is as Easy as Detecting Unique Solutions”  In _Theoretical Computer Science_ 47, 1986, pp. 85–93  DOI: 10.1016/0304-3975(86)90135-0
  * [Yam02] Tomoyuki Yamakami  “Quantum NP and a Quantum Hierarchy”  In _Foundations of Information Technology in the Era of Network and Mobile Computing: IFIP 17th World Computer Congress — TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science (TCS 2002) August 25–30, 2002, Montréal, Québec, Canada_ , IFIP — The International Federation for Information Processing  Boston, MA: Springer US, 2002, pp. 323–336  DOI: 10.1007/978-0-387-35608-2˙27