We prove several new results concerning the pure quantum polynomial hierarchy pureQPH. First, we show that QMA(2) ⊆ pureQΣ_2, i.e., two unentangled existential provers can be simulated by competing existential and universal provers. We further prove that pureQΣ_2 ⊆ QΣ_3 ⊆ NEXP. Second, we give an error reduction result for pureQPH, and, as a consequence, prove that pureQPH = 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 pureQΣ_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 ∃∀-mixed local Hamiltonian problem lies in NP^QMA ∩ coNP^QMA.

Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state ρ, while only requiring measurements on logarithmically many copies of ρ in the size of P. In this work, we initiate the study of verification of classical shadows, denoted classical shadow validity (CSV), from the perspective of computational complexity, which asks: Given a classical shadow S, how hard is it to verify that S predicts the measurement statistics of a quantum state? We first show that even for the elegantly simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete. This hardness continues to hold for the high-dimensional extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be "dequantized" for low-Frobenius norm observables, i.e., solved in randomized poly-time with standard sampling assumptions. Finally, we show that CSV for exponentially many observables is complete for a quantum generalization of the second level of the polynomial hierarchy, yielding the first natural complete problem for such a class.

The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash equilibria, subclasses of TFNP remain arguably few and far between. In this work, we define two new subclasses of TFNP borne of the study of complex polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental Theorem of Algebra (SFTA). The first of these is based on Bézout's theorem from algebraic geometry, marking the first TFNP subclass based on an algebraic geometric principle. At the heart of our study is the computational problem known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR), first studied by [Laumann, Läuchli, Moessner, Scardicchio, and Sondhi 2010]. Among other results, we show that QSAT with SDR is MHS-complete, thus giving not only the first link between quantum complexity theory and TFNP, but also the first TFNP problem whose classical variant (SAT with SDR) is easy but whose quantum variant is hard. We also show how to embed the roots of a sparse, high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of MHS. We conjecture this construction also works in the low-error setting, which would imply SFTA is contained in MHS.

In this work we investigate the computational complexity of the pure consistency of local density matrices (PureCLDM) and pure N-representability (Pure-N-Representability; analog of PureCLDM for bosonic or fermionic systems) problems. In these problems the input is a set of reduced density matrices and the task is to determine whether there exists a global pure state consistent with these reduced density matrices. While mixed CLDM, i.e. where the global state can be mixed, was proven to be QMA-complete by Broadbent and Grilo [JoC 2022], almost nothing was known about the complexity of the pure version. Before our work the best upper and lower bounds were QMA(2) and QMA. Our contribution to the understanding of these problems is twofold. Firstly, we define a pure state analogue of the complexity class QMA+ of Aharanov and Regev [FOCS 2003], which we call PureSuperQMA. We prove that both pure-N-Representability and PureCLDM are complete for this new class. Along the way we supplement Broadbent and Grilo by proving hardness for 2-qubit reduced density matrices and showing that mixed N-Representability is QMA-complete. Secondly, we improve the upper bound on PureCLDM. Using methods from algebraic geometry, we prove that PureSuperQMA is in PSPACE. Our methods, and the PSPACE upper bound, are also valid for PureCLDM with exponential or even perfect precision, hence precisePureCLDM is not preciseQMA(2)=NEXP-complete, unless PSPACE=NEXP. We view this as evidence for a negative answer to the longstanding open question whether PureCLDM is QMA(2)-complete. The techniques we develop for our PSPACE upper bound are quite general. We are able to use them for various applications: from proving PSPACE upper bounds on other quantum problems to giving an efficient parallel (NC) algorithm for (non-convex) quadratically constrained quadratic programs with few constraints.

We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in QMA₁ but not in QCMA when the QCMA verifier is only allowed polynomially many adaptive rounds and exponentially many parallel queries per round. Additionally, we derandomize the permutation-oracle separation of Fefferman and Kimmel, obtaining an in-place oracle separation between QMA₁ and QCMA. Furthermore, we focus on QCMA and QMA with an exponentially small gap, where we show a separation assuming the gap is fixed, but not when it may be arbitrarily small. Finally, we derive consequences for approximate ground-state preparation from sparse Hamiltonian oracle access, including a bounded adaptivity frustration-free variant.

$\mathsf{QMA}_1$ is $\mathsf{QMA}$ with perfect completeness, i.e., the prover must accept with a probability of exactly $1$ in the YES-case. Whether $\mathsf{QMA}_1$ and $\mathsf{QMA}$ are equal is still a major open problem. It is not even known whether $\mathsf{QMA}_1$ has a universal gateset; Solovay-Kitaev does not apply due to perfect completeness. Hence, we do not generally know whether $\mathsf{QMA}_1^G=\mathsf{QMA}_1^{G'}$ (superscript denoting gateset), given two universal gatesets $G,G'$. In this paper, we make progress towards the gateset question by proving that for all $k\in\mathbb N$, the gateset $G_{2^k}$ (Amy et al., RC 2024) is universal for all gatesets in the cyclotomic field $\mathbb{Q}(ζ_{2^k}),ζ_{2^k}=e^{2πi/2^k}$, i.e. $\mathsf{QMA}_1^G\subseteq\mathsf{QMA}_1^{G_{2^k}}$ for all gatesets $G$ in $\mathbb{Q}(ζ_{2^k})$. For $\mathsf{BQP}_1$, we can even show that $G_2$ suffices for all $2^k$-th cyclotomic fields. We exhibit complete problems for all $\mathsf{QMA}_1^{G_{2^k}}$: Quantum $l$-SAT in $\mathbb{Q}(ζ_{2^k})$ is complete for $\mathsf{QMA}_1^{G_{2^k}}$ for all $l\ge4$, and $l=3$ if $k\ge3$, where quantum $l$-SAT is the problem of deciding whether a set of $l$-local Hamiltonians has a common ground state. Additionally, we give the first $\mathsf{QMA}_1$-complete $2$-local Hamiltonian problem: It is $\mathsf{QMA}_1^{G_{2^k}}$-complete (for $k\ge3$) to decide whether a given $2$-local Hamiltonian $H$ in $\mathbb{Q}(ζ_{2^k})$ has a nonempty nullspace. Our techniques also extend to sparse Hamiltonians, and so we can prove the first $\mathsf{QMA}_1(2)$-complete (i.e. $\mathsf{QMA}_1$ with two unentangled provers) Hamiltonian problem. Finally, we prove that the Gapped Clique Homology problem defined by King and Kohler (FOCS 2024) is $\mathsf{QMA}_1^{G_2}$-complete, and the Clique Homology problem without promise gap is PSPACE-complete.

Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSAT with each constraint acting on a d_A-dimensional and d_B-dimensional qudit pair, denoted (d_A×d_B)-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain QMA_1-hard, in that (2×5)-QSAT is QMA_1-complete. (QMA_1 is a quantum analogue of MA with perfect completeness.) In contrast, (2×2)-QSAT (i.e. Quantum 2-SAT on qubits) is well-known to be poly-time solvable [Bravyi, 2006]. Our second main result proves that (3×d)-QSAT on the 1D line with d ∈ O(1) is also QMA_1-hard. Finally, we initiate the study of (2×d)-QSAT on the 1D line by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state. As implied by our title, our first result uses a direct embedding: We combine a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset and Nagaj, 2013]. Of note is a new simplified and analytic proof for the latter (as opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection Lemma", allowing us to break low energy analyses into small patches of projectors, and to improve the soundness analysis of [GN13] from Ω(1/T⁶) to Ω(1/T²), for T the number of gates. Our second result goes via black-box reduction: Given an arbitrary 1D Hamiltonian H on d'-dimensional qudits, we show how to embed it into an effective 1D (3×d)-QSAT instance, for d ∈ O(1). Our approach may be viewed as a weaker notion of "analog simulation" (à la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based QMA_1-hardness result.

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

A celebrated result in classical complexity theory is Savitch’s theorem, which states that non-deterministic polynomial-space computations (NPSPACE) can be simulated by deterministic poly-space computations (PSPACE). In this work, we initiate the study of a quantum analogue of NPSPACE, denoted Streaming-QCMASPACE (SQCMASPACE), in which an exponentially long classical proof is streamed to a poly-space quantum verifier. We first show that a quantum analogue of Savitch’s theorem is unlikely to hold, in that SQCMASPACE = NEXP. For completeness, we also introduce the companion class Streaming-QMASPACE (SQMASPACE) with an exponentially long streamed quantum proof, and show SQMASPACE = QMAEXP (the quantum analogue of NEXP). Our primary focus, however, is on the study of exponentially long streaming classical proofs, where we next show the following two main results. The first result shows that, in strong contrast to the classical setting, the solution space of a quantum constraint satisfaction problem (i.e. a local Hamiltonian) is always connected when exponentially long proofs are permitted. For this, we show how to simulate any Lipschitz continuous path on the unit hypersphere via a sequence of local unitary gates, at the expense of blowing up the circuit size. This shows that quantum error-correcting codes can be unable to detect one codeword erroneously evolving to another if the evolution happens sufficiently slowly, and answers an open question of [Gharibian, Sikora, ICALP 2015] regarding the Ground State Connectivity problem. Our second main result is that any SQCMASPACE computation can be embedded into "unentanglement", i.e. into a quantum constraint satisfaction problem with unentangled provers. Formally, we show how to embed SQCMASPACE into the Sparse Separable Hamiltonian problem of [Chailloux, Sattath, CCC 2012] (QMA(2)-complete for 1/poly promise gap), at the expense of scaling the promise gap with the streamed proof size. As a corollary, we obtain the first systematic construction for obtaining QMA(2)-type upper bounds on arbitrary multi-prover interactive proof systems, where the QMA(2) promise gap scales exponentially with the number of bits of communication in the interactive proof. Our construction uses a new technique for exploiting unentanglement to simulate quadratic Boolean functions, which in some sense allows history states to encode the future.

We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$ and $P^{QMA}$, respectively. The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate Simulation (APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by the classes $P^{NP[\log]}$ and $P^{QMA[\log]}$, defined identically to $P^{NP}$ and $P^{QMA}$, except that only logarithmically many oracle queries are allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by a $P^{NP}$ machine have a "query graph" which is a tree, then this computation can be simulated in $P^{NP[\log]}$. In this work, we first show that for any verification class $C\in\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\exp}\}$, any $P^C$ machine with a query graph of "separator number" $s$ can be simulated using deterministic time $\exp(s\log n)$ and $s\log n$ queries to a $C$-oracle. When $s\in O(1)$ (which includes the case of $O(1)$-treewidth, and thus also of trees), this gives an upper bound of $P^{C[\log]}$, and when $s\in O(\log^k(n))$, this yields bound $QP^{C[\log^{k+1}]}$ (QP meaning quasi-polynomial time). We next show how to combine Gottlob's "admissible-weighting function" framework with the "flag-qubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a unified approach for embedding $P^C$ computations directly into APX-SIM instances in a black-box fashion. Finally, we formalize a simple no-go statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear polynomial $p$ specified via an arithmetic circuit, if one can "weakly compress" $p$ so that its optimal value requires $m$ bits to represent, then $P^{NP}$ can be decided with only $m$ queries to an NP-oracle.

Motivated by the problem of shape recognition by nanoscale computing agents, we investigate the problem of detecting the geometric shape of a structure composed of hexagonal tiles by a finite-state automaton robot. In particular, in this paper we consider the question of recognizing whether the tiles are assembled into a parallelogram whose longer side has length l = f(h), for a given function f(*), where h is the length of the shorter side. To determine the computational power of the finite-state automaton robot, we identify functions that can or cannot be decided when the robot is given a certain number of pebbles. We show that the robot can decide whether l = ah+b for constant integers a and b without any pebbles, but cannot detect whether l = f(h) for any function f(x) = omega(x). For a robot with a single pebble, we present an algorithm to decide whether l = p(h) for a given polynomial p(*) of constant degree. We contrast this result by showing that, for any constant k, any function f(x) = omega(x^(6k + 2)) cannot be decided by a robot with k states and a single pebble. We further present exponential functions that can be decided using two pebbles. Finally, we present a family of functions f_n(*) such that the robot needs more than n pebbles to decide whether l = f_n(h).