On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity

Grewal, Sabee; Rudolph, Dorian

doi:10.4230/LIPIcs.ICALP.2026.103

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity

Sabee Grewal

The University of Texas at Austin, TX, USA Dorian Rudolph

Department of Computer Science and Institute for Photonic Quantum Systems (PhoQS), Paderborn University, Germany

Abstract

We prove several new results concerning the pure quantum polynomial hierarchy $\mathsf{pureQPH}$ . First, we show that $\mathsf{QMA}(2)\subseteq\mathsf{pureQ\Sigma_{2}}$ , i.e., two unentangled existential provers can be simulated by competing existential and universal provers. We further prove that $\mathsf{pureQ\Sigma_{2}}\subseteq\mathsf{Q\Sigma_{3}}\subseteq\mathsf{NEXP}$ . Second, we give an error reduction result for $\mathsf{pureQPH}$ , and, as a consequence, prove that $\mathsf{pureQPH}=\mathsf{QPH}$ . A key ingredient in this result is an improved dimension-independent disentangler. Finally, we initiate the study of quantified Hamiltonian complexity, the quantum analogue of quantified Boolean formulae. We prove that the quantified pure sparse Hamiltonian problem is $\mathsf{pureQ\Sigma_{i}}$ -complete. By contrast, other natural variants (pure/local, mixed/local, and mixed/sparse) admit nontrivial containments but fail to be complete under known techniques. For example, we show that the $\exists\forall$ -mixed local Hamiltonian problem lies in $\mathsf{NP}^{\mathsf{QMA}}\cap\mathsf{coNP}^{\mathsf{QMA}}$ .

Keywords and phrases:

quantum complexity theory, quantum polynomial hierarchy, pure quantum polynomial hierarchy, QPH, QMA(2), quantum proof systems, interactive proofs, quantified Hamiltonian complexity, local Hamiltonian problem, sparse Hamiltonians, disentanglers

Category:

Track A: Algorithms, Complexity and Games

Funding:

Sabee Grewal: SG was supported in part by an IBM PhD Fellowship.

Dorian Rudolph: DR was supported in part by the DFG under grant number 432788384.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum complexity theory ; Theory of computation

\rightarrow

Problems, reductions and completeness

Related Version:

Full Version: https://arxiv.org/abs/2510.06522 [17]

Acknowledgements:

We thank Justin Yirka, Sevag Gharibian, and William Kretschmer for helpful conversations. This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing.

DOI:

10.4230/LIPIcs.ICALP.2026.103

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The polynomial hierarchy ( $\mathsf{PH}$ ) [32] plays a central role in complexity theory. It has been instrumental in understanding the power of computational models such as $\mathsf{BPP}$ [31, 28], low-depth classical circuits [14], counting classes [34], and non-uniform computation [24]. More recently, $\mathsf{PH}$ has been used to provide evidence for the hardness of simulating quantum circuits and has underpinned theoretical foundations for quantum supremacy demonstrations [8, 1, 7].

Quantum generalizations of the polynomial hierarchy have been explored intermittently over the past two decades [36, 22, 15, 13, 18, 2, 5], and have recently begun to find broader applications within quantum complexity theory [3]. Given the central role of $\mathsf{PH}$ , it is natural to study its quantum analogues and their role in quantum complexity theory.

As with most prior work, we focus on the quantifier-based definitions of the quantum polynomial hierarchy. In this setting, the $i$ th level, denoted $\mathsf{Q\Sigma_{i}}$ , consists of promise problems that can be decided by a quantum polynomial-time verifier interacting with $i$ rounds of quantum proofs, where the quantifiers alternate between existential and universal. More concretely, $\mathsf{Q\Sigma_{i}}$ (resp. $\mathsf{Q\Pi_{i}}$ ) consists of problems where the interaction begins with an existential (resp. universal) quantum proof, followed by alternating quantifiers over polynomial-size quantum states, with the verifier required to accept with high probability in the YES case and reject in the NO case. The union over all levels defines the quantum polynomial hierarchy $\mathsf{QPH}$ . The pure quantum polynomial hierarchy $\mathsf{pureQPH}$ is defined analogously, except that the quantified quantum proofs are restricted to be pure states.¹¹1There is also a third natural variant: the entangled quantum polynomial hierarchy, where the provers are allowed to entangle their proofs across rounds. Grewal and Yirka [18] showed that this variant collapses to its second level.

A central challenge in defining a quantum analogue of the polynomial hierarchy is determining the “right” formulation among several possible variants. This question has been raised before [15, 2], but it remains unresolved. This work tackles the problem directly: we prove several new results about $\mathsf{pureQPH}$ that, taken together, provide compelling evidence that it is the most natural quantifier-based definition of the quantum polynomial hierarchy.

At the same time, each of our results is interesting in its own right. Our first contribution gives a new upper bound on $\mathsf{QMA}(2)$ , placing it in the second level of $\mathsf{pureQPH}$ . This shows that two existential provers can be simulated by competing provers and recasts $\mathsf{QMA}(2)$ as a min-max optimization problem (rather than a nonconvex optimization over separable states). Our second and most technical result is an error reduction procedure for $\mathsf{pureQPH}$ , which in turn implies $\mathsf{pureQPH}=\mathsf{QPH}$ ; the key tool is a new dimension-independent disentangler, extending recent work of Jeronimo and Wu [21]. Finally, we initiate the study of quantified Hamiltonian complexity, a quantum analogue of quantified Boolean formulae. These problems capture robust ground-state questions, such as whether there exists a state on one subsystem that ensures the overall system remains low-energy regardless of perturbations to the rest.

1.1 Our Results

Our first result establishes that $\mathsf{QMA(2)}\subseteq\mathsf{pureQ\Sigma_{2}}\subseteq\mathsf{Q\Sigma_{3}}$ , i.e., that the second level of $\mathsf{pureQPH}$ is sandwiched between $\mathsf{QMA(2)}$ and the third level of $\mathsf{QPH}$ . Prior work has shown that $\mathsf{Q\Sigma_{3}}\subseteq\mathsf{NEXP}$ [15].

Theorem 1 (Combination of Theorems 14 and 15).

$\mathsf{QMA}(2)\subseteq\mathsf{pureQ\Sigma_{2}}\subseteq\mathsf{Q\Sigma_{3}}% \subseteq\mathsf{NEXP}$ .

Informally, $\mathsf{QMA(2)}$ is the class of promise problems decidable given two unentangled quantum proofs. Since its introduction in 2001 [27], it has been known that $\mathsf{QMA}\subseteq\mathsf{QMA(2)}\subseteq\mathsf{NEXP}$ . However, whether $\mathsf{QMA(2)}$ is “closer” to $\mathsf{QMA}$ or to $\mathsf{NEXP}$ remains a central open problem in quantum complexity theory.

What Theorem 1 contributes to this question is nuanced. Our result shows that $\mathsf{QMA(2)}$ can be captured by a one-round quantum refereed-game model with an existential prover followed by an (adversarial) universal prover who has perfect knowledge of the first message. Conceptually, this recasts the nonconvex “maximize over separable witnesses” view of $\mathsf{QMA(2)}$ as a single alternation

\max_{\ket{\psi}}\min_{\ket{\phi}}\mathrm{tr}\left(\Pi(\ket{\psi}\!\!\bra{\psi% }\otimes\ket{\phi}\!\!\bra{\phi})\right),

that is, a saddle-point optimization problem. This perspective opens the door to applying techniques from min–max optimization, game theory, and the study of quantum refereed games to better understand the true power of $\mathsf{QMA(2)}$ . Moreover, in closely related models where provers are allowed mixed-state strategies, the game value can be approximated in $\mathsf{PSPACE}$ [20]. We view this as qualitative evidence that $\mathsf{QMA(2)}$ is perhaps not equal to $\mathsf{NEXP}$ .

Our second result is an error reduction result for $\mathsf{pureQPH}$ , resolving an open problem of Gharibian et al. [15] and Agarwal et al. [2].

Theorem 2 (Restatement of Theorem 16).

$\mathsf{pureQ\Sigma_{r}}\subseteq\mathsf{Q\Sigma_{7r}}(c^{\prime},s^{\prime})$ with $c^{\prime}\geq 1-1/q(n)$ and $s^{\prime}\leq 1/q(n)$ , where $q$ is an arbitrary polynomial.

That is, we show that any protocol in $\mathsf{pureQ\Sigma_{r}}$ can be converted into one in $\mathsf{Q\Sigma_{7r}}$ whose completeness (resp. soundness) is $1/\mathrm{poly}$ -close to $1$ (resp. $0$ ) at the cost of a constant-factor increase in the number of alternations.

Observe that Theorem 2 says that every level of $\mathsf{pureQPH}$ is contained in some level of $\mathsf{QPH}$ , i.e., that $\mathsf{pureQPH}\subseteq\mathsf{QPH}$ . The reverse containment $\mathsf{pureQPH}\supseteq\mathsf{QPH}$ is easy to see: the provers can simply send purifications of the proofs in the $\mathsf{QPH}$ protocol. Hence, the following corollary is immediate.

Corollary 3 (Restatement of Corollary 17).

$\mathsf{pureQPH}=\mathsf{QPH}$ .

We emphasize that the equivalence of $\mathsf{pureQPH}$ and $\mathsf{QPH}$ is far from obvious. To illustrate, consider the following simple two-player game: Player 1 sends a state to the verifier, and Player 2, after learning Player 1’s message, must send the same state.²²2All of the protocols and proof systems we study can be viewed as games of perfect information, meaning that each prover (or player) is fully aware of all moves made in the game so far. Indeed, even $\mathsf{PH}$ has this game-theoretic interpretation. The verifier runs a SWAP test, declaring “Player 1 wins” if the test fails and “Player 2 wins” if it passes. If the players are restricted to sending pure states, then Player 2 can always win with probability $1$ , by perfectly replicating Player 1’s state. By contrast, if mixed states are allowed, Player 1 can send the maximally mixed state, in which case Player 2’s winning probability drops to approximately $1/2$ .

Indeed, Theorems 2 and 3 are our most technically involved results. To establish them, we construct a new dimension-independent disentangler.

Lemma 4 (Restatement of Lemma 23).

Let $\mathcal{H}=\mathbb{C}^{d_{1}}\otimes\dotsm\otimes\mathbb{C}^{d_{s}}$ , $k\in\mathbb{N}$ , and $\delta>0$ . There exist parameters $\ell\in\mathrm{poly}(\delta^{-1},k),m\in O(\delta^{-2})$ and a quantum channel

\Gamma\colon\mathcal{D}(\mathcal{H}^{\otimes 4\ell})\to\mathcal{D}(\mathcal{H}% ^{\otimes k}),

with the following properties: for all states $\rho_{1},\rho_{2},\rho_{3},\rho_{4}\in\mathcal{D}(\mathcal{H}^{\otimes\ell})$ , there exists a distribution $\{p_{i}\}_{i=1}^{m}$ over product states $\ket{\zeta_{i}}=\ket{\zeta_{i,1}}\otimes\dots\otimes\ket{\zeta_{i,s}},\;\ket{% \zeta_{i,j}}\in\mathbb{C}^{d_{j}}$ such that

\left\lVert\Gamma(\rho_{1}\otimes\rho_{2}\otimes\rho_{3}\otimes\rho_{4})-\sum_% {i=1}^{m}p_{i}\ket{\zeta_{i}}\!\!\bra{\zeta_{i}}^{\otimes k}\right\rVert_{1}% \leq\delta.

(1)

Furthermore, for every pure product state $\ket{\psi}=\ket{\psi_{1}}\otimes\dotsm\otimes\ket{\psi_{s}}\in\mathcal{H}$ , $\Gamma(\ket{\psi}\!\!\bra{\psi}^{\otimes 4\ell})=\ket{\psi}\!\!\bra{\psi}^{% \otimes k}$ .

Our construction builds on the disentangler of Jeronimo and Wu [21], but strengthens it in a key way. While the Jeronimo-Wu channel guarantees closeness to a convex combination of product states, our disentangler ensures that the output is close to a convex combination of only $m=O(\delta^{-2})$ product states, where $\delta$ is a parameter that can be chosen. In other words, not only is the disentangled output structured, but it is also supported on a small set of product states, which is crucial for our amplification procedure. The tradeoff is that we use four unentangled input states whereas the Jeronimo-Wu channel only uses two.

Our final set of results concerns quantified Hamiltonian complexity. We study natural generalizations of the local Hamiltonian problem, which asks: given a local Hamiltonian $H$ , decide whether there exists a state $\ket{\psi}$ with energy $\braket{\psi|H|\psi}\leq a$ , or if instead all states satisfy $\braket{\psi|H|\psi}\geq b$ , promised one of these is the case. The local Hamiltonian problem is well known to be $\mathsf{QMA}$ -complete [26, 25].

We extend this to the quantified setting, in analogy with quantified Boolean formulae [6]. For instance, the $\exists\forall$ -mixed local Hamiltonian problem ( $\exists\forall$ -MLH) is defined as follows: given a local Hamiltonian $H$ , decide whether there exists a mixed state $\rho$ such that for all mixed states $\sigma$ , $\mathrm{tr}(H(\rho\otimes\sigma))\leq a$ , or if instead, for all $\rho$ , there exists a $\sigma$ such that $\mathrm{tr}(H(\rho\otimes\sigma))\geq b$ , promised one of these is the case. For this problem, we obtain the following containment:

Proposition 5 (Restatement of Corollary 31).

The $\exists\forall$ -mixed local Hamiltonian problem is in $\mathsf{NP}^{\mathsf{QMA}}\cap\mathsf{coNP}^{\mathsf{QMA}}$ .

Since no complete problems are known for $\mathsf{NP}\cap\mathsf{coNP}$ , we find it implausible that $\exists\forall$ -MLH is complete for $\mathsf{NP}^{\mathsf{QMA}}\cap\mathsf{coNP}^{\mathsf{QMA}}$ . Moreover, hardness for either $\mathsf{NP}^{\mathsf{QMA}}$ or $\mathsf{coNP}^{\mathsf{QMA}}$ would collapse these two classes, which also seems unlikely.

In addition to the mixed/local case, we also study the mixed/sparse, pure/local, and pure/sparse variants. These are defined analogously: the “sparse” condition means the Hamiltonian is row-sparse rather than local, while the “pure” versus “mixed” distinction specifies whether the quantified states are pure or mixed. For the mixed/sparse and pure/local variants, our findings parallel the mixed/local case: we can establish containments but are unable to prove hardness. In fact, existing circuit-to-Hamiltonian constructions appear inadequate for obtaining hardness in these settings, suggesting that either new techniques would be required or that these variants fail to be complete problems for any class studied in this work.

The pure/sparse variant stands out as the only case where we can establish a completeness result. To capture this formally, we define the $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ and $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ problems (generalizing the $\mathsf{QMA(2)}$ -complete separable sparse Hamiltonian problem [12]), in which the input is a sparse Hamiltonian and the problem quantifies over $i$ quantum proofs (see Definition 26). In this setting, we obtain the following completeness theorem:

Theorem 6 (Restatement of Theorem 37).

$\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ is $\mathsf{pureQ\Sigma_{i}}$ -complete and $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ is $\mathsf{pureQ\Pi_{i}}$ -complete.

These completeness results show that $\mathsf{pureQPH}$ admits natural complete problems, in contrast to the other variants of the quantum polynomial hierarchy. This highlights $\mathsf{pureQPH}$ as perhaps the most natural quantifier-based definition of the quantum polynomial hierarchy.

1.2 Main Ideas

Proving $\mathsf{QMA(2)}\subseteq\mathsf{pureQ\Sigma_{2}}\subseteq\mathsf{Q\Sigma_{3}}$ .

The proof that $\mathsf{QMA(2)}\subseteq\mathsf{pureQ\Sigma_{2}}$ is similar to the simple two-player game described earlier: one player sends a pure state, and the other must reproduce it exactly. With pure states, honesty can be enforced by a SWAP test. If the second player deviates, the SWAP test detects the inconsistency with constant probability.

A structural result of Harrow and Montanaro [19] ensures that in $\mathsf{QMA}(2)$ the two unentangled proofs may be taken to be identical. Thus, in $\mathsf{pureQ\Sigma_{2}}$ , the existential prover sends one copy of this proof $\ket{\psi}$ , while the universal prover is challenged to send the same state. The verifier first applies a SWAP test and, if the test fails, immediately accepts (since the universal prover failed its task). If the SWAP test passes, the verifier then runs the $\mathsf{QMA}(2)$ verification on the two states. Interestingly, the $\mathsf{QMA}(2)$ verification procedure is run on the post-measurement states after the SWAP test is applied; a careful analysis shows that this simulation succeeds.

The second inclusion, $\mathsf{pureQ\Sigma_{2}}\subseteq\mathsf{Q\Sigma_{3}}$ , also relies on the SWAP test, but now it is used to enforce purity rather than equality. In the $\mathsf{Q\Sigma_{3}}$ setting, the verifier receives three states: $\rho_{1}$ and $\rho_{3}$ from the existential prover, and $\rho_{2}$ from the universal prover. The goal is to simulate the $\mathsf{pureQ\Sigma_{2}}$ protocol, where one prover supplies a pure state $\ket{\psi_{1}}$ and the other supplies a pure state $\ket{\psi_{2}}$ .

A simple observation is that the universal prover in $\mathsf{pureQ\Sigma_{2}}$ has no incentive to send a mixed state, since they move last; hence, we can safely take $\rho_{2}$ to play the role of $\ket{\psi_{2}}$ . To certify that $\rho_{1}$ is effectively pure, the $\mathsf{Q\Sigma_{3}}$ verifier asks for two copies, $\rho_{1}$ and $\rho_{3}$ , and with some probability runs a SWAP test between them (rejecting if the test fails, and accepting otherwise). Otherwise, the verifier simulates the original $\mathsf{pureQ\Sigma_{2}}$ verification using $\rho_{1},\rho_{2}$ .

Amplification and $\mathsf{pureQPH}=\mathsf{QPH}$ .

Our amplification procedure is the most technically involved part of this work. As a first step, we transform the standard alternating-proof system – where the provers take turns sending states in the order $\exists\forall\exists\dots$ – into a system where, in each turn, a prover sends four unentangled proofs simultaneously. We achieve this by increasing the number of rounds by a factor of $7$ . In seven rounds the verifier receives states $\rho_{1},\dots,\rho_{7}$ , where the odd-indexed states ( $\rho_{1},\rho_{3},\rho_{5},\rho_{7}$ ) come from the existential prover and the even-indexed states ( $\rho_{2},\rho_{4},\rho_{6}$ ) come from the universal prover. The verifier discards the even-indexed states by default, leaving a block of four unentangled states from the existential prover, $\rho_{1}\otimes\rho_{3}\otimes\rho_{5}\otimes\rho_{7}$ . An analogous construction handles the universal prover’s turns. In this way, each turn of the game is simulated by a block of seven rounds, giving us a protocol where the verifier receives four unentangled proofs per prover per turn.

Our goal now is to simulate $\mathsf{pureQ\Sigma_{r}}$ in this $r$ -round system where each prover sends four unentangled mixed proofs per turn (which, as explained, can be simulated in $\mathsf{Q\Sigma_{7r}}$ ). For each block of four proofs, the verifier applies our disentangler (Lemma 4) to reduce the input to a convex mixture over a small set of product states. Conceptually, in the $i$ th round, each product state in the mixture can be viewed as $\ket{T}\ket{\psi}$ , where $\ket{T}$ encodes a transcript of the first $i-1$ rounds and $\ket{\psi}$ is the candidate response for the current round given that transcript. In this way, every round can be interpreted as producing a distribution over transcript–answer pairs, and the verifier’s job is to make sure the prover sends a pair consistent with the ongoing interaction.

The verifier maintains a “canonical transcript” that grows round by round. At each step, the disentangler outputs a mixture of possible continuations, each consisting of a transcript prefix and a candidate answer. The verifier checks consistency between the candidate transcript and the actual transcript accumulated so far using repeated SWAP tests; if the tests succeed, the answer is appended to the canonical transcript. If they fail, the current prover loses the round (accepting if it is the universal prover’s turn, rejecting otherwise). After $r$ rounds, the verifier runs the original $\mathsf{pureQ\Sigma_{r}}$ verifier $V_{x}$ on fresh copies of the canonical transcript and performs standard majority amplification to decide the outcome.

Quantified Hamiltonian Complexity.

Our approach to proving Proposition 5 proceeds in two steps. First, we show that $\exists\forall$ -MLH lies in $\mathsf{NP}^{\mathsf{QMA}}$ and, similarly, that $\forall\exists$ -MLH lies in $\mathsf{coNP}^{\mathsf{QMA}}$ . This step uses the fact that checking consistency of local density matrices – given local reduced density matrices, decide whether they arise from some global quantum state – can be solved with a single $\mathsf{QMA}$ query [29]. At a high level, the $\mathsf{NP}$ prover supplies classical descriptions of the reduced density matrices for the first witness $\rho$ . A single $\mathsf{QMA}$ oracle call is then used to check that these matrices are indeed consistent with some global state. Once this is certified, the verifier can “compress” the Hamiltonian $H$ into a smaller Hamiltonian $H^{\prime}$ that only acts on the Hilbert space corresponding to the universal prover’s state. Deciding whether all states $\sigma$ satisfy $\mathrm{tr}(H^{\prime}\sigma)\geq b$ can then be handled with a $\mathsf{coQMA}$ query, which is equivalent to a $\mathsf{QMA}$ query. The proof concludes by observing that $\exists\forall$ -MLH and $\forall\exists$ -MLH are equivalent by a minimax theorem.

We now turn to our completeness proofs of $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ and $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ . These problems can be viewed as the $\exists\forall$ - and $\forall\exists$ -pure sparse Hamiltonian (PSH) problems generalized to an arbitrary constant number of quantifiers. The containment is relatively straightforward. We use the techniques of Aharonov and Ta-Shma [4] to efficiently simulate the dynamics of sparse Hamiltonians in $\mathsf{BQP}$ , which places $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ and $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ inside $\mathsf{pureQ\Sigma_{i}}$ and $\mathsf{pureQ\Pi_{i}}$ , respectively.

The hardness direction requires extending the circuit-to-Hamiltonian framework to the quantified setting. Our construction generalizes the Hamiltonians of Chailloux and Sattath [12], who proved that $\exists\exists$ -PSH is $\mathsf{QMA}(2)$ -complete.³³3In the terminology of Chailloux and Sattath [12], the separable sparse Hamiltonian problem is $\mathsf{QMA}(2)$ -complete. In our language, this corresponds exactly to the $\exists\exists$ -PSH problem. We extend their approach to handle an arbitrary constant number of alternating quantifiers, ensuring that the Hamiltonian faithfully encodes the transcript of the underlying quantified proof system.

2 Preliminaries

For matrices, $\left\lVert\cdot\right\rVert_{1}$ denotes the Schatten $1$ -norm (also known as the trace norm or nuclear norm). For quantum states $\rho,\sigma$ , define the trace distance between $\rho$ and $\sigma$ as $d_{\mathrm{tr}}(\rho,\sigma)\coloneqq\frac{1}{2}\left\lVert\rho-\sigma\right% \rVert_{1}$ . If $\rho=\ket{\psi}\!\!\bra{\psi}$ and $\sigma=\ket{\phi}\!\!\bra{\phi}$ , then $d_{\mathrm{tr}}(\ket{\psi},\ket{\phi})=\sqrt{1-\lvert\braket{\psi|\phi}\rvert^% {2}}$ . Let $\mathcal{D}(\mathcal{H})$ denote the set of density operators on Hilbert space $\mathcal{H}$ . The following is a basic fact about trace distance.

Fact 7.

Let $\rho$ and $\sigma$ be quantum states with $d_{\mathrm{tr}}(\rho,\sigma)\leq\varepsilon$ . Then for any POVM element $0\leq M\leq 1$ , $\lvert\mathrm{tr}(M\rho)-\mathrm{tr}(M\sigma)\rvert\leq\varepsilon$ .

We also make use of two standard tools in quantum computation and quantum information, the SWAP test and the Gentle Measurement lemma, which we record below.

Lemma 8 (SWAP test [10]).

The SWAP test between two quantum states $\rho$ and $\sigma$ fails with probability $\frac{1}{2}-\frac{\mathrm{tr}(\rho\sigma)}{2}$ .

Lemma 9 (Gentle measurement [35]).

Consider a quantum state $\rho$ and a measurement operator $0\leq M\leq 1$ where $\mathrm{tr}(\rho M)\geq 1-\varepsilon$ . The post-measurement state $\rho^{\prime}\coloneqq\frac{\sqrt{M}\,\rho\,\sqrt{M}}{\mathrm{tr}(M\rho)},$ then satisfies $d_{\mathrm{tr}}(\rho,\rho^{\prime})\leq 2\sqrt{\varepsilon}.$

Finally, we turn to the formal definitions of $\mathsf{QPH}$ and $\mathsf{pureQPH}$ . We begin by specifying the individual levels of these hierarchies.

Definition 10 ( $\mathsf{Q\Sigma_{i}}$ ).

Let $A=(A_{\mathrm{yes}},A_{\mathrm{no}})$ be a promise problem. We say that $A$ is in $\mathsf{Q\Sigma_{i}}(c,s)$ for poly-time computable functions $c,s:\mathbb{N}\to[0,1]$ if there exists a polynomial $p(n)$ and a poly-time uniform family of quantum circuits $\{V_{x}\}_{x\in\{0,1\}^{*}}$ such that for every $n$ -bit input $x$ , $V_{x}$ takes in quantum proofs $\rho_{1},\dots,\rho_{i}\in\mathcal{D}(\mathbb{C}^{2^{p(n)}})$ and outputs a single qubit, such that:

$\blacksquare$

Completeness: $x\in A_{\mathrm{yes}}$ $\Rightarrow$ $\exists\rho_{1}\forall\rho_{2}\ldots Q_{i}\rho_{i}$ s.t. $\mathop{\bf Pr\/}[V_{x}\text{ accepts }\rho_{1}\otimes\dotsm\otimes\rho_{i}]% \geq c(n)$ .
$\blacksquare$

Soundness: $x\in A_{\mathrm{no}}$ $\Rightarrow$ $\forall\rho_{1}\exists\rho_{2}\ldots\overline{Q}_{i}\rho_{i}$ s.t. $\mathop{\bf Pr\/}[V_{x}\text{ accepts }\rho_{1}\otimes\dotsm\otimes\rho_{i}]% \leq s(n)$ .

Here, $Q_{i}$ is $\exists$ when $i$ is odd and $\forall$ otherwise, and $\overline{Q}_{i}$ is the complementary quantifier to $Q_{i}$ . Finally, define $\mathsf{Q\Sigma_{i}}:=\bigcup_{{c(n)-s(n)\in\Omega(1/\mathrm{poly}(n))}}% \mathsf{Q\Sigma_{i}}(c,s).$ Define $\mathsf{pureQ\Sigma_{i}}$ analogously, restricting $\rho_{1},\dots,\rho_{i}$ to pure states.

$\blacktriangleright$ Remark 11.

All messages being $p(n)$ qubits is without loss of generality, even for $\mathsf{pureQ\Sigma_{i}}$ , as the verifier can project messages onto a smaller subspace and let the sender lose if the projection fails.

$\mathsf{QPH}$ and $\mathsf{pureQPH}$ are the union over all levels of their hierarchies.

Definition 12 ( $\mathsf{QPH}$ and $\mathsf{pureQPH}$ [15, 2]).

The quantum polynomial hierarchy is defined as $\mathsf{QPH}\coloneqq\bigcup_{i=0}^{\infty}\mathsf{Q\Sigma_{i}},$ and the pure quantum polynomial hierarchy is defined as $\mathsf{pureQPH}\coloneqq\bigcup_{i=0}^{\infty}\mathsf{pureQ\Sigma_{i}}.$

One has to be careful when discussing oracles to promise problems, e.g., $\mathsf{NP}^{\mathsf{QMA}}$ . We say a deterministic Turing machine $M$ with access to a promise oracle $O=(O_{\mathrm{yes}},O_{\mathrm{no}})$ accepts/rejects robustly if $M$ accepts/rejects regardless of how invalid queries are answered (see also [16, Definition 3]).

Definition 13 ( $\mathsf{NP}$ with promise oracle [2, Footnote 3]).

Let $O$ be a promise problem. We say $A\in\mathsf{NP}^{O}$ if there exists a polynomial-time deterministic Turing machine $M$ , such that

$\blacksquare$

$x\in A_{\mathrm{yes}}\ \Rightarrow\ \exists y\colon M^{O}(x,y)$ accepts robustly.
$\blacksquare$

$x\in A_{\mathrm{no}}\ \Rightarrow\ \forall y\colon M^{O}(x,y)$ rejects robustly.

This definition may be considered the weakest “reasonable” definition for $\mathsf{NP}$ with promise oracle, without outright forbidding invalid queries.

3 Sandwiching the Second Level of $\mathsf{pureQPH}$

We prove the inclusions $\mathsf{QMA(2)}\subseteq\mathsf{pureQ\Sigma_{2}}\subseteq\mathsf{Q\Sigma_{3}}$ , i.e., that the second level of $\mathsf{pureQPH}$ lies between $\mathsf{QMA(2)}$ and the third level of $\mathsf{QPH}$ . It is known from prior work that $\mathsf{Q\Sigma_{3}}\subseteq\mathsf{NEXP}$ [15]. We begin by establishing the first inclusion, showing that any $\mathsf{QMA}(2)$ protocol can be simulated within the second level of $\mathsf{pureQPH}$ .

Theorem 14.

$\mathsf{QMA}(2)\subseteq\mathsf{pureQ\Sigma_{2}}$ .

Proof.

Let $A\in\mathsf{QMA}(2)$ . By [19], there exists a verifier $V$ , such that


$\displaystyle\forall x\in A_{\mathrm{yes}},\,\exists\ket{\psi}\colon\;\mathrm{% tr}\!\left(H_{x}\big(\ket{\psi}\!\!\bra{\psi}_{A}\otimes\ket{\psi}\!\!\bra{% \psi}_{B}\big)\right)$	$\displaystyle\geq 1-\varepsilon,$	(2a)
$\displaystyle\forall x\in A_{\mathrm{no}},\,\forall\rho\,\forall\sigma\colon\;% \mathrm{tr}\!\left(H_{x}(\rho_{A}\otimes\sigma_{B})\right)$	$\displaystyle\leq\varepsilon,$	(2b)

where $H_{x}$ denotes the POVM element corresponding to acceptance on input $x$ , and $\varepsilon\in 2^{-O(n)}$ . We now construct a $\mathsf{pureQ\Sigma_{2}}$ verifier $V^{\prime}$ as follows. On input $x$ , $V^{\prime}$ receives two states $\ket{\psi}_{A}$ and $\ket{\phi}_{B}$ and acts as follows:

1.

Perform a SWAP test on registers $A$ and $B$ . If the SWAP test fails, then accept.
2.

Otherwise, run $V$ on registers $A$ and $B$ , and accept only if $V$ accepts.

We let $H_{x}^{\prime}$ denote the POVM element corresponding to acceptance on input $x$ for the verifier $V^{\prime}$ .

First, we prove the soundness of $V^{\prime}$ , which is straightforward. Suppose $x\in A_{\mathrm{no}}$ . By Equation 2b, we have $\forall\ket{\psi}\colon\mathrm{tr}\left(H_{x}(\ket{\psi}\!\!\bra{\psi}\otimes% \ket{\psi}\!\!\bra{\psi})\right)\leq\varepsilon.$ In this case, the no-prover will always send $\ket{\phi}_{B}=\ket{\psi}_{A}$ , which ensures the SWAP test accepts with probability $1$ (Lemma 8) and leaves the state undisturbed. The verifier then proceeds to run $V$ on $\ket{\psi}_{A}\otimes\ket{\psi}_{A}$ , which will accept with probability at most $\varepsilon$ . Therefore, the overall acceptance probability of $V^{\prime}$ is at most $\varepsilon$ .

Now suppose $x\in A_{\mathrm{yes}}$ . We will show $\exists\ket{\psi}\,\forall\ket{\phi}\colon\mathrm{tr}\left(H^{\prime}_{x}(\ket% {\psi}\!\!\bra{\psi}\otimes\ket{\phi}\!\!\bra{\phi})\right)\geq c$ for some constant $c>0$ , which suffices to complete the proof. Let $\ket{\psi}$ be the witness guaranteed by Equation 2a. For an arbitrary state $\ket{\phi}$ , define $\delta\coloneqq d_{\mathrm{tr}}(\ket{\psi},\ket{\phi})$ , so $\lvert\braket{\psi|\phi}\rvert^{2}=1-\delta^{2}$ . By Lemma 8, $V^{\prime}$ accepts in step (1) (i.e., the SWAP test fails) with probability $\frac{1}{2}-\frac{1}{2}\lvert\braket{\psi|\phi}\rvert^{2}=\frac{\delta^{2}}{2}.$ If the SWAP test succeeds, let $\rho_{AB}=\ket{\psi}\!\!\bra{\psi}\otimes\ket{\phi}\!\!\bra{\phi}$ , and let $\rho^{\prime}_{AB}$ be the post-measurement state conditioned on the SWAP test succeeding. By the Gentle Measurement Lemma (Lemma 9), $d_{\mathrm{tr}}(\rho,\rho^{\prime})\leq\sqrt{2}\delta.$ Let $\rho^{*}=\ket{\psi}\!\!\bra{\psi}\otimes\ket{\psi}\!\!\bra{\psi}$ . By the triangle inequality,

d_{\mathrm{tr}}(\rho^{*},\rho^{\prime})\leq d_{\mathrm{tr}}(\rho^{*},\rho)+d_{% \mathrm{tr}}(\rho,\rho^{\prime})\leq\delta+\sqrt{2}\delta=(1+\sqrt{2})\delta.

(3)

Thus, by Fact 7 and Equation 2a, $V$ accepts $\rho^{\prime}$ with probability at least

\mathrm{tr}(H_{x}\rho^{\prime})\geq 1-\varepsilon-d_{\mathrm{tr}}(\rho^{*},% \rho^{\prime})\geq 1-\varepsilon-(1+\sqrt{2})\delta.

(4)

Therefore, the overall acceptance probability of $V^{\prime}$ on $\rho_{AB}$ is

\mathrm{tr}(H_{x}^{\prime}\rho)=\frac{\delta^{2}}{2}+\left(1-\frac{\delta^{2}}% {2}\right)\max\left\{0,1-\varepsilon-(1+\sqrt{2})\delta\right\}.

(5)

Consider the case where $\delta\geq\frac{1-\varepsilon}{1+\sqrt{2}}$ . The $\max$ term vanishes, so the acceptance probability is simply $\frac{\delta^{2}}{2}$ , minimized when $\delta$ is as small as possible, i.e., $\delta=\frac{1-\varepsilon}{1+\sqrt{2}}$ . Now consider the case where $\delta\leq\frac{1-\varepsilon}{1+\sqrt{2}}$ . The expression becomes $1-\varepsilon-(1+\sqrt{2})\delta+\frac{\varepsilon}{2}\delta^{2}+\frac{1+\sqrt% {2}}{2}\delta^{3}$ , which is decreasing on the interval $[0,\frac{1-\varepsilon}{1+\sqrt{2}}]$ , so the minimum also occurs at $\delta=\frac{1-\varepsilon}{1+\sqrt{2}}$ . In both cases, the minimizing value is $\delta^{\star}=\frac{1-\varepsilon}{1+\sqrt{2}}$ , giving

\mathrm{tr}(H_{x}^{\prime}\rho)=\frac{(1-\varepsilon)^{2}}{2(1+\sqrt{2})^{2}}=% \left(\frac{3}{2}-\sqrt{2}\right)\left(1-\varepsilon\right)^{2}>0.085,

(6)

for sufficiently large $n$ . $\hfill\blacktriangleleft$

We now show that the second level of $\mathsf{pureQPH}$ is contained in the third level of $\mathsf{QPH}$ .

Theorem 15.

$\mathsf{pureQ\Sigma_{2}}\subseteq\mathsf{Q\Sigma_{3}}$ .

Proof.

Let $A\in\mathsf{pureQ\Sigma_{2}}$ . Then there exists a verifier $V$ with completeness $c$ , soundness $s$ , and $c-s\geq n^{-O(1)}$ , together with a POVM element $H_{x}$ for each input $x$ , such that


$\displaystyle\forall x\in A_{\mathrm{yes}},\,\exists\ket{\psi}\;\forall\ket{% \phi}\colon\mathrm{tr}(H_{x}(\ket{\psi}\!\!\bra{\psi}_{A}\otimes\ket{\phi}\!\!% \bra{\phi}_{B}))$	$\displaystyle\geq c,$	(7a)
$\displaystyle\forall x\in A_{\mathrm{no}},\,\forall\ket{\psi}\;\exists\ket{% \phi}\colon\mathrm{tr}(H_{x}(\ket{\psi}\!\!\bra{\psi}_{A}\otimes\ket{\phi}\!\!% \bra{\phi}_{B}))$	$\displaystyle\leq s.$	(7b)

Define a $\mathsf{Q\Sigma_{3}}$ verifier $V^{\prime}$ with POVM $H_{x}^{\prime}$ on input $x$ as follows. Let $\rho_{1}$ be the proof sent by the yes-prover in the first round, $\rho_{2}$ be the proof sent by the no-prover in the second round, and $\rho_{3}$ be the proof sent by the yes-prover in the third round. $V^{\prime}$ then proceeds as follows:

1.

With probability $p$ , run $V(\rho_{1},\rho_{2})$ , accepting or rejecting according to $V$ ’s output.
2.

With probability $1-p$ , run a SWAP test between $\rho_{1}$ and $\rho_{3}$ , and accept only if the SWAP test passes.

We must exhibit completeness/soundness paramters $c^{\prime},s^{\prime}$ with $c^{\prime}-s^{\prime}\geq n^{-O(1)}$ , such that


$\displaystyle\forall x\in A_{\mathrm{yes}},\,\exists\rho_{1}\;\forall\rho_{2}% \;\exists\rho_{3}\colon\mathrm{tr}(H^{\prime}_{x}(\rho_{1}\otimes\rho_{2}% \otimes\rho_{3}))$	$\displaystyle\geq c^{\prime}$	(8a)
$\displaystyle\forall x\in A_{\mathrm{no}},\ \forall\rho_{1}\;\exists\rho_{2}\;% \forall\rho_{3}\colon\mathrm{tr}(H^{\prime}_{x}(\rho_{1}\otimes\rho_{2}\otimes% \rho_{3}))$	$\displaystyle\leq s^{\prime}.$	(8b)

Suppose $x\in A_{\mathrm{yes}}$ . We have $c^{\prime}=(1-p)+p\cdot c=1-p(1-c),$ because the yes-prover can send $\rho_{1}=\rho_{3}=\ket{\psi}\!\!\bra{\psi}$ from Equation 7a and the no-prover gains no advantage from sending a mixed state by convexity.

Now suppose $x\in A_{\mathrm{no}}$ . Let $1-\frac{\delta}{2}$ be the probability that the SWAP test between $\rho_{1}$ and $\rho_{3}$ passes. Then, by Lemma 8, $\mathrm{tr}(\rho_{1}\rho_{3})=1-\delta$ , which implies $\lambda_{\mathrm{max}}(\rho_{1})\geq 1-\delta$ by Hölder’s inequality. Let $\ket{\psi}$ be the corresponding eigenvector. By Equation 7b, there exists a “refutation” $\ket{\phi}$ (depending on $\ket{\psi}$ ) such that $\mathrm{tr}(H_{x}(\ket{\psi}\!\!\bra{\psi}_{A}\otimes\ket{\phi}\!\!\bra{\phi}_% {B}))\leq s.$ Let the no-prover send $\rho_{2}=\ket{\phi}\!\!\bra{\phi}$ . Using linearity and that $0\leq H_{x}\leq 1$ , we get

	$\displaystyle\mathrm{tr}\left(H_{x}(\rho_{1}\otimes\rho_{2})\right)$	$\displaystyle=\lambda_{\mathrm{max}}\mathrm{tr}\left(H_{x}(\ket{\psi}\!\!\bra{% \psi}\otimes\rho_{2})\right)+(1-\lambda_{\mathrm{max}})\mathrm{tr}\left(H_{x}(% \sigma\otimes\rho_{2})\right)$		(9)
		$\displaystyle\leq\lambda_{\mathrm{max}}\cdot s+(1-\lambda_{\mathrm{max}})\cdot 1% =s+(1-\lambda_{\mathrm{max}})(1-s)\leq(1-\delta)s+\delta,$		(9)

where, in the first line we use the fact that $\rho_{1}=\lambda_{\mathrm{max}}\ket{\psi}\!\!\bra{\psi}+(1-\lambda_{\mathrm{% max}})\sigma$ for some state $\sigma$ , and, in the last line, we use the fact that $\lambda_{\mathrm{max}}\geq 1-\delta$ . The overall acceptance probability $s^{\prime}$ of $V^{\prime}$ is thus

	$\displaystyle s^{\prime}$	$\displaystyle=\max_{\delta\in[0,1]}\left((1-p)(1-\frac{\delta}{2})+p((1-\delta% )s+\delta)\right)$		(10)
		$\displaystyle=1-p+ps+\delta\left(p(1-s)-\frac{1-p}{2}\right)=\max\left(1-p+ps,% \frac{1+p}{2}\right).$		(10)

We choose $p=\frac{1}{3-2s}$ , which ensures that $p\in(0,1]$ because $s\in[0,1]$ . Then

	$\displaystyle 1-p+ps$	$\displaystyle=1-\frac{1}{3-2s}+\frac{s}{3-2s}=\frac{3-2s-1+s}{3-2s}=\frac{2-s}% {3-2s},\qquad\text{and}$		(11)
	$\displaystyle\frac{1+p}{2}$	$\displaystyle=\frac{1+\frac{1}{3-2s}}{2}=\frac{\frac{3-2s+1}{3-2s}}{2}=\frac{4% -2s}{2(3-2s)}=\frac{2-s}{3-2s},$		(12)

so the two terms in the $\max$ function become equal. Therefore, $s^{\prime}=\frac{2-s}{3-2s}$ . Our completeness parameter $c^{\prime}$ becomes

c^{\prime}=1-p(1-c)=1-\frac{1-c}{3-2s}=\frac{3-2s-(1-c)}{3-2s}=\frac{2-2s+c}{3% -2s}.

(13)

Therefore, the completeness/soundness gap is

c^{\prime}-s^{\prime}=\frac{2-2s+c}{3-2s}-\frac{2-s}{3-2s}=\frac{c-s}{3-2s}.

(14)

Because $c-s\geq n^{-O(1)}$ by assumption and $3-2s\leq 3$ , we have $c^{\prime}-s^{\prime}\geq\frac{c-s}{3}\geq n^{-O(1)}$ , which completes the proof. $\hfill\blacktriangleleft$

4 Amplification of $\mathsf{pureQPH}$ via Disentanglers

In this section, we give an error reduction result for $\mathsf{pureQPH}$ . We show that any protocol in $\mathsf{pureQ\Sigma_{r}}$ can be converted into one in $\mathsf{Q\Sigma_{7r}}$ whose completeness is arbitrarily close to 1 and whose soundness is arbitrarily close to 0 (up to $1/\mathrm{poly}(n)$ ). In other words, we can amplify the gap between YES and NO cases at the cost of a constant-factor increase in the number of alternations.

Theorem 16.

$\mathsf{pureQ\Sigma_{r}}\subseteq\mathsf{Q\Sigma_{7r}}(c^{\prime},s^{\prime})$ with $c^{\prime}\geq 1-1/q(n)$ and $s^{\prime}\leq 1/q(n)$ , where $q$ is an arbitrary polynomial.

Theorem 16 shows that every level of $\mathsf{pureQPH}$ is contained in $\mathsf{QPH}$ . The reverse inclusion $\mathsf{QPH}\subseteq\mathsf{pureQPH}$ is straightforward: given mixed-state proofs, the provers can instead send purifications, and the verifier can trace out the auxiliary registers to recover the original mixed states. Putting these two directions together, we conclude that the hierarchies are equal.

Corollary 17.

$\mathsf{pureQPH}=\mathsf{QPH}$ .

The remainder of this section is devoted to proving Theorem 16. Before presenting the proof, we construct a disentangler tailored to our purposes, building on the dimension-independent disentangler of Jeronimo and Wu [21].

Theorem 18 (Disentangler [21]).

Let $d,\ell\geq\kappa\in\mathbb{N}$ and $\mathcal{H}=\mathbb{C}^{d}$ . There exists an efficient quantum channel $\Lambda:\mathcal{D}(\mathcal{H}^{\otimes 2\ell})\to\mathcal{D}(\mathcal{H}^{% \otimes\kappa})$ , such that for all states $\rho_{1},\rho_{2}$ , there exists a distribution $\mu$ on pure states $\ket{\psi}\in\mathbb{C}^{d}$ , such that

\left\lVert\Lambda(\rho_{1}\otimes\rho_{2})-\int{\psi}^{\otimes\kappa}d\mu% \right\rVert_{1}\leq\tilde{O}\left(\left(\frac{\kappa^{3}}{\ell}\right)^{1/4}% \right).

(15)

Furthermore, $\Lambda({\psi}^{\otimes 2\ell})={\psi}^{\otimes\kappa}$ for all $\ket{\psi}\in\mathcal{H}$ .

Note that by Carathéodory’s theorem [11], we always have

\int{\psi}^{\otimes\kappa}d\mu=\sum_{i}p_{i}{\psi_{i}}^{\otimes\kappa}

(16)

for some distribution $p_{i}$ on pure states $\ket{\psi_{i}}$ .

We also use the following facts about the SWAP test and the product test of Harrow and Montanaro [19]. We let $P_{\mathrm{swap}}(\rho,\sigma)$ and $P_{\mathrm{prod}}(\rho,\sigma)$ denote the acceptance probability of the SWAP test and the product test, respectively. We let $P_{\mathrm{prod}}(\rho)\coloneq P_{\mathrm{prod}}(\rho,\rho)$ .

Lemma 19 (Product Test [19, Theorem 3]).

Given $\ket{\psi}\in\mathbb{C}^{d_{1}}\otimes\dotsm\otimes\mathbb{C}^{d_{n}}$ , let

1-\varepsilon=\max\bigl\{\lvert\braket{\psi|\phi_{1},\dots,\phi_{n}}\rvert^{2}% \bigm|\ket{\phi_{i}}\in\mathbb{C}^{d_{i}},i\in[n]\bigr\}.

(17)

Then $P_{\mathrm{prod}}({\psi})=1-\Theta(\varepsilon)$ .

Lemma 20 ([19, Proof of Lemma 5]).

$P_{\mathrm{prod}}(\rho,\sigma)\leq\frac{1}{2}(P_{\mathrm{prod}}(\rho)+P_{% \mathrm{prod}}(\sigma))$ .

Lemma 21.

$P_{\mathrm{prod}}(\rho,\sigma)\leq P_{\mathrm{swap}}(\rho,\sigma)$ .

To proceed, we need the following combinatorial lemma about distributions. Intuitively, it says that if a certain event happens with non-negligible probability, then a small “hitting set” of outcomes suffices to capture the event with high conditional probability. The proof is given in the full version [17].

Lemma 22.

Let $p=(p_{i}),q=(q_{j})$ be independent probability distributions over $[N]$ . Let $S\subseteq[N]^{2}$ satisfy $\mathop{\bf Pr\/}[(i,j)\in S]=\varepsilon$ . Then there exists a set $X\subseteq[N]$ of size $m\leq\left\lceil 1/e\varepsilon\gamma\right\rceil,$ such that $\mathop{\bf Pr\/}[\exists k\in X:(i,k)\in S\mid(i,j)\in S]\geq 1-\gamma$ .

We now combine our combinatorial lemma with the dimension-independent disentangler of Jeronimo and Wu to obtain a new disentangler suited for our setting.

Lemma 23.

Let $\mathcal{H}=\mathbb{C}^{d_{1}}\otimes\dotsm\otimes\mathbb{C}^{d_{s}}$ , $\kappa\in\mathbb{N}$ , and $\delta>0$ . There exist parameters $\ell\in\mathrm{poly}(\delta^{-1},\kappa),m\in O(\delta^{-2})$ and a quantum channel $\Gamma\colon\mathcal{D}(\mathcal{H}^{\otimes 4\ell})\to\mathcal{D}(\mathcal{H}% ^{\otimes\kappa}),$ with the following properties: for all states $\rho_{1},\dots,\rho_{4}\in\mathcal{D}(\mathcal{H}^{\otimes\ell})$ , there exists a distribution $\{p_{i}\}_{i=1}^{m}$ over product states $\ket{\zeta_{i}}=\ket{\zeta_{i,1}}\otimes\dots\otimes\ket{\zeta_{i,s}},\;\ket{% \zeta_{i,j}}\in\mathbb{C}^{d_{j}}$ such that

\left\lVert\Gamma(\rho_{1}\otimes\rho_{2}\otimes\rho_{3}\otimes\rho_{4})-\sum_% {i=1}^{m}p_{i}\ket{\zeta_{i}}\!\!\bra{\zeta_{i}}^{\otimes\kappa}\right\rVert_{% 1}\leq\delta.

(18)

Furthermore, for every pure product state $\ket{\psi}=\ket{\psi_{1}}\otimes\dotsm\otimes\ket{\psi_{s}}\in\mathcal{H}$ , $\Gamma(\ket{\psi}\!\!\bra{\psi}^{\otimes 4\ell})=\ket{\psi}\!\!\bra{\psi}^{% \otimes\kappa}$ .

Proof.

Let $\Lambda\colon\mathcal{D}(\mathcal{H}^{\otimes 2\ell})\to\mathcal{D}(\mathcal{H% }^{\otimes(\kappa+\kappa^{\prime})})$ denote the channel from Theorem 18, now parameterized to output $\kappa+\kappa^{\prime}$ copies rather than $\kappa$ , where $\kappa^{\prime}$ will be chosen later. We define $\Gamma(\rho_{1}\otimes\rho_{2}\otimes\rho_{3}\otimes\rho_{4})$ as follows:

1.

Apply $\Lambda$ twice to obtain $\sigma_{1}=\Lambda(\rho_{1}\otimes\rho_{2})$ and $\sigma_{2}=\Lambda(\rho_{3}\otimes\rho_{4})$ on registers $\mathcal{A}_{1},\dots,\mathcal{A}_{\kappa+\kappa^{\prime}}$ and $\mathcal{B}_{1},\dots,\mathcal{B}_{\kappa+\kappa^{\prime}}$ respectively.
2.
For $i=1,\dots,\kappa^{\prime}$ , perform a product test between $\mathcal{A}_{i}$ and $\mathcal{B}_{i}$ .
1. (a)
  
  If all product tests accept, output registers $\mathcal{A}_{\kappa^{\prime}+1},\dots,\mathcal{A}_{\kappa+\kappa^{\prime}}$ .
2. (b)
  
  Otherwise, output $\ket{\mathbf{0}}^{\otimes\kappa}$ , where $\ket{\mathbf{0}}=\ket{0_{1},\dots,0_{s}}\in\mathcal{H}$ .

Let $\eta=\Gamma(\rho_{1}\otimes\rho_{2}\otimes\rho_{3}\otimes\rho_{4})$ be the output of our channel. Note that, by Theorems 18 and 16, $\sigma_{1}$ and $\sigma_{2}$ in step 1 can be approximated as

\left\lVert\sigma_{1}\otimes\sigma_{2}-\sigma^{\prime}_{1}\otimes\sigma_{2}^{% \prime}\right\rVert_{1}\leq 2\varepsilon_{\Lambda},\quad\sigma_{1}^{\prime}=% \sum_{i=1}^{M}p_{i}{\ket{\psi_{i}}\!\!\bra{\psi_{i}}}^{\otimes(\kappa+\kappa^{% \prime})},\sigma_{2}^{\prime}=\sum_{j=1}^{M}q_{j}{\ket{\phi_{j}}\!\!\bra{\phi_% {j}}}^{\otimes(\kappa+\kappa^{\prime})},

(19)

where $\varepsilon_{\Lambda}$ denotes the error due to $\Lambda$ (Equation 15). We will eventually choose $\ell$ so that $2\varepsilon_{\Lambda}\leq\tfrac{\delta}{2}$ .

Let $\Gamma_{2}$ be the channel corresponding to step 2 in the definition of $\Gamma$ above. By contractivity, we have $\left\lVert\eta-\Gamma_{2}(\sigma_{1}^{\prime}\otimes\sigma_{2}^{\prime})% \right\rVert_{1}=\left\lVert\Gamma_{2}(\sigma_{1}\otimes\sigma_{2})-\Gamma_{2}% (\sigma_{1}^{\prime}\otimes\sigma_{2}^{\prime})\right\rVert_{1}\leq 2% \varepsilon_{\Lambda}.$ Let $p_{\mathrm{acc}}$ be the probability that all product tests accept in step (2a). If $p_{\mathrm{acc}}\leq\delta/4$ , then

\left\lVert\eta-\ket{\mathbf{0}}\!\!\bra{\mathbf{0}}^{\otimes\kappa}\right% \rVert_{1}\leq 2\varepsilon_{\Lambda}+2p_{\mathrm{acc}}\leq\delta.

(20)

Hence, assume $p_{\mathrm{acc}}>\delta/4$ . It holds that

p_{\mathrm{acc}}=\sum_{i,j}p_{i}q_{j}P_{\mathrm{prod}}({\ket{\psi_{i}}\!\!\bra% {\psi_{i}}},{\ket{\phi_{j}}\!\!\bra{\phi_{j}}})^{\kappa^{\prime}}\eqcolon\sum_% {i,j}p_{i}q_{j}c_{ij}.

(21)

Define $\varepsilon_{S}\coloneqq\alpha p_{\mathrm{acc}}$ for $\alpha\in(0,1)$ to be determined later. Let $S=\{(i,j)\mid c_{ij}\geq\varepsilon_{S}\}$ . Then

p_{\mathrm{acc}}=\mathop{\bf E\/}[c_{ij}]\leq\varepsilon_{S}\mathop{\bf Pr\/}[% S^{c}]+\mathop{\bf Pr\/}[S]\;\Longrightarrow\;\mathop{\bf Pr\/}[S]\geq(1-% \alpha)p_{\mathrm{acc}}.

(22)

We will use Lemma 22 to approximate $\ket{\psi_{i}}$ with $(i,j)\in S$ with a small distribution. However, there is still a chance that the product tests in (2a) accept (event $A$ ) even if $(i,j)\notin S$ :

\mathop{\bf Pr\/}[A\cap S^{c}]=\sum_{ij\in S^{c}}p_{i}q_{j}c_{ij}\leq\sum_{ij}% p_{i}q_{j}\varepsilon_{S}=\alpha p_{\mathrm{acc}}

(23)

For all $(i,j)\in S$ , $P_{\mathrm{prod}}(\ket{\psi_{i}}\!\!\bra{\psi_{i}},\ket{\phi_{j}}\!\!\bra{\phi% _{j}})=c_{ij}^{1/\kappa^{\prime}}\geq(\varepsilon_{S})^{1/\kappa^{\prime}}% \eqcolon\tau,$ where $\kappa^{\prime}\geq-t\ln(\alpha\delta/4)>-t\ln(\varepsilon_{S})$ gives $\tau=(\varepsilon_{S})^{1/\kappa^{\prime}}\geq e^{-1/t}\geq 1-1/t$ for $t>1$ to be determined later. By Lemma 22 with parameters $\varepsilon\leftarrow\mathop{\bf Pr\/}[S]$ and $\gamma$ to be determined later, there exists a set $X\subseteq[M]$ of size $m=O(1/((1-\alpha)p_{\mathrm{acc}}\gamma))\leq O(1/(\delta\gamma))$ (recall $p_{\mathrm{acc}}>\delta/4$ ) such that

\mathop{\bf Pr\/}[i\in S^{\prime}\mid(i,j)\in S]\geq 1-\gamma,\qquad S^{\prime% }=\{i\in[M]\mid\exists j_{i}\in X\colon(i,j_{i})\in S\}.

(24)

For all $i\in S^{\prime}$ , define $\ket{\eta_{i}}=\ket{\phi_{j_{i}}}$ for some $j_{i}$ with $(i,j_{i})\in S$ . These $\ket{\eta_{i}}$ must be close to product as $P_{\mathrm{prod}}(\ket{\psi_{i}}\!\!\bra{\psi_{i}},\ket{\eta_{i}}\!\!\bra{\eta% _{i}})\geq\tau\geq 1-1/t$ . By Lemma 20,

P_{\mathrm{prod}}(\ket{\psi_{i}}\!\!\bra{\psi_{i}},\ket{\eta_{i}}\!\!\bra{\eta% _{i}})\leq\frac{1}{2}\bigl(P_{\mathrm{prod}}(\ket{\psi_{i}}\!\!\bra{\psi_{i}})% +P_{\mathrm{prod}}(\ket{\eta_{i}}\!\!\bra{\eta_{i}})\bigr)\;\Longrightarrow\;P% _{\mathrm{prod}}(\ket{\eta_{i}}\!\!\bra{\eta_{i}})\geq 1-2/t.

By Lemma 19, there exists $\ket{\zeta_{i}}=\ket{\zeta_{i,1}}\otimes\dotsm\otimes\ket{\zeta_{i,s}}\in% \mathcal{H}$ such that $\lvert\braket{\eta_{i}|\zeta_{i}}\rvert^{2}\geq 1-O(1/t)$ . Additionally $\lvert\braket{\psi_{i}|\eta_{i}}\rvert^{2}=2P_{\mathrm{swap}}(\ket{\eta_{i}}\!% \!\bra{\eta_{i}},\ket{\psi_{i}}\!\!\bra{\psi_{i}})-1\geq 2P_{\mathrm{prod}}(% \ket{\eta_{i}}\!\!\bra{\eta_{i}},\ket{\psi_{i}}\!\!\bra{\psi_{i}})-1\geq 1-2/t$ by Lemma 21. Hence, for an appropriate constant $C$ ,

	$\displaystyle\left\lVert\ket{\psi_{i}}\!\!\bra{\psi_{i}}^{\otimes\kappa}-\ket{% \zeta_{i}}\!\!\bra{\zeta_{i}}^{\otimes\kappa}\right\rVert_{1}$	$\displaystyle\leq\left\lVert\ket{\psi_{i}}\!\!\bra{\psi_{i}}^{\otimes\kappa}-% \ket{\eta_{i}}\!\!\bra{\eta_{i}}^{\otimes\kappa}\right\rVert_{1}+\left\lVert% \ket{\eta_{i}}\!\!\bra{\eta_{i}}^{\otimes\kappa}-\ket{\zeta_{i}}\!\!\bra{\zeta% _{i}}^{\otimes\kappa}\right\rVert_{1}$		(25)
		$\displaystyle=2\sqrt{1-\lvert\braket{\psi_{i}\|\eta_{i}}\rvert^{2\kappa}}+2% \sqrt{1-\lvert\braket{\eta_{i}\|\zeta_{i}}\rvert^{2\kappa}}\leq\sqrt{C\kappa/t},$		(25)

where the last step uses Bernoulli’s inequality.

Finally we approximate the idealized output state $\eta^{\prime}=\Gamma_{2}(\sigma_{1}^{\prime}\otimes\sigma_{2}^{\prime})$ as $\widetilde{\eta}$ (with small support):

	$\displaystyle\eta^{\prime}$	$\displaystyle=\sum_{i,j}p_{i}q_{j}\left((1-c_{ij})\ket{\mathbf{0}}\!\!\bra{% \mathbf{0}}^{\otimes\kappa}+c_{ij}\ket{\psi_{i}}\!\!\bra{\psi_{i}}^{\otimes% \kappa}\right)$		(26)
	$\displaystyle\widetilde{\eta}$	$\displaystyle=\sum_{(i,j)\in S\wedge i\in S^{\prime}}p_{i}q_{j}\left((1-c_{ij}% )\ket{\mathbf{0}}\!\!\bra{\mathbf{0}}^{\otimes\kappa}+c_{ij}\ket{\zeta_{i}}\!% \!\bra{\zeta_{i}}^{\otimes\kappa}\right)+\sum_{(i,j)\notin S\vee i\notin S^{% \prime}}p_{i}q_{j}\ket{\mathbf{0}}\!\!\bra{\mathbf{0}}^{\otimes\kappa}$		(27)

To bound $\left\lVert\eta^{\prime}-\widetilde{\eta}\right\rVert_{1}$ , we need to bound three sources of error: (i) Accepting $(i,j)\notin S$ , which occurs with probability $\mathop{\bf Pr\/}[A\cap S^{c}]\leq\alpha p_{\mathrm{acc}}\leq\alpha$ by Equation 23; (ii) Getting $(i,j)\in S$ , but $i\notin S^{\prime}$ , which occurs with probability $\mathop{\bf Pr\/}[(i,j)\in S\wedge i\notin S^{\prime}]\leq\mathop{\bf Pr\/}[i% \notin S^{\prime}\mid(i,j)\in S]\leq\gamma$ ; (iii) Approximation error $\sqrt{C\kappa/t}$ from Equation 25. Therefore, we get

$\displaystyle\left\lVert\eta^{\prime}-\widetilde{\eta}\right\rVert_{1}$	$\displaystyle\leq\left\lVert\sum_{(i,j)\in S\wedge i\in S^{\prime}}p_{i}q_{j}c% _{ij}\left(\ket{\psi_{i}}\!\!\bra{\psi_{i}}^{\otimes\kappa}-\ket{\zeta_{i}}\!% \!\bra{\zeta_{i}}^{\otimes\kappa}\right)\right\rVert_{1}$	(28)
	$\displaystyle\qquad\qquad+\left\lVert\sum_{(i,j)\notin S\vee i\notin S^{\prime% }}p_{i}q_{j}c_{ij}\left(\ket{\psi_{i}}\!\!\bra{\psi_{i}}^{\otimes\kappa}-\ket{% \mathbf{0}}\!\!\bra{\mathbf{0}}^{\otimes\kappa}\right)\right\rVert_{1}$
	$\displaystyle\leq\max_{i\in S^{\prime}}\left\lVert\ket{\psi_{i}}\!\!\bra{\psi_% {i}}^{\otimes\kappa}-\ket{\zeta_{i}}\!\!\bra{\zeta_{i}}^{\otimes\kappa}\right% \rVert_{1}+2\mathop{\bf Pr\/}[A\cap S^{c}]+2\mathop{\bf Pr\/}[S\cap S^{\prime c}]$
	$\displaystyle\leq 2\left(\sqrt{C\kappa/t}+\alpha+\gamma\right).$

We set $t=C\kappa(8/\delta)^{2},\;\alpha=\gamma=\delta/16,\;\kappa^{\prime}=\lceil-t% \ln(\alpha\delta/4)\rceil,\;\ell=\tilde{O}\!\left((\kappa+\kappa^{\prime})^{3}% /\delta^{4}\right).$ Thus, $\varepsilon_{\Lambda}\leq\delta/4$ by Theorem 18, and the overall error is

\left\lVert\eta-\widetilde{\eta}\right\rVert\leq 2\varepsilon_{\Lambda}+2\left% (\sqrt{C\kappa/t}+\alpha+\gamma\right)\leq\delta/2+2(\delta/8+\delta/16+\delta% /16)\leq\delta.\

(29)

$\hfill\blacktriangleleft$

Amplified verifier $V^{\prime}_{x}$ on input $x$

Input: Messages $\rho_{1},\dots,\rho_{r}$ , where each $\rho_{i}$ is a product across 4 registers.

1. Selection of canonical transcript (rounds $i=1$ to $r$ ):

$\blacksquare$

Disentangle: Apply the channel $\Gamma$ from Lemma 23 to $\rho_{i}$ to obtain a state $\rho_{i}^{\prime}$ close to a mixture of only poly-many pure states $\ket{\zeta}$ .
$\blacksquare$

Response table: The disentangler ensures that $\ket{\zeta}$ has the tensor product structure $\ket{\zeta}=\bigotimes_{j=1}^{M_{i}}\bigl(\ket{T_{ij}}\otimes\ket{\psi_{ij}}% \bigr),$ where $\ket{T_{ij}}$ represents a candidate history and $\ket{\psi_{ij}}$ is the proposed response.
$\blacksquare$
Select player response:
- –
  
  Perform $W$ SWAP tests between the current canonical transcript $\ket{C_{i-1}}$ and the candidate history $\ket{T_{ij}}$ .
- –
  
  If all tests accept for some index $j$ , update the transcript $\ket{C_{i}}\coloneq\ket{T_{ij}}\otimes\ket{\psi_{ij}}.$
- –
  
  If no index passes all SWAP tests, the current player loses immediately.

2. Verification: Run the original verifier $V_{x}$ on $T$ copies of the final transcript $\ket{C_{r}}$ . Accept if at least $T(c+s)/2$ runs accept.

Figure 1: Informal description of the amplified verifier protocol. Intuition: Since the provers send mixed states, there does not exist a deterministic history of states sent so far. Thus, the verifier forces the provers to send a “lookup table” of responses for every possible history. The verifier maintains a specific path called the canonical transcript

\ket{C_{i}}

and uses SWAP tests to query the lookup table for the consistent extension of that path.

Using the above lemma, we now show the containment $\mathsf{pureQPH}\subseteq\mathsf{QPH}$ . The main challenge is that a mixed state behaves like a probability distribution over pure states. For instance, when Bob sends a mixed state proof $\rho=\sum_{i=1}^{m}p_{i}\ket{\psi_{i}}\!\!\bra{\psi_{i}}$ , Alice does not know which $\ket{\psi_{i}}$ the verifier will actually observe. The disentangler of Lemma 23 resolves this issue. If each proof is required to be product across four registers, then, after running the disentangler, the proof can be written in the form $\sum_{i=1}^{m}p_{i}\ket{\zeta_{i}}\!\!\bra{\zeta_{i}}^{\otimes\kappa}$ , where each $\ket{\zeta_{i}}=\ket{\zeta_{i,1}}\otimes\cdots\otimes\ket{\zeta_{i,s}}$ , and, crucially, the number of terms $m$ is polynomially bounded.

This structure means that Alice no longer needs to know which $\ket{\zeta_{i}}$ the verifier observes. Instead, she can provide a response to every possible $\ket{\zeta_{i}}$ simultaneously, encoded in tensor product form. Concretely, the $i$ th message contains a table (in tensor product form) listing all possible transcripts of rounds $1,\dots,i-1$ together with Alice’s corresponding responses. The disentangler ensures enough copies of each transcript are available, and the verifier can then use SWAP tests to select which transcript to use. See Figure 1 for an informal description of the full verifier protocol.

To enforce that each message is a product across four registers, we increase the number of rounds by a factor of $7$ . In other words, we show $\mathsf{pureQ\Sigma_{r}}\subseteq\mathsf{Q\Sigma_{7r}}$ . Within each block of seven quantifiers, we discard every other quantifier (positions $2,4,6$ ) and bundle the remaining four into a single quantifier ranging over product states:

\exists\rho_{1}\forall\rho_{2}\exists\rho_{3}\forall\rho_{4}\exists\rho_{5}% \forall\rho_{6}\exists\rho_{7}\quad\longmapsto\quad\exists\rho=(\rho_{1}% \otimes\rho_{3}\otimes\rho_{5}\otimes\rho_{7})

(30)

Thus, by increasing the number of rounds by a factor of $7$ , we simulate a proof system where the provers send states that are in tensor product across the four registers.

Theorem 16. [Restated, see original statement.]

$\mathsf{pureQ\Sigma_{r}}\subseteq\mathsf{Q\Sigma_{7r}}(c^{\prime},s^{\prime})$ with $c^{\prime}\geq 1-1/q(n)$ and $s^{\prime}\leq 1/q(n)$ , where $q$ is an arbitrary polynomial.

Proof.

Let $A\in\mathsf{pureQ\Sigma_{r}}$ . Then there exist functions $c,s:\mathbb{N}\to[0,1]$ with $c(n)-s(n)\geq n^{-O(1)}$ , a polynomial $p(n)$ , and a polynomial-time uniform family of verifiers $\{V_{x}\}_{x\in\{0,1\}^{*}}$ such that, for every $x\in\{0,1\}^{n}$ , we have


$\displaystyle x$	$\displaystyle\in A_{\mathrm{yes}}\Rightarrow\exists\ket{\psi_{1}}\forall\ket{% \psi_{2}}\dotsm\overline{Q_{r}}\ket{\psi_{r-1}}Q_{r}{\ket{\psi_{r}}}\colon P_{% x}(\ket{\psi_{1}}\!\!\bra{\psi_{1}}\otimes\dotsm\otimes\ket{\psi_{r}}\!\!\bra{% \psi_{r}})\geq c(n),$	(31a)
$\displaystyle x$	$\displaystyle\in A_{\mathrm{no}}\,\Rightarrow\forall\ket{\psi_{1}}\exists\ket{% \psi_{2}}\dotsm Q_{r}\ket{\psi_{r-1}}\overline{Q_{r}}{\ket{\psi_{r}}}\colon P_% {x}(\ket{\psi_{1}}\!\!\bra{\psi_{1}}\otimes\dotsm\otimes\ket{\psi_{r}}\!\!\bra% {\psi_{r}})\leq s(n),$	(31b)

where $Q_{r}=\forall$ if $r$ is even and $Q_{r}=\exists$ if $r$ is odd. Here $P_{x}(\rho)$ denotes the acceptance probability of $V_{x}$ on input state $\rho\in\mathcal{D}(\mathcal{H}^{\otimes r})$ , with $\mathcal{H}=\mathbb{C}^{2^{p(n)}}$ .

We prove that $A\in\mathsf{Q\Sigma_{7r}}(c^{\prime},s^{\prime})$ by constructing a verifier $V_{x}^{\prime}$ that receives $7r$ messages in $\mathcal{D}(\mathcal{H}^{\otimes\ell})$ , where $\ell$ will be determined later (and depend on our application of Lemma 23). As described in Equation 30, the verifier $V_{x}^{\prime}$ discards $3r$ of these messages and simulates an $r$ -round protocol in which each round- $i$ message has the product form $\rho_{i}=\rho_{i,1}\otimes\dotsm\otimes\rho_{i,4}$ . Thus, it suffices to prove


$\displaystyle x$	$\displaystyle\in A_{\mathrm{yes}}$	$\displaystyle\quad\Rightarrow\quad$	$\displaystyle\exists\rho_{1}\dotsm Q_{r}\rho_{r}\colon P^{\prime}_{x}(\rho_{1}% \otimes\dotsm\otimes\rho_{r})\geq c^{\prime}(n),$	(32a)
$\displaystyle x$	$\displaystyle\in A_{\mathrm{no}}$	$\displaystyle\quad\Rightarrow\quad$	$\displaystyle\forall\rho_{1}\dotsm\overline{Q_{r}}\rho_{r}\colon P^{\prime}_{x% }(\rho_{1}\otimes\dotsm\otimes\rho_{r})\leq s^{\prime}(n),$	(32b)

where $P^{\prime}_{x}(\rho)$ denotes the acceptance probability of $V_{x}^{\prime}$ and each $\rho_{i}$ is restricted to the four-register product form above. Given $\rho_{1},\dots,\rho_{r}\in\mathcal{D}(\mathcal{H}^{\otimes\ell})$ as input with $\rho_{i}=\rho_{i,1}\otimes\dots\otimes\rho_{i,4}$ , the verifier $V_{x}^{\prime}$ acts as follows (see Figure 1 for an informal description):

1.
(Determine the canonical transcript) For $i=1,\dots,r$ :
1. (a)
  
  (Disentangle) Let $\Gamma$ denote the disentangler from Lemma 23 with parameters $\kappa=K$ and $\delta$ to be specified later. For the $i$ th iteration, we write $\Gamma_{i}$ , since each application will act on a different-sized Hilbert space. Define $\rho_{i}^{\prime}=\Gamma_{i}(\rho_{i})$ . By Lemma 23, there exists a mixed state $\eta_{i}=\sum_{k=1}^{m_{i}}p_{ik}\ket{\zeta_{i}^{(k)}}\!\!\bra{\zeta_{i}^{(k)}% }^{\otimes K}$ with $m_{i}=O(\delta^{-2})$ such that $\left\lVert\eta_{i}-\rho_{i}^{\prime}\right\rVert_{1}\leq\delta$ . Additionally, each $\ket{\zeta_{i}^{(k)}}$ can be written as $\ket{\zeta_{i}^{(k)}}=\bigotimes_{j=1}^{M_{i}}\ket{T_{{ij}}^{(k)}}\ket{\psi_{% ij}^{(k)}}$ for $M_{i}=M_{i-1}m_{i-1}$ (and $M_{1}=1$ ), $\ket{T_{ij}^{(k)}}\in\mathcal{H}^{\otimes(i-1)}$ , $\ket{\psi_{ij}^{(k)}}\in\mathcal{H}$ . For analysis, fix a pure branch $\ket{\zeta_{i}}=\bigotimes_{j=1}^{M_{i}}\ket{T_{{ij}}}\ket{\psi_{ij}}$ from this distribution (pretending the verifier $V^{\prime}_{x}$ receives a random pure state from the mixed state). Each $\ket{T_{ij}}\ket{\psi_{ij}}$ is a transcript-answer pair; i.e., $\ket{\psi_{ij}}$ is the prover’s message on the $i$ th round conditioned on $\ket{T_{ij}}$ being the transcript for the previous $i-1$ rounds. Note that $M_{i}$ grows with each round because the transcript gets progressively longer each round.
2. (b)
  
  (Select player response to current transcript) If $i=1$ , set $\ket{\phi_{1}}\coloneq\ket{\psi_{i,1}}$ and $\ket{C_{1}}\coloneq\ket{\phi_{1}}$ . Otherwise, for each $j=1,\dots,M_{i}$ , perform $W$ (to be determined later) SWAP tests between $\ket{C_{i-1}}$ and $\ket{T_{ij}}$ (choose $K$ sufficiently large to have enough copies $\ket{C_{i-1}}$ and $\ket{T_{ij}}$ ).⁴⁴4Note that each $\ket{\zeta_{i}}$ contains a copy of each transcript and that we have $K$ copies of $\ket{\zeta_{i}}$ . If all SWAP tests accept for some $j$ , set $\ket{C_{i}}\coloneq\ket{T_{ij}}\otimes\ket{\psi_{ij}}$ . Else, let the current player lose, i.e., accept if $i$ is even and reject if $i$ is odd.
2.

Simulate $V_{x}$ on fresh copies of $\ket{C_{r}}$ $T$ times and accept if the number accepting runs, $N_{\mathrm{acc}}$ , satisfies $N_{\mathrm{acc}}\geq T(c+s)/2$ .

Completeness. Let $x\in A_{\mathrm{yes}}$ . By Equation 31a, Alice (first player, odd rounds) can always win with probability at least $c(n)$ , regardless of which pure state Bob sends in the even rounds. Let $\ket{\alpha_{1}}$ be the best state Alice can choose in round $1$ . For any Bob message $\ket{\beta_{2}}$ in round $2$ , there exists $\ket{\alpha_{3}(\beta_{2})}$ , such that Alice can win with probability $\geq c(n)$ . Inductively define $\ket{\alpha_{i}(\beta_{2},\dots,\beta_{i-1})}$ as Alice’s best response in round $i$ , given Bob’s messages $\ket{\beta_{2}},\dots,\ket{\beta_{i-1}}$ and Alice’s messages $\ket{\alpha_{1}},\dots,\ket{\alpha_{i-2}(\beta_{2},\dots,\beta_{i-3})}$ .

We need to show that Equation 32a holds. We can analyze $V_{x}^{\prime}$ on the disentangled states as

\big\lvert P_{x}^{\prime}(\rho_{1}\otimes\dotsm\otimes\rho_{r})-P_{x}^{\prime% \prime}(\eta_{1}\otimes\dotsm\otimes\eta_{r})\big\rvert\leq r\delta/2,

(33)

where $P_{x}^{\prime\prime}(\eta_{1}\otimes\dotsm\otimes\eta_{r})$ denotes the acceptance probability of $V_{x}^{\prime}$ when each $\rho_{i}^{\prime}$ is replaced by $\eta_{i}$ . For Alice’s rounds, we can assume $\eta_{i}=\rho_{i}^{\prime}=\Gamma_{i}(\rho_{i})$ since Alice can always send a state of the correct product form. Further, Alice’s answer in round $i$ may depend on $\eta_{1},\dots,\eta_{i-1}$ , since $\rho_{j}^{\prime}$ only depends on $\rho_{j}$ , and the $\rho_{j}^{\prime}\approx\eta_{j}$ approximation is merely an analytical tool and so Alice can choose any $\eta_{i}$ satisfying Lemma 23.

For $\rho_{1}$ , Alice simply sends $4\ell$ copies of $\ket{\alpha_{1}}$ . Now consider odd round $i>1$ . There are $M_{i}=M_{i-1}m_{i-1}$ possible choices for the canonical transcript $\ket{C_{i-1}}$ (which includes Bob’s message) after round $i-1$ . Alice sends $4\ell$ copies of $\bigotimes_{j=1}^{M_{i}}\ket{T_{ij}}\ket{\alpha(T_{ij})}$ , where $\ket{\alpha(T_{ij})}$ denotes Alice’s best answer given transcript $\ket{T_{ij}}$ in the first $i-1$ rounds. This let’s Alice pass the SWAP test in (1b) with probability $1$ (in the $P_{x}^{\prime\prime}(\eta_{1}\otimes\dotsm\otimes\eta_{r})$ analysis with $\eta_{i}$ chosen by Alice).

We argue that $V_{x}^{\prime}$ always chooses a transcript that is accepted with probability almost $c$ . There are two sources of error. The first is Bob cheating and altering the transcript, so that the verifier selects $\ket{T_{ij}}\neq\ket{C_{{i-1}}}$ in step (1b) of Bob’s round. For $d_{\mathrm{tr}}(\ket{T_{ij}}\!\!\bra{T_{ij}},\ket{C_{i-1}}\!\!\bra{C_{i-1}})\leq\varepsilon$ , Alice’s chance of winning decreases by at most $\varepsilon$ . If $d_{\mathrm{tr}}(\ket{T_{ij}}\!\!\bra{T_{ij}},\ket{C_{i-1}}\!\!\bra{C_{i-1}})=% \sqrt{1-\lvert\braket{C_{i-1}|T_{ij}}\rvert^{2}}\geq\varepsilon$ , then $\lvert\braket{C_{i-1}|T_{ij}}\rvert^{2}\leq 1-\varepsilon^{2}$ and the probability of all $W$ SWAP tests accepting is

\left\lparen\frac{1}{2}+\frac{1}{2}\lvert\braket{C_{i-1}|T_{ij}}\rvert^{2}% \right\rparen^{W}\leq\left\lparen 1-\frac{\varepsilon^{2}}{2}\right\rparen^{W}% \leq e^{-W\varepsilon^{2}/2}\leq\frac{1}{4qrM_{r}}

(34)

for $W=\lceil 2\varepsilon^{-2}\ln(4qrM_{r})\rceil$ with $\varepsilon=\gamma/4r$ and $\gamma=c-s$ . The second source of error is (1b) choosing a wrong $\ket{T_{ij}}$ for $\ket{C_{i}}$ in Alice’s round. Alice does not lose in (1b), but there may be multiple $\ket{T_{ij}}$ close to $\ket{C_{i-1}}$ . Again, Alice’s winning probability decreases by at most $d_{\mathrm{tr}}(\ket{T_{ij}}\!\!\bra{T_{ij}},\ket{C_{i-1}}\!\!\bra{C_{i-1}})$ , and the probability of choosing a “bad” transcript is bounded by Equation 34. We can take the union bound over all rounds and entries in the tables to bound the probability that a bad transcript is selected by $1/(4q)$ . Thus, Alice’s winning probability decreases at most $r\varepsilon=\gamma/4$ in total, which gives $\mathop{\bf Pr\/}[P_{x}(C_{r})\geq c-\gamma/4]\geq 1-\frac{1}{4q},$ where the probability is taken over the choice of $\ket{\zeta_{i}^{(k)}}$ in step (1a) and outcome of the SWAP tests in (1b). Assuming $P_{x}(C_{r})\geq c-\gamma/4$ and thus $\mathop{\bf E\/}[N_{\mathrm{acc}}]\geq(c-\gamma/4)T$ , the probability of $V^{\prime}_{x}$ rejecting in step 2 can be bounded with Hoeffding’s inequality

\mathop{\bf Pr\/}[N_{\mathrm{acc}}\leq(c-\gamma/2)T]\leq\exp\left\lparen-\frac% {2(\gamma T/4)^{2}}{T}\right\rparen\leq\exp(-\gamma^{2}T/8)\leq\frac{1}{4q},

(35)

for $T=\lceil 8\gamma^{-2}\ln(4q)\rceil$ . Setting $\delta=1/(rq)$ , and taking into account the disentangler error $1/(2q)$ of Equation 33, Alice wins with probability $\geq 1-1/q$ . We have now assigned all parameters to polynomials in $n$ . For all of the SWAP tests and simulations of $V_{x}$ , we need $K\geq W\cdot rM_{r}+T$ copies of each message. Note $M_{i}$ grows exponentially in $r=O(1)$ .

Soundness. For $x\in A_{\mathrm{no}}$ the analysis is analogous, just swapping the roles of Alice and Bob, i.e., “ $\exists$ ” is now Bob. The only difference is that now the second player wins, which is insignificant for the above analysis. $\hfill\blacktriangleleft$

5 Quantified Hamiltonian Complexity

In this section, we initiate the study of quantified Hamiltonian problems. Our primary motivation is to identify complete problems for the various definitions of $\mathsf{QPH}$ to better understand these classes and the relationship among their different variants. At the same time, quantified Hamiltonian problems are natural in their own right: they naturally generalize quantified Boolean formulae from classical complexity theory [33] to the quantum Hamiltonian setting. From a physical perspective, these problems capture robust versions of ground-state questions. For example, these problems allow us to ask: “Does there exist a state on one subsystem such that, no matter how the rest of the system is perturbed, the total system remains in a low-energy state?”

5.1 Quantified Hamiltonian Problems

We now formally define the quantified Hamiltonian problems studied in this work. There are four natural variants we consider, determined by the following choices: (i) whether the quantified states are restricted to be pure or may be mixed, and (ii) whether the Hamiltonian is local or sparse. Our definitions generalize the separable local Hamiltonian problem (or $\exists\exists$ -PLH in our notation) and separable sparse Hamiltonian problem (or $\exists\exists$ -PSH) of Chailloux and Sattath [12] to the alternating quantifier setting. Note that pure/mixed makes no difference in the $\exists\exists$ case due to convexity.

Definition 24 ( $\exists\forall$ - $k$ -LH).

Let $2n$ be the number of qubits, $k\geq 1$ a fixed constant, and $a,b\in\mathbb{R}$ satisfying $b-a\geq 1/\mathrm{poly}(n)$ . Given a $k$ -local Hamiltonian $H$ as input, the task is to decide, under the promise that one of these holds:

$\blacksquare$

(YES case): $\exists\rho\forall\sigma\colon\mathrm{tr}(H(\rho\otimes\sigma))\leq a$ , or
$\blacksquare$

(NO case): $\forall\rho\exists\sigma\colon\mathrm{tr}(H(\rho\otimes\sigma))\geq b$ .

We write $\exists\forall$ - $k$ -MLH (mixed, local Hamiltonian) for the version where $\rho$ and $\sigma$ may be mixed states and $\exists\forall$ - $k$ -PLH (pure, local Hamiltonian) for the version where $\rho=\ket{\psi}\!\!\bra{\psi}$ and $\sigma=\ket{\phi}\!\!\bra{\phi}$ are pure states.

To move from local to sparse Hamiltonians, we replace the locality constraint with a sparsity condition on the input operator.

Definition 25 (Row-sparse operators).

An operator $A$ is row-sparse if:

$\blacksquare$

Each row of $A$ has at most $\mathrm{poly}(n)$ nonzero entries, and
$\blacksquare$

There exists a polynomial-time algorithm which, given a row index $i$ , outputs the list of all pairs $(i,A_{ij})$ such that $A_{ij}\neq 0$ .

We can now extend the quantified local Hamiltonian problems to their sparse-Hamiltonian counterparts. We define the problems below for an arbitrary constant number of quantifiers, as we will later prove completeness at every level.

Definition 26 (Quantified sparse Hamiltonian problems).

Let $i\in\mathbb{N}$ and fix a polynomial $q$ . The promise problem $\mathsf{MSH\mathchar 45\relax\Sigma}_{i}$ is defined as follows:

$\blacksquare$

(Input): A $d$ -sparse Hamiltonian $H$ on $n=n_{1}+\dotsm+n_{i}$ qubits with $\lVert H\rVert_{\mathrm{max}}\leq q(n)$ , thresholds $a,b\in\mathbb{R}$ with $b-a\geq 1/q(n)$ , and $H$ is defined by a circuit that given $r$ outputs all entries in row $r$ (see Definition 25).⁵⁵5The parameters $d, n$ are implicitly bounded in terms of input size via the circuit description of $H$ .
$\blacksquare$

(YES case): $\exists\rho_{1}\forall\rho_{2}\dotsm Q_{i}\colon\mathrm{tr}(H(\rho_{1}\otimes% \dotsm\otimes\rho_{i}))\leq a$ .
$\blacksquare$

(NO case): $\forall\rho_{1}\exists\rho_{2}\dotsm\overline{Q_{i}}\rho_{i}\colon\mathrm{tr}(% H(\rho_{1}\otimes\dotsm\otimes\rho_{i}))\geq b$ .

Here, $Q_{i}$ is $\exists$ when $i$ is odd and $\forall$ when $i$ is even, and $\overline{Q_{i}}$ is the complementary quantifier. Each $\rho_{j}$ is quantified over $\mathcal{D}(\mathcal{H}_{j})$ with $\mathcal{H}_{j}=\mathbb{C}^{2^{n_{j}}}$ .

The pure variant $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ is defined identically, except that $\rho_{1},\dots,\rho_{i}$ are restricted to pure states. Finally, $\mathsf{MSH\mathchar 45\relax\Pi}_{i}$ and $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ are obtained by inverting all quantifiers.

Generally, a problem is in $\mathsf{pureQ\Sigma_{i}}$ if and only if its complement is in $\mathsf{pureQ\Pi_{i}}$ . Although $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ is not equal to the complement of $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ , there is a trivial poly-time reduction.

Lemma 27.

$\mathsf{PSH\mathchar 45\relax\Pi}_{i}\leq_{p}\overline{\mathsf{PSH\mathchar 45% \relax\Sigma}_{i}}$ and $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}\leq_{p}\overline{\mathsf{PSH\mathchar 4% 5\relax\Pi}_{i}}$ for all $i\in\mathbb{N}$ , i.e., $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ is the complement of $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ , up to poly-time many-one (aka Karp) reductions. The analogous statement holds for the mixed/sparse, pure/local, and mixed/local variants.

Proof.

$(H,a,b)\in(\mathsf{PSH\mathchar 45\relax\Pi}_{i})_{\mathrm{yes}}\;% \Longleftrightarrow\;(-H,-b,-a)\in(\mathsf{PSH\mathchar 45\relax\Sigma}_{i})_{% {\mathrm{no}}}$ follows directly from Definition 26. $\hfill\blacktriangleleft$

In the remainder of this section, we establish containment and hardness results for the quantified Hamiltonian problems defined above. The results we obtain for the two-quantifier versions are summarized in Table 1; generalizing these to more quantifiers is relatively straightforward.

Table 1: Variants of the

\exists\forall

-quantified Hamiltonian problems. All variants are contained in

\mathsf{PSPACE}

except for the pure/sparse case, where the best known upper bound is

\mathsf{NEXP}

.

	Local	Sparse
Mixed	$\in\mathsf{NP}^{\mathsf{QMA}}\cap\mathsf{coNP}^{\mathsf{QMA}}$ (Corollary 31)	$\in\mathsf{Q\Sigma_{2}}$ (Proposition 33)
Pure	$\in\mathsf{NP}^{\mathsf{pureSuperQMA}}$ (Proposition 32)	$\mathsf{pureQ\Sigma_{2}}$ -complete (Theorem 37)

5.2 Quantified Local Hamiltonian: $\mathsf{NP}$ with a $\mathsf{QMA}$ Oracle

We begin by analyzing the pure/local and mixed/local variants of the quantified Hamiltonian problem. In particular, we show that these solved by oracle classes of the form $\mathsf{NP}^{O}$ for a promise class $O$ , and we refer the reader to Definition 13 for a definition of $\mathsf{NP}$ with an oracle to a promise class.

A key step in our proofs is checking the consistency of local density matrices: given a collection of reduced density matrices, does there exist a global quantum state that is consistent with all of them? If the global state is allowed to be mixed, checking consistency is known to be $\mathsf{QMA}$ -complete [29, 9]. If, instead, one must decide whether there exists a global pure state consistent with the reduced density matrices, the problem is $\mathsf{pureSuperQMA}$ -complete [23].⁶⁶6In $\mathsf{pureSuperQMA}$ , the verifier runs $\mathrm{poly}$ -many circuit checks on the same pure witness state that all must accept with probability exactly $1/2$ in the YES case. In the NO case, at least one check has acceptance probability bounded away from $1/2$ . See [23] for a formal definition.

Because the Hamiltonian is local, each term in $H$ acts on only a constant number of qubits. This means that for any purported proof state, it suffices for the prover to supply the reduced density matrices on just those local subsystems. The first witness for the quantified Hamiltonian problem can therefore be succinctly described by a classical list of local density matrices. The remaining task – verifying that these matrices are consistent with a true quantum state – can be outsourced to a $\mathsf{QMA}$ oracle. We formalize this now.

Proposition 28.

$\exists\forall$ - $k$ - $\mathrm{MLH}\in\mathsf{NP}^{\|\mathsf{QMA}[2]}$ .

Proof.

Let $H=\sum_{i}H_{i}$ be the given $k$ -local Hamiltonian. The $\mathsf{NP}$ prover provides the collection of reduced density matrices of the candidate state $\rho$ on the supports of the local terms $H_{i}$ .

First, the verifier checks that these reduced density matrices are consistent with some global state. This can be done using a single $\mathsf{QMA}$ query, since consistency of local density matrices is $\mathsf{QMA}$ -complete [29, 9].

Next, for each term $H_{i}$ , the verifier computes an effective operator $H_{i}^{\prime}\;=\;\sum_{j}p_{ij}\,\bra{\psi_{ij}}H_{i}\ket{\psi_{ij}},$ where $\rho_{i}=\sum_{j}p_{ij}\ket{\psi_{ij}}\!\!\bra{\psi_{ij}}$ is the reduced density matrix of $\rho$ on the qubits that $H_{i}$ acts upon. Let $H^{\prime}=\sum_{i}H_{i}^{\prime}$ . Then $H^{\prime}$ is an operator acting only on the Hilbert space corresponding to the $\forall$ -prover’s state $\sigma$ .

Finally, the verifier queries a $\mathsf{coQMA}$ oracle to check whether $\forall\sigma\colon\mathrm{tr}(H^{\prime}\sigma)\;\geq\;b.$ Since the procedure requires only one $\mathsf{QMA}$ query (for consistency) and one $\mathsf{coQMA}$ query (which can be implemented using $\mathsf{QMA}$ ), the entire protocol lies in $\mathsf{NP}^{\|\mathsf{QMA}[2]}$ . $\hfill\blacktriangleleft$

It turns out that $\mathsf{NP}^{\|\mathsf{QMA}[2]}=\mathsf{NP}^{\mathsf{QMA}}$ . It is not clear whether a single query in Proposition 29 suffices to simulate $\mathsf{NP}^{\mathsf{QMA}}$ , because one query is a $\mathsf{QMA}$ -query and the other is a $\mathsf{coQMA}$ -query. The proof is given in the full version [17].

Proposition 29.

$\mathsf{NP}^{\mathsf{QMA}}\subseteq\mathsf{NP}^{\|\mathsf{QMA}[2]}$ .

By Lemma 27, we immediately get an analogous result for $\forall\exists$ - $k$ -MLH.

Proposition 30.

$\forall\exists$ - $k$ - $\mathrm{MLH}\in\mathsf{coNP}^{\mathsf{QMA}}$ .

Proof.

Because $\exists\forall$ - $k$ -MLH is in $\mathsf{NP}^{\mathsf{QMA}}$ , it’s immediate that $\overline{\exists\forall\text{-$k$-MLH}}$ is in $\mathsf{coNP}^{\mathsf{QMA}}$ . Lemma 27 implies that there is a reduction from $\forall\exists$ - $k$ -MLH to $\overline{\exists\forall\text{-$k$-MLH}}$ , which completes the proof. $\hfill\blacktriangleleft$

Corollary 31.

$\exists\forall$ - $k$ - $\mathrm{MLH}\in\mathsf{NP}^{\mathsf{QMA}}\cap\mathsf{coNP}^{\mathsf{QMA}}$ .

Proof.

By a min-max theorem (e.g., [18, Theorem 2.2]), we have that $\exists\forall$ -MLH = $\forall\exists$ -MLH. Thus, Propositions 28 and 30 implies the result. $\hfill\blacktriangleleft$

An argument essentially identical to that of Proposition 28 yields the following containment for the pure/local case.

Proposition 32.

$\exists\forall$ - $k$ - $\mathrm{PLH}\in\mathsf{NP}^{\|\mathsf{pureSuperQMA}[2]}$ .

Here, one query to the $\mathsf{pureSuperQMA}$ oracle verifies that the provided local density matrices are consistent with some global pure state (a complete problem for $\mathsf{pureSuperQMA}$ [23]), and a second $\mathsf{coQMA}$ query is used exactly as in the proof of Proposition 28. We omit the details, since the argument carries over verbatim.

We remark that, unlike in the mixed-state case, we do not obtain containment in $\mathsf{NP}^{\mathsf{pureSuperQMA}}\cap\mathsf{coNP}^{\mathsf{pureSuperQMA}}$ , because the minimax theorem invoked in Corollary 31 does not apply when the proofs are restricted to pure states.

At present, there is no known approach to proving hardness for the intersection class $\mathsf{NP}^{\mathsf{QMA}}\cap\mathsf{coNP}^{\mathsf{QMA}}$ . Moreover, such hardness results appear unlikely: we do not know of any complete problems for even $\mathsf{NP}\cap\mathsf{coNP}$ and if the $\exists\forall$ -MLH problem were hard for either $\mathsf{NP}^{\mathsf{QMA}}$ or $\mathsf{coNP}^{\mathsf{QMA}}$ , it would imply $\mathsf{NP}^{\mathsf{QMA}}=\mathsf{coNP}^{\mathsf{QMA}}$ , an equality that seems implausible.

5.3 Quantified Sparse Hamiltonian: Complete Problems for $\mathsf{pureQPH}$

We now turn to the sparse variants of the quantified Hamiltonian problem. Our first result establishes that the $\exists\forall$ -mixed sparse Hamiltonian problem lies in $\mathsf{Q\Sigma_{2}}$ . More significantly, we prove that the quantified pure sparse Hamiltonian (PSH) problems are complete for each level of the pure quantum polynomial hierarchy. That is, for every $i\in\mathbb{N}$ , $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ is $\mathsf{pureQ\Sigma_{i}}$ -complete and $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ is $\mathsf{pureQ\Pi_{i}}$ -complete. This gives the first natural family of complete problems for $\mathsf{pureQPH}$ .

Proposition 33.

$\exists\forall$ - $\mathrm{MSH}$ is contained in $\mathsf{Q\Sigma_{2}}$ .

Proof.

The proof is identical to the containment result give in Theorem 37 (below); we defer the details to that proof. $\hfill\blacktriangleleft$

Our completeness result requires the following lemmas. The first lemma is a simple but useful structural fact: if two registers are almost symmetric, then one register must be close to containing a copy of the other. This lets us “pull out” a clean copy of a state whenever the verifier enforces near-symmetry via a SWAP test. The proof is given in the full version [17].

Lemma 34.

Let $\ket{\psi}\in\mathcal{H}_{A}$ and $\ket{\phi}\in\mathcal{H}_{B}\otimes\mathcal{H}_{C}$ with $\mathcal{H}_{A}\cong\mathcal{H}_{B}$ , and $\Pi_{\mathrm{sym}}$ denote the projector onto the symmetric subspace. If $\mathrm{tr}((\Pi_{\mathrm{sym}})_{AB}(\ket{\psi}\!\!\bra{\psi}\otimes\ket{\phi% }\!\!\bra{\phi}))\geq 1-\varepsilon>1/2$ , then there exists $\ket{\phi_{2}}\in\mathcal{H}_{C}$ , such that $d_{\mathrm{tr}}(\ket{\phi},\ket{\psi,\phi_{2}})\leq\sqrt{2\varepsilon}$ .

Next, we recall Kitaev’s circuit-to-Hamiltonian construction, which is the backbone of essentially all Hamiltonian complexity reductions.

Lemma 35 (Kitaev’s circuit-to-Hamiltonian mapping [26]⁷⁷7This lemma is only implicit [26]. A direct proof can be found in [30, Remark 3.3].).

Let $V=U_{m}\dotsm U_{1}$ be a quantum circuit of $m$ $2$ -local gates with $a$ ancilla qubits and $b$ input qubits. Then there exists a Hamiltonian $H^{(V)}$ that is the sum of $O(m)$ $5$ -local projectors, such that

\ker H=\mathrm{span}\left\{\frac{1}{\sqrt{m+1}}\sum_{t=0}^{m}U_{t}\dotsm U_{1}% (\ket{0^{a}}_{\mathcal{A}}\ket{\psi}_{\mathcal{B}})\otimes\ket{1^{t}0^{m-t}}_{% \mathcal{C}}\middle|\ket{\psi}\in\mathbb{C}^{2^{b}}\right\},

(36)

where $\mathcal{A}$ is the ancilla register, $\mathcal{B}$ is the input register, and $\mathcal{C}$ is the clock register. $H^{(V)}$ has a spectral gap of $\Omega(1/m^{2})$ .

The final tool we need is a variant of the well-known Projection Lemma, which frequently appears in Hamiltonian complexity.

Lemma 36 (State Projection Lemma [23]).

Let $H=H_{1}+H_{2}$ be the sum of two Hamiltonians acting on Hilbert space $\mathcal{H}=\mathcal{S}\oplus\mathcal{S}^{\perp}$ , where $\mathcal{S}$ is the kernel of $H_{2}$ and the other eigenvalues are at least $J$ . Let $\rho$ be a state in $\mathcal{H}$ such that $\mathrm{tr}(H\rho)\leq\varepsilon$ . Then there exists a state $\sigma$ (pure if $\rho$ is pure) in $\mathcal{S}$ , such that $d_{\mathrm{tr}}(\rho,\sigma)\leq\delta$ and $\mathrm{tr}(H\sigma)\leq\varepsilon+2\delta\left\lVert H_{1}\right\rVert$ , for $\delta=\sqrt{(\varepsilon+\left\lVert H_{1}\right\rVert)/J}$ .

We are now ready to prove our completeness result.

Theorem 37.

$\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ is $\mathsf{pureQ\Sigma_{i}}$ -complete and $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ is $\mathsf{pureQ\Pi_{i}}$ -complete.

Proof.

Containment. $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}\in\mathsf{pureQ\Sigma_{i}}$ is completely analogous to the containment of the Separable Sparse Hamiltonian problem (i.e. $\exists\exists\mathchar 45\relax\mathrm{PSH}$ ) in $\mathsf{QMA}(2)$ [12]. Given $d$ -sparse $n$ -qubit Hamiltonian $H$ with $0\preceq H\preceq I$ and error $\varepsilon$ , [12] constructs a circuit $Q$ (using Hamiltonian simulation and phase estimation) that runs in time $\mathrm{poly}(d,n,\varepsilon^{-1})$ , such that for all states $\ket{\psi}$ , we have $\big\lvert\mathop{\bf Pr\/}[Q\text{ accepts }\ket{\psi}]-\bra{\psi}H\ket{\psi}% \big\rvert\leq\varepsilon.$ So all the $\mathsf{pureQ\Sigma_{i}}$ -verifier needs to do is normalize the input Hamiltonian to satisfy $0\preceq H\preceq I$ and simulate $Q$ with $\varepsilon=1/(4q(n))$ , which gives a promise gap of $1/(2q(n))$ .

Hardness. Let $i\in\mathbb{N}$ . We will show $\mathsf{PSH\mathchar 45\relax\Pi}_{i}$ is $\mathsf{pureQ\Pi_{i}}$ -hard for even $i$ , and $\mathsf{PSH\mathchar 45\relax\Sigma}_{i}$ is $\mathsf{pureQ\Sigma_{i}}$ -hard for odd $i$ . The other two cases follow by Lemma 27. Let $i$ be even and $A\in\mathsf{pureQ\Pi_{i}}$ (the proof for odd $i$ and $A\in\mathsf{pureQ\Sigma_{i}}$ is completely analogous). Given $x\in\{0,1\}^{n}$ , we construct Hamiltonian $H_{x}$ in time $\mathrm{poly}(n)$ , such that for $a, b$ to be determined later,


$\displaystyle x$	$\displaystyle\in A_{\mathrm{yes}}$	$\displaystyle\quad\Rightarrow\quad$	$\displaystyle(H_{x},a,b)\in(\mathsf{PSH\mathchar 45\relax\Pi}_{i})_{\mathrm{% yes}}$	(37a)
$\displaystyle x$	$\displaystyle\in A_{\mathrm{no}}$	$\displaystyle\quad\Rightarrow\quad$	$\displaystyle(H_{x},a,b)\in(\mathsf{PSH\mathchar 45\relax\Pi}_{i})_{\mathrm{no}}$	(37b)

There exists a poly-time uniform family of verifiers $\{V_{x}\}$ , such that


$\displaystyle x$	$\displaystyle\in A_{\mathrm{yes}}$	$\displaystyle\quad\Rightarrow\quad$	$\displaystyle\forall\ket{\psi_{1}}\exists\ket{\psi_{2}}\dotsm\forall\ket{\psi_% {i-1}}\exists{\ket{\psi_{i}}}\colon P_{x}(\psi_{1}\otimes\dotsm\otimes\psi_{i}% )\geq c(n),$	(38a)
$\displaystyle x$	$\displaystyle\in A_{\mathrm{no}}$	$\displaystyle\quad\Rightarrow\quad$	$\displaystyle\exists\ket{\psi_{1}}\forall\ket{\psi_{2}}\dotsm\exists\ket{\psi_% {i-1}}\forall{\ket{\psi_{i}}}\colon P_{x}(\psi_{1}\otimes\dotsm\otimes\psi_{i}% )\leq s(n),$	(38b)

where $P_{x}(\rho)$ denotes the acceptance probability of $V_{x}$ on input $\rho$ . Let $m\leq n^{O(1)}$ be the number of gates of $V_{x}$ and $p<m$ (without loss of generality) the number of qubits in each message. Denote the $i$ message registers of $V_{x}$ by $\mathcal{B}_{1},\dots,\mathcal{B}_{i}$ of $p$ qubits each. The Hamiltonian $H$ will act on registers $\mathcal{H}_{1}=\mathcal{B}_{1},\dots,\mathcal{H}_{i-1}=\mathcal{B}_{i-1},% \mathcal{H}_{i}=\mathcal{A}\mathcal{B}\mathcal{C}$ , where $\mathcal{A}$ is the ancilla register of $n_{\mathcal{A}}\leq m$ qubits, $\mathcal{B}=\mathcal{B}_{1}\dots\mathcal{B}_{i}$ is the input register to $V$ of $i p$ qubits, and $\mathcal{C}$ is the clock register of $m$ qubits. In terms of Definition 26, we have $n_{1}=\dotsm=n_{i-1}=p$ and $n_{i}=ip+m+n_{\mathcal{A}}$ . Finally define the Hamiltonian

H_{x}=\ket{0}\!\!\bra{0}_{\mathcal{A}_{1}}\otimes\ket{1}\!\!\bra{1}_{\mathcal{% C}_{m}}+J_{1}\ket{0}\!\!\bra{0}_{\mathcal{C}_{1}}\otimes(I-\Pi_{\mathrm{sym}})% _{\mathcal{H}_{1}\dots\mathcal{H}_{i-1},\mathcal{B}_{1}\dots\mathcal{B}_{i-1}}% +J_{2}H^{(V_{x})}_{\mathcal{A}\mathcal{B}\mathcal{C}},

(39)

with $H^{(V_{x})}$ from Lemma 35, $\Pi_{\mathrm{sym}}$ the projector onto the symmetric subspace across the cut $\mathcal{H}_{1}\dots\mathcal{H}_{i-1}$ / $\mathcal{B}_{1}\dots\mathcal{B}_{i-1}$ , and sufficiently large $1\ll J_{1}\ll J_{2}\leq n^{O(1)}$ . $H_{x}$ is $O(m)$ -sparse since $H^{(V_{x})}$ is local and has $O(m)$ terms, and $\Pi_{\mathrm{sym}}$ is $2$ -sparse.

Let $a=(1-c)/(m+1)$ and $b=(1-c+\gamma/4)/(m+1)$ , where $\gamma=c-s$ . Note that the gap $b-a\geq 1/q(n)$ and bound $\lVert H_{x}\rVert_{\mathrm{max}}\leq O(J_{2}m)\leq q(n)$ for $n=n_{1}+\dotsm+n_{i}$ can be achieved by padding the last message (i.e. increasing $n_{i}$ ) and letting $H_{x}$ act as identity on the padding qubits. We lose purity of the last message, but that is not an issue since Equations 38a and 38b are still true when replacing the pure $\ket{\psi_{i}}$ with a mixed $\rho_{i}$ (by convexity).

For $x\in A_{\mathrm{yes}}$ , we have Equation 38a we argue that

\forall\ket{\phi_{1}}\exists\ket{\phi_{2}}\dotsm\forall\ket{\phi_{i-1}}\exists% \ket{\phi_{i}}\colon\mathrm{tr}\bigl(H(\phi_{1}\otimes\dotsm\otimes\phi_{i})% \bigr)\leq a,

(40)

holds with $\ket{\psi_{j}}\in\mathcal{H}_{j}$ for all $j\in[i]$ . For rounds $2,4,\dots,i-2$ , Alice (taking the game interpretation with Bob as first player ( $\forall$ ) and Alice as second player $(\exists)$ ) can simply send the same response as in (38a), i.e., $\ket{\phi_{j}}=\ket{\psi_{j}}$ for even $j<i$ . In the last round, Alice sends a valid history state of the form

\ket{\phi_{i}}=\frac{1}{\sqrt{m+1}}\sum_{t=0}^{m}U_{t}\dotsm U_{1}(\ket{0}_{% \mathcal{A}}\ket{\psi_{1},\dots,\psi_{i}}_{\mathcal{B}})\otimes\ket{1^{t}0^{m-% t}}_{\mathcal{C}},

(41)

where $\ket{\psi_{i}}$ corresponds to Alice’s last message in (38a), and $U_{1},\dots,U_{m}$ are the gates of $V_{x}$ with output register $\mathcal{A}_{1}$ . Then we get $\mathrm{tr}(H_{x}(\phi_{1}\otimes\dotsm\otimes\phi_{i}))\leq(1-c)/(m+1)$ since $V_{x}$ rejects $\ket{\psi_{1},\dots,\psi_{i}}$ with probability $\leq 1-c$ .

Now consider $x\in A_{\mathrm{no}}$ and assume

\forall\ket{\phi_{1}}\exists\ket{\phi_{2}}\dotsm\forall\ket{\phi_{i-1}}\exists% \ket{\phi_{i}}\colon\mathrm{tr}\bigl(H(\phi_{1}\otimes\dotsm\otimes\phi_{i})% \bigr)<b.

(42)

We will show that this contradicts Equation 38b. Let $\ket{\phi}=\ket{\phi_{1},\dots,\phi_{i}}$ , and $\varepsilon=\gamma/(8(m+1))$ . By Lemmas 35 and 36 and choosing sufficiently large $J_{2}\in\mathrm{poly}(J_{1},m,\gamma^{-1})$ , there exists a state $\ket{\phi_{i}^{\prime}}$ , such that for some input state $\ket{\eta}$ :

		$\displaystyle\ket{\phi_{i}^{\prime}}=\frac{1}{\sqrt{m+1}}\sum_{t=0}^{m}U_{t}% \dotsm U_{1}\ket{0}_{\mathcal{A}}\ket{\eta}_{\mathcal{B}}\otimes\ket{1^{t}0^{m% -t}}_{\mathcal{C}},$		(43)
		$\displaystyle\quad d_{\mathrm{tr}}\bigl(\ket{\phi_{i}},\ket{\phi_{i}^{\prime}}% \bigr)\leq\varepsilon,\quad\text{and }\;\mathrm{tr}\bigl(J_{1}(I-\Pi_{\mathrm{% sym}})(\phi_{1}\otimes\dotsm\otimes\phi_{i-1}\otimes\phi_{i}^{\prime})\bigr)% \leq b+J_{1}\varepsilon.$		(43)

By Lemma 34 and choosing sufficiently large $J_{1}$ , there exists a state $\ket{\eta_{i}}$ , such that

d_{\mathrm{tr}}(\ket{\phi_{1},\dots,\phi_{i-1},\eta_{i}},\ket{\eta})\leq\varepsilon,

(44)

and therefore $d_{\mathrm{tr}}(\ket{\phi_{i}},\ket{\phi_{i}^{\prime\prime}})\leq 2\varepsilon$ , with

\ket{\phi_{i}^{\prime\prime}}=\frac{1}{\sqrt{m+1}}\sum_{t=0}^{m}U_{t}\dotsm U_% {1}\ket{0}_{\mathcal{A}}\ket{\phi_{1},\dots,\phi_{i-1},\eta_{i}}_{\mathcal{B}}% \otimes\ket{1^{t}0^{m-t}}_{\mathcal{C}}.

(45)

Hence,

\mathrm{tr}\bigl(H(\phi_{1}\otimes\dotsm\otimes\phi_{i-1}\otimes\phi_{i}^{% \prime\prime})\bigr)=\frac{1}{m+1}\bigl(1-P_{x}(\phi_{1}\otimes\dotsm\otimes% \phi_{i-1}\otimes\eta_{i})\bigr)\leq b+2\varepsilon.

(46)

Thus, $P_{x}(\phi_{1}\otimes\dotsm\otimes\phi_{i-1}\otimes\eta_{i})\geq c-\gamma/4-% \gamma/4=c-\gamma/2=s+\gamma/2$ . Therefore,

\forall\ket{\psi_{1}}\exists\ket{\psi_{2}}\dotsm\forall\ket{\psi_{i-1}}\exists% \ket{\eta_{i}}:P_{x}(\psi_{1}\otimes\dotsm\otimes\psi_{i-1}\otimes\eta_{i})% \geq s+\gamma/2,

(47)

which means that Alice can win with probability at least $s+\gamma/2$ by choosing the even messages $\ket{\psi_{2}}=\ket{\phi_{2}},\dots,\ket{\psi_{i-2}}=\ket{\phi_{i-2}},\ket{% \psi_{i}}=\ket{\eta_{i}}$ with $\ket{\phi_{1}},\dots,\ket{\phi_{i}}$ as in Equation 42, and $\ket{\eta_{i}}$ as in Equation 44. This contradicts Equation 38b. $\hfill\blacktriangleleft$

We note that proving that $\exists\forall$ -MSH is $\mathsf{Q\Sigma_{2}}$ -hard seems out of reach with current techniques. Theorem 37 relies on the SWAP test, but this approach fails in the mixed-state setting, because the SWAP test fails to check equality of mixed states. Any hardness proof would therefore require fundamentally new ideas.

6 Open Problems

1.

Are there complete problems for variants of the quantum polynomial hierarchy beyond $\mathsf{pureQPH}$ ? For example, can the pure/local, mixed/local, or mixed/sparse Hamiltonian problems be shown complete for any class?
2.

It is striking that the local variants of the quantified Hamiltonian problem only required quantum computation in the oracle part of the machine. For instance, in Proposition 32, the base machine is merely $\mathsf{NP}$ . A natural direction is to better understand the relationship between $\mathsf{NP}^{\mathsf{QMA}}$ and $\mathsf{QMA}^{\mathsf{QMA}}$ .
3.

Is $\exists\forall$ - $k$ -PLH complete for $\mathsf{NP}^{\|\mathsf{pureSuperQMA}[2]}$ ? A positive answer would imply that

$\mathsf{NP}^{\|\mathsf{pureSuperQMA}[2]}\subseteq\mathsf{pureQ\Sigma_{2}},$

giving the first connection between oracle-based and quantifier-based definitions of the quantum polynomial hierarchy.
4.

Can one construct disentanglers with guarantees stronger than those in Theorem 18? In particular, is it possible to design a disentangler whose output is always (close to) a pure state?

References

[1] Scott Aaronson and Alex Arkhipov. The Computational Complexity of Linear Optics. In Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 333–342. ACM, 2011. doi:10.1145/1993636.1993682.
[2] Avantika Agarwal, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph. Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306, pages 7:1–7:17, 2024. doi:10.4230/LIPIcs.MFCS.2024.7.
[3] Avantika Agarwal and Srijita Kundu. A Cautionary Note on Quantum Oracles, 2025. doi:10.48550/arXiv.2504.19470.
[4] Dorit Aharonov and Amnon Ta-Shma. Adiabatic Quantum State Generation. SIAM Journal on Computing, 37(1):47–82, 2007. doi:10.1137/060648829.
[5] Kartik Anand, Kabgyun Jeong, and Junseo Lee. Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy, 2025. doi:10.48550/arXiv.2506.19792.
[6] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. doi:10.1017/CBO9780511804090.
[7] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the Complexity and Verification of Quantum Random Circuit Sampling. Nature Physics, 15(2):159–163, 2019. doi:10.1038/s41567-018-0318-2.
[8] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical Simulation of Commuting Quantum Computations Implies Collapse of the Polynomial Hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2126):459–472, 2010. doi:10.1098/rspa.2010.0301.
[9] Anne Broadbent and Alex Bredariol Grilo. Qma-hardness of consistency of local density matrices with applications to quantum zero-knowledge. SIAM Journal on Computing, 51(4):1400–1450, August 2022. doi:10.1137/21m140729x.
[10] Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum Fingerprinting. Physical Review Letters, 87(16):167902, 2001. doi:10.1103/PhysRevLett.87.167902.
[11] C. Carathéodory. Über den variabilitätsbereich der fourier’schen konstanten von positiven harmonischen funktionen. Rendiconti del Circolo Matematico di Palermo (1884-1940), 32(1):193–217, 1911. doi:10.1007/BF03014795.
[12] Andre Chailloux and Or Sattath. The Complexity of the Separable Hamiltonian Problem. In Proceedings of the 2012 IEEE Conference on Computational Complexity, CCC ’12, pages 32–41, 2012. doi:10.1109/CCC.2012.42.
[13] Chirag Falor, Shu Ge, and Anand Natarajan. A Collapsible Polynomial Hierarchy for Promise Problems, 2023. doi:10.48550/arXiv.2311.12228.
[14] Merrick Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1):13–27, 1984. doi:10.1007/BF01744431.
[15] Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum Generalizations of the Polynomial Hierarchy with Applications to $\mathsf{QMA(2)}$ . computational complexity, 31(2):13, 2022. doi:10.1007/s00037-022-00231-8.
[16] Oded Goldreich. On Promise Problems: A Survey, pages 254–290. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006. doi:10.1007/11685654_12.
[17] Sabee Grewal and Dorian Rudolph. On the pure quantum polynomial hierarchy and quantified hamiltonian complexity, 2025. doi:10.48550/arXiv.2510.06522.
[18] Sabee Grewal and Justin Yirka. The Entangled Quantum Polynomial Hierarchy Collapses. In 39th Computational Complexity Conference (CCC 2024), volume 300, pages 6:1–6:23, 2024. doi:10.4230/LIPIcs.CCC.2024.6.
[19] Aram W. Harrow and Ashley Montanaro. Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization. Journal of the ACM, 60(1), 2013. doi:10.1145/2432622.2432625.
[20] Rahul Jain and John Watrous. Parallel Approximation of Non-interactive Zero-sum Quantum Games. In 24th Annual IEEE Conference on Computational Complexity, pages 243–253, 2009. doi:10.1109/CCC.2009.26.
[21] Fernando Granha Jeronimo and Pei Wu. Dimension Independent Disentanglers from Unentanglement and Applications. In 39th Computational Complexity Conference (CCC 2024), volume 300 of CCC ’24, pages 26:1–26:28, 2024. doi:10.4230/LIPIcs.CCC.2024.26.
[22] Joshua Lockhart and Carlos E. González-Guillén. Quantum State Isomorphism, 2017. arXiv:1709.09622.
[23] Jonas Kamminga and Dorian Rudolph. On the Complexity of Pure-State Consistency of Local Density Matrices, 2025. arXiv:2411.03096.
[24] Richard M. Karp and Richard J. Lipton. Some Connections Between Nonuniform and Uniform Complexity Classes. In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC ’80, pages 302–309, 1980. doi:10.1145/800141.804678.
[25] Julia Kempe, Alexei Kitaev, and Oded Regev. The Complexity of the Local Hamiltonian Problem. SIAM Journal on Computing, 35(5):1070–1097, 2006. doi:10.1137/S0097539704445226.
[26] A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation. American Mathematical Society, USA, 2002.
[27] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. Quantum certificate verification: Single versus multiple quantum certificates, 2001. arXiv:quant-ph/0110006.
[28] Clemens Lautemann. $\mathsf{BPP}$ and the Polynomial Time Hierarchy. Information Processing Letters, 17:215–218, 1983.
[29] Yi-Kai Liu. Consistency of Local Density Matrices is $\mathsf{QMA}$ -Complete. In Proceedings of the 9th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, and 10th International Conference on Randomization and Computation, APPROX’06/RANDOM’06, pages 438–449, 2006. doi:10.1007/11830924_40.
[30] Dorian Rudolph, Sevag Gharibian, and Daniel Nagaj. Quantum 2-SAT on Low Dimensional Systems Is $\mathsf{QMA}_{1}$ -Complete: Direct Embeddings and Black-Box Simulation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325, pages 85:1–85:24, 2025. doi:10.4230/LIPIcs.ITCS.2025.85.
[31] Michael Sipser. A Complexity Theoretic Approach to Randomness. In 15th Symposium on Theory of Computing, pages 330–335. ACM Press, 1983. doi:10.1145/800061.808762.
[32] Larry J. Stockmeyer. The Polynomial-Time Hierarchy. Theoretical Computer Science, 3(1):1–22, 1976. doi:10.1016/0304-3975(76)90061-X.
[33] Larry J. Stockmeyer and Albert R. Meyer. Word Problems Requiring Exponential Time (Preliminary Report). In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC ’73, pages 1–9. Association for Computing Machinery, 1973. doi:10.1145/800125.804029.
[34] Seinosuke Toda. $\mathsf{PP}$ Is as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing, 20(5):865–877, 1991. doi:10.1137/0220053.
[35] Andreas Winter. Coding Theorem and Strong Converse for Quantum Channels. IEEE Transactions on Information Theory, 45(7):2481–2485, 1999. doi:10.1109/18.796385.
[36] Tomoyuki Yamakami. Quantum $\mathsf{NP}$ and a Quantum Hierarchy. In 2nd IFIP International Conference on Theoretical Computer Science, pages 323–336. Kluwer Academic Publishers, 2002.

[bib.bib1] [1] Scott Aaronson and Alex Arkhipov. The Computational Complexity of Linear Optics. In Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 333–342. ACM, 2011. doi:10.1145/1993636.1993682.

[bib.bib2] [2] Avantika Agarwal, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph. Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306, pages 7:1–7:17, 2024. doi:10.4230/LIPIcs.MFCS.2024.7.

[bib.bib3] [3] Avantika Agarwal and Srijita Kundu. A Cautionary Note on Quantum Oracles, 2025. doi:10.48550/arXiv.2504.19470.

[bib.bib4] [4] Dorit Aharonov and Amnon Ta-Shma. Adiabatic Quantum State Generation. SIAM Journal on Computing, 37(1):47–82, 2007. doi:10.1137/060648829.

[bib.bib5] [5] Kartik Anand, Kabgyun Jeong, and Junseo Lee. Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy, 2025. doi:10.48550/arXiv.2506.19792.

[bib.bib6] [6] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. doi:10.1017/CBO9780511804090.

[bib.bib7] [7] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the Complexity and Verification of Quantum Random Circuit Sampling. Nature Physics, 15(2):159–163, 2019. doi:10.1038/s41567-018-0318-2.

[bib.bib8] [8] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical Simulation of Commuting Quantum Computations Implies Collapse of the Polynomial Hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2126):459–472, 2010. doi:10.1098/rspa.2010.0301.

[bib.bib9] [9] Anne Broadbent and Alex Bredariol Grilo. Qma-hardness of consistency of local density matrices with applications to quantum zero-knowledge. SIAM Journal on Computing, 51(4):1400–1450, August 2022. doi:10.1137/21m140729x.

[bib.bib10] [10] Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum Fingerprinting. Physical Review Letters, 87(16):167902, 2001. doi:10.1103/PhysRevLett.87.167902.

[bib.bib11] [11] C. Carathéodory. Über den variabilitätsbereich der fourier’schen konstanten von positiven harmonischen funktionen. Rendiconti del Circolo Matematico di Palermo (1884-1940), 32(1):193–217, 1911. doi:10.1007/BF03014795.

[bib.bib12] [12] Andre Chailloux and Or Sattath. The Complexity of the Separable Hamiltonian Problem. In Proceedings of the 2012 IEEE Conference on Computational Complexity, CCC ’12, pages 32–41, 2012. doi:10.1109/CCC.2012.42.

[bib.bib13] [13] Chirag Falor, Shu Ge, and Anand Natarajan. A Collapsible Polynomial Hierarchy for Promise Problems, 2023. doi:10.48550/arXiv.2311.12228.

[bib.bib14] [14] Merrick Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1):13–27, 1984. doi:10.1007/BF01744431.

[bib.bib15] [15] Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum Generalizations of the Polynomial Hierarchy with Applications to $\mathsf{QMA(2)}$ . computational complexity, 31(2):13, 2022. doi:10.1007/s00037-022-00231-8.

[bib.bib16] [16] Oded Goldreich. On Promise Problems: A Survey, pages 254–290. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006. doi:10.1007/11685654_12.

[bib.bib17] [17] Sabee Grewal and Dorian Rudolph. On the pure quantum polynomial hierarchy and quantified hamiltonian complexity, 2025. doi:10.48550/arXiv.2510.06522.

[bib.bib18] [18] Sabee Grewal and Justin Yirka. The Entangled Quantum Polynomial Hierarchy Collapses. In 39th Computational Complexity Conference (CCC 2024), volume 300, pages 6:1–6:23, 2024. doi:10.4230/LIPIcs.CCC.2024.6.

[bib.bib19] [19] Aram W. Harrow and Ashley Montanaro. Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization. Journal of the ACM, 60(1), 2013. doi:10.1145/2432622.2432625.

[bib.bib20] [20] Rahul Jain and John Watrous. Parallel Approximation of Non-interactive Zero-sum Quantum Games. In 24th Annual IEEE Conference on Computational Complexity, pages 243–253, 2009. doi:10.1109/CCC.2009.26.

[bib.bib21] [21] Fernando Granha Jeronimo and Pei Wu. Dimension Independent Disentanglers from Unentanglement and Applications. In 39th Computational Complexity Conference (CCC 2024), volume 300 of CCC ’24, pages 26:1–26:28, 2024. doi:10.4230/LIPIcs.CCC.2024.26.

[bib.bib22] [22] Joshua Lockhart and Carlos E. González-Guillén. Quantum State Isomorphism, 2017. arXiv:1709.09622.

[bib.bib23] [23] Jonas Kamminga and Dorian Rudolph. On the Complexity of Pure-State Consistency of Local Density Matrices, 2025. arXiv:2411.03096.

[bib.bib24] [24] Richard M. Karp and Richard J. Lipton. Some Connections Between Nonuniform and Uniform Complexity Classes. In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC ’80, pages 302–309, 1980. doi:10.1145/800141.804678.

[bib.bib25] [25] Julia Kempe, Alexei Kitaev, and Oded Regev. The Complexity of the Local Hamiltonian Problem. SIAM Journal on Computing, 35(5):1070–1097, 2006. doi:10.1137/S0097539704445226.

[bib.bib26] [26] A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation. American Mathematical Society, USA, 2002.

[bib.bib27] [27] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. Quantum certificate verification: Single versus multiple quantum certificates, 2001. arXiv:quant-ph/0110006.

[bib.bib28] [28] Clemens Lautemann. $\mathsf{BPP}$ and the Polynomial Time Hierarchy. Information Processing Letters, 17:215–218, 1983.

[bib.bib29] [29] Yi-Kai Liu. Consistency of Local Density Matrices is $\mathsf{QMA}$ -Complete. In Proceedings of the 9th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, and 10th International Conference on Randomization and Computation, APPROX’06/RANDOM’06, pages 438–449, 2006. doi:10.1007/11830924_40.

[bib.bib30] [30] Dorian Rudolph, Sevag Gharibian, and Daniel Nagaj. Quantum 2-SAT on Low Dimensional Systems Is $\mathsf{QMA}_{1}$ -Complete: Direct Embeddings and Black-Box Simulation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325, pages 85:1–85:24, 2025. doi:10.4230/LIPIcs.ITCS.2025.85.

[bib.bib31] [31] Michael Sipser. A Complexity Theoretic Approach to Randomness. In 15th Symposium on Theory of Computing, pages 330–335. ACM Press, 1983. doi:10.1145/800061.808762.

[bib.bib32] [32] Larry J. Stockmeyer. The Polynomial-Time Hierarchy. Theoretical Computer Science, 3(1):1–22, 1976. doi:10.1016/0304-3975(76)90061-X.

[bib.bib33] [33] Larry J. Stockmeyer and Albert R. Meyer. Word Problems Requiring Exponential Time (Preliminary Report). In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC ’73, pages 1–9. Association for Computing Machinery, 1973. doi:10.1145/800125.804029.

[bib.bib34] [34] Seinosuke Toda. $\mathsf{PP}$ Is as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing, 20(5):865–877, 1991. doi:10.1137/0220053.

[bib.bib35] [35] Andreas Winter. Coding Theorem and Strong Converse for Quantum Channels. IEEE Transactions on Information Theory, 45(7):2481–2485, 1999. doi:10.1109/18.796385.

[bib.bib36] [36] Tomoyuki Yamakami. Quantum $\mathsf{NP}$ and a Quantum Hierarchy. In 2nd IFIP International Conference on Theoretical Computer Science, pages 323–336. Kluwer Academic Publishers, 2002.

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Results

Theorem 1 (Combination of Theorems 14 and 15).

Theorem 2 (Restatement of Theorem 16).

Corollary 3 (Restatement of Corollary 17).

Lemma 4 (Restatement of Lemma 23).

Proposition 5 (Restatement of Corollary 31).

Theorem 6 (Restatement of Theorem 37).

1.2 Main Ideas

Proving 𝗤𝗠𝗔⁢(𝟮)⊆𝗽𝘂𝗿𝗲𝗤⁢𝝨𝟮⊆𝗤⁢𝝨𝟯.

Amplification and 𝗽𝘂𝗿𝗲𝗤𝗣𝗛=𝗤𝗣𝗛.

Quantified Hamiltonian Complexity.

2 Preliminaries

Fact 7.

Lemma 8 (SWAP test [10]).

Lemma 9 (Gentle measurement [35]).

Definition 10 (𝖰⁢Σ𝗂).

▶ Remark 11.

Definition 12 (𝖰𝖯𝖧 and 𝗉𝗎𝗋𝖾𝖰𝖯𝖧 [15, 2]).

Definition 13 (𝖭𝖯 with promise oracle [2, Footnote 3]).

3 Sandwiching the Second Level of 𝗽𝘂𝗿𝗲𝗤𝗣𝗛

Theorem 14.

Proof.

Theorem 15.

Proof.

4 Amplification of 𝗽𝘂𝗿𝗲𝗤𝗣𝗛 via Disentanglers

Theorem 16.

Corollary 17.

Theorem 18 (Disentangler [21]).

Lemma 19 (Product Test [19, Theorem 3]).

Lemma 20 ([19, Proof of Lemma 5]).

Lemma 21.

Lemma 22.

Lemma 23.

Proof.

Theorem 16. [Restated, see original statement.]

Proof.

5 Quantified Hamiltonian Complexity

5.1 Quantified Hamiltonian Problems

Definition 24 (∃∀-k-LH).

Definition 25 (Row-sparse operators).

Definition 26 (Quantified sparse Hamiltonian problems).

Lemma 27.

Proof.

5.2 Quantified Local Hamiltonian: 𝗡𝗣 with a 𝗤𝗠𝗔 Oracle

Proposition 28.

Proof.

Proposition 29.

Proposition 30.

Proof.

Corollary 31.

Proof.

Proposition 32.

5.3 Quantified Sparse Hamiltonian: Complete Problems for 𝗽𝘂𝗿𝗲𝗤𝗣𝗛

Proposition 33.

Proof.

Lemma 34.

Lemma 35 (Kitaev’s circuit-to-Hamiltonian mapping [26]777This lemma is only implicit [26]. A direct proof can be found in [30, Remark 3.3].).

Lemma 36 (State Projection Lemma [23]).

Theorem 37.

Proof.

6 Open Problems

References

Proving $\mathsf{QMA(2)}\subseteq\mathsf{pureQ\Sigma_{2}}\subseteq\mathsf{Q\Sigma_{3}}$ .

Amplification and $\mathsf{pureQPH}=\mathsf{QPH}$ .

Definition 10 ( $\mathsf{Q\Sigma_{i}}$ ).

$\blacktriangleright$ Remark 11.

Definition 12 ( $\mathsf{QPH}$ and $\mathsf{pureQPH}$ [15, 2]).

Definition 13 ( $\mathsf{NP}$ with promise oracle [2, Footnote 3]).

3 Sandwiching the Second Level of $\mathsf{pureQPH}$

4 Amplification of $\mathsf{pureQPH}$ via Disentanglers

Definition 24 ( $\exists\forall$ - $k$ -LH).

5.2 Quantified Local Hamiltonian: $\mathsf{NP}$ with a $\mathsf{QMA}$ Oracle

5.3 Quantified Sparse Hamiltonian: Complete Problems for $\mathsf{pureQPH}$

Lemma 35 (Kitaev’s circuit-to-Hamiltonian mapping [26]⁷⁷7This lemma is only implicit [26]. A direct proof can be found in [30, Remark 3.3].).