The Pure-State Consistency of Local Density Matrices Problem: In PSPACE and Complete for a Class Between QMA and QMA(2)

Kamminga, Jonas; Rudolph, Dorian

doi:10.4230/LIPIcs.ITCS.2026.83

The Pure-State Consistency of Local Density Matrices Problem: In PSPACE and Complete for a Class Between QMA and QMA(2)

Jonas Kamminga

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

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

Abstract

In this work we investigate the computational complexity of the pure consistency of local density matrices ( $\mathsf{PureCLDM}$ ) and pure $N$ -representability ( $\mathsf{Pure}$ - $N$ - $\mathsf{Representability}$ ; analog of $\mathsf{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 $\mathsf{CLDM}$ , i.e. where the global state can be mixed, was proven to be $\mathsf{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 $\mathsf{QMA}(2)$ and $\mathsf{QMA}$ . Our contribution to the understanding of these problems is twofold.

Firstly, we define a pure state analogue of the complexity class $\mathsf{QMA}^{+}$ of Aharanov and Regev [FOCS 2003], which we call $\mathsf{PureSuperQMA}$ . We prove that both $\mathsf{pure}$ - $N$ - $\mathsf{Representability}$ and $\mathsf{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$ - $\mathsf{Representability}$ is $\mathsf{QMA}$ -complete.

Secondly, we improve the upper bound on $\mathsf{PureCLDM}$ . Using methods from algebraic geometry, we prove that $\mathsf{PureSuperQMA}\subseteq\mathsf{PSPACE}$ . Our methods, and the $\mathsf{PSPACE}$ upper bound, are also valid for $\mathsf{PureCLDM}$ with exponential or even perfect precision, hence $\mathsf{precisePureCLDM}$ is not $\mathsf{preciseQMA}(2)=\mathsf{NEXP}$ -complete, unless $\mathsf{PSPACE}=\mathsf{NEXP}$ . We view this as evidence for a negative answer to the longstanding open question whether $\mathsf{PureCLDM}$ is $\mathsf{QMA}(2)$ -complete.

The techniques we develop for our $\mathsf{PSPACE}$ upper bound are quite general. We are able to use them for various applications: from proving $\mathsf{PSPACE}$ upper bounds on other quantum problems to giving an efficient parallel ( $\mathsf{NC}$ ) algorithm for (non-convex) quadratically constrained quadratic programs with few constraints.

Keywords and phrases:

Quantum Complexity Theory, PSPACE, QMA(2), Consistency of Local Density Matrices, Polynomial Optimization

Funding:

Jonas Kamminga: supported by the DFG under grant number 450041824.

Dorian Rudolph: supported by the DFG under grant number 432788384 and 563388236.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum complexity theory

Related Version:

Full Version: https://arxiv.org/abs/2411.03096 [18]

Acknowledgements:

The authors would like to thank Dima Grigoryev for suggesting that the GP algorithm could be parallelized, pointing to helpful references, and giving us advice on how this could be proven.

DOI:

10.4230/LIPIcs.ITCS.2026.83

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

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

1 Introduction

“Are these local density matrices consistent with some global state?” This quantum variant of the $\mathsf{NP}$ -complete marginal problem is known as the consistency of local density matrices problem ( $\mathsf{CLDM}$ ) or quantum marginal problem and as the $N$ -representability problem ( $N\mathchar 45\relax\mathsf{Representability}$ ) when dealing with indistinguishable particles. It is of fundamental interest to quantum physics. In fact, it was already recognized as an important question in the sixties [10]. At that time, the hope was that the ground state energy of quantum systems could be found using reduced density matrices. This hope was supported by the fact that Hamiltonians showing up in nature are all local. One requirement would be that it is possible to check that alleged reduced density matrices are indeed consistent with a valid global quantum state, hence the interest in the $\mathsf{CLDM}$ problem.

Over the years it became apparent that this hope would not materialize, especially when Kitaev proved that computing ground state energies of local Hamiltonians is $\mathsf{QMA}$ -hard [20]. Also the $\mathsf{CLDM}$ problem itself was proven to be hard. First by Liu, who proved that the (mixed state) $\mathsf{CLDM}$ problem is contained in $\mathsf{QMA}$ and $\mathsf{QMA}$ -complete under Turing reductions [22] and later, together with Christandl and Verstraete, proved that the $N$ -representability problem is also $\mathsf{QMA}$ -complete under Turing reductions [23]. This was improved by Broadbent and Grilo who showed that the mixed $\mathsf{CLDM}$ is also $\mathsf{QMA}$ -hard under Karp reductions, establishing it as $\mathsf{QMA}$ -complete [9].

In this work we focus our attention on a variant of $\mathsf{CLDM}$ that is of interest to physics and complexity theory. This variant, the pure consistency of local density matrices problem, or $\mathsf{PureCLDM}$ asks not whether there exists any state consistent with the reduced density matrices, but demands that this consistent state is pure. Physically, this restriction to pure states is well motivated as isolated systems will always be in a pure state. If one has some reduced density matrices of some molecule it might be more interesting to know whether these are consistent with some global state of the molecule in isolation, i.e. a pure state, rather than some larger state where the molecule is entangled with its environment.

From a complexity point of view $\mathsf{PureCLDM}$ is interesting because of its connections with the class $\mathsf{QMA}(2)$ . While the complexity of mixed $\mathsf{CLDM}$ is well understood to be $\mathsf{QMA}$ , the best known upper bound to $\mathsf{PureCLDM}$ is the class $\mathsf{QMA}(2)$ and it has been a longstanding open question whether $\mathsf{PureCLDM}$ is complete for $\mathsf{QMA}(2)$ [23]. If it would be complete that would be interesting for several reasons. Firstly, it would be a highly physically motivated complete problem for $\mathsf{QMA}(2)$ , a class that has attracted a lot of attention but generally lacks physical complete problems. Secondly, there has been a large interest in the relation between purity testing and $\mathsf{QMA}(2)$ . In many ways, the power of $\mathsf{QMA}(2)$ seems to come from the ability to do SWAP tests [16]. On the other hand, a correspondence between protocols over separable states and protocols with a purity constraint has been used in several works (e.g. [16, 32]). Recently, it has been suggested that purity testing could already be enough to give $\mathsf{QMA}(2)$ its power [4]. Establishing $\mathsf{PureCLDM}$ as a complete problem for $\mathsf{QMA}(2)$ would suggest that indeed SWAP tests are not necessary to capture the power of $\mathsf{QMA}(2)$ and indeed a purity constraint is already enough.

1.1 Our results

In this work we investigate the complexity of $\mathsf{PureCLDM}$ and $\mathsf{Pure}\mathchar 45\relax N\mathchar 45\relax\mathsf{Representability}$ and give evidence towards a negative answer to the longstanding open question whether they are $\mathsf{QMA}(2)$ -complete.

Definition 1.1 ( $k\mathchar 45\relax\mathsf{PureCLDM}$ , informal).

We are given pairs $(\rho_{1},C_{1}),\dots,(\rho_{m},C_{m})$ , where the $\rho_{i}$ are reduced density matrices and $C_{i}\subseteq[n]$ with $\lvert C_{i}\rvert\leq k$ for all $i$ . Additionally, we are given parameters $\alpha$ and $\beta$ with $\beta-\alpha\geq 1/\mathrm{poly}(n)$ . Decide whether:

$\blacksquare$

YES: there exists a consistent pure state, that is, a state $\lvert\psi\rangle$ such that $\lVert\operatorname{Tr}_{\overline{C_{i}}}(\lvert\psi\rangle\langle\psi\rvert)% -\rho_{i}\rVert\leq\alpha$ for all $i\in[m]$ .
$\blacksquare$

NO: all pure states are “far from” consistent, that is, for all $\lvert\psi\rangle$ , there is an $i\in[m]$ with $\lVert\operatorname{Tr}_{\overline{C_{i}}}(\lvert\psi\rangle\langle\psi\rvert)% -\rho_{i}\rVert\geq\beta$ .

1.1.1 $\mathsf{PureCLDM}$ is complete for $\mathsf{PureSuperQMA}$

Our first main result on the complexity of $\mathsf{PureCLDM}$ is that it is complete for the class of (promise) problems decided by a “super-verifier” (c.f. [2]) that is given a pure state proof. Following [2] we call this class $\mathsf{PureSuperQMA}$ .¹¹1[2] use the name $\mathsf{QMA}{+}$ , but recently $\mathsf{QMA}^{+}$ has been used to refer to $\mathsf{QMA}$ with proofs with nonnegative amplitudes [17, 5]. As $\mathsf{QMA}{+}$ is sometimes referred to as $\mathsf{QMA}$ with a super-verifier, we use $\mathsf{SuperQMA}$ .

Definition 1.2 ( $\mathsf{PureSuperQMA}$ , informal).

A promise problem $A=(A_{\textup{yes}},A_{\textup{no}},A_{\textup{inv}})$ is in $\mathsf{PureSuperQMA}(m,\varepsilon,\delta)$ if there exist $m$ constraints $\mathcal{V}=\{(V_{x,i},r_{x,i},s_{x,i})\}_{i\in[m]}$ such that:

$\blacksquare$

$\forall x\in A_{\textup{yes}}\;\exists\lvert\psi\rangle\colon\Pr_{i}(\lvert p(% V_{x,i},\psi)-r_{x,i}\rvert\leq s_{x,i})=1$ , that is, the $V_{x,i}$ accept $\lvert\psi\rangle$ with acceptance probability at most $s_{x,i}$ away from $r_{x,i}$ .
$\blacksquare$

$\forall x\in A_{\textup{no}}\;\forall\lvert\psi\rangle\colon\Pr_{i}(\lvert p(V% _{x,i},\psi)-r_{x,i}\rvert\leq s_{x,i}+\varepsilon)\leq 1-\delta$ , that is, at least a $\delta$ fraction of the $V_{x,i}$ accept $\lvert\psi\rangle$ with probability more than $s_{x,i}+\varepsilon$ away from $r_{x,i}$ .

Here $p(V,\psi)$ denotes the acceptance probability of the circuit $V$ when ran on input $\lvert\psi\rangle$ .

In the following we refer to $m$ as the number of checks or constraints and to $\varepsilon$ and $\delta$ as precision parameters. We denote the union of $\mathsf{PureSuperQMA}(m,\varepsilon,\delta)$ where $m$ is polynomial and $\varepsilon$ and $\delta$ are inverse polynomial as $\mathsf{PureSuperQMA}(\mathrm{poly},\frac{1}{\mathrm{poly}},\frac{1}{\mathrm{% poly}})\eqcolon\mathsf{PureSuperQMA}$ .

We show that the definition of $\mathsf{PureSuperQMA}$ can be significantly simplified: we can set all $r_{x,i}=1/2$ and all $s_{x,i}=0$ without changing the complexity. Our proof of $\mathsf{PureSuperQMA}$ -completeness holds already for $k\mathchar 45\relax\mathsf{PureCLDM}_{1}$ , which is $k\mathchar 45\relax\mathsf{PureCLDM}$ with “exact consistency” as well as for Bosonic/Fermionic $\mathsf{Pure}\mathchar 45\relax N\mathchar 45\relax\mathsf{Representability}$ .

Theorem 1.3.

$k\mathchar 45\relax\mathsf{PureCLDM}_{1}$ is $\mathsf{PureSuperQMA}$ -complete for all $k\geq 2$ .

Corollary 1.4.

Fermionic/bosonic $\mathsf{Pure}\mathchar 45\relax N\mathchar 45\relax\mathsf{Representability}_{1}$ is $\mathsf{PureSuperQMA}$ -complete.²²2Technical details of $\mathsf{Pure}\mathchar 45\relax N\mathchar 45\relax\mathsf{Representability}$ are in the full version [18].

Note that $\mathsf{PureSuperQMA}$ as the complete complexity class is quite natural, since Liu’s proof for $\mathsf{CLDM}\in\mathsf{QMA}$ also goes via $\mathsf{SuperQMA}=\mathsf{QMA}$ . Since a pure state analogue to this latter statement is not known, we have to remain the super-verifier regime. Along the way to Theorem 1.3, we show that the $k\mathchar 45\relax\mathsf{CLDM}$ problem is already $\mathsf{QMA}$ -hard for $k\geq 2$ . This improves upon the results by Broadbent and Grilo [9] who show hardness for $k\geq 5$ . We also resolve one of their open questions by showing that the (mixed) fermionic and bosonic $N$ -representability problems are $\mathsf{QMA}$ -hard, already for $2$ -particle reduced density matrices.

1.1.2 $\mathsf{PureSuperQMA}$ as a “light” version of $\mathsf{QMA}(2)$

Next, we prove results suggesting $\mathsf{PureSuperQMA}$ can be viewed as a “light” version of $\mathsf{QMA}(2)$ . It lies between $\mathsf{QMA}$ and $\mathsf{QMA}(2)$ but contains $\mathsf{NP}$ already with $\log$ -size proofs and becomes $\mathsf{NEXP}$ when the number of checks and the precision are exponential. This mirrors $\mathsf{QMA}(2)$ that also contains $\mathsf{NP}$ with $\log$ -size proofs [6] and becomes equal to $\mathsf{NEXP}$ when made exponentially precise [26]. On the other hand, $\mathsf{QMA}$ with $\log$ -size proofs is equal to $\mathsf{BQP}$ [24], which is believed not to contain $\mathsf{NP}$ , and $\mathsf{PreciseQMA}=\mathsf{PSPACE}$ [11] is believed to be different from $\mathsf{NEXP}$ . Figure 1 depicts the relationships between the classes discussed here.

Proposition 1.5.

$\mathsf{QMA}\subseteq\mathsf{PureSuperQMA}\subseteq\mathsf{PureSuperQMA}(\exp,% \frac{1}{\mathrm{poly}},\frac{1}{\mathrm{poly}})\subseteq\mathsf{QMA}(2)$ .

Proposition 1.6.

$\mathsf{NP}$ can be decided in $\mathsf{PureSuperQMA}$ already with $\log$ -size proofs.

Proposition 1.7.

$\mathsf{PureSuperQMA}(\exp,\frac{1}{\exp},\frac{1}{\exp})=\mathsf{NEXP}$

1.1.3 $\mathsf{PureSuperQMA}$ is upper bounded by $\mathsf{PSPACE}$

Proving a non-trivial upper bound on the complexity of $\mathsf{QMA}(2)$ is a major open question in the field. As such, one might wonder whether our “light” version of $\mathsf{QMA}(2)$ does admit a non-trivial upper bound. Our second main result is that it does indeed, namely $\mathsf{PSPACE}$ . This sharpens the upper bound on the complexity of $\mathsf{PureCLDM}$ from $\mathsf{QMA}(2)\subseteq\mathsf{NEXP}$ to $\mathsf{PSPACE}$ .

Theorem 1.8.

$\mathsf{PureSuperQMA}\subseteq\mathsf{PureSuperQMA}(\mathrm{poly},0,\frac{1}{% \mathrm{poly}})\subseteq\mathsf{PSPACE}$ .

Our proof relies on methods from algebraic geometry and also works for $\mathsf{PureSuperQMA}$ with exponential or even perfect precision as long as the number of constraints is polynomial.

What does this mean for $\mathsf{QMA}(2)$ ? Of course showing that $\mathsf{PureCLDM}$ is $\mathsf{QMA}(2)$ -hard would imply $\mathsf{QMA}(2)\subseteq\mathsf{PSPACE}$ but there is a catch. To prove Theorem 1.8 we use methods from algebraic geometry that also work for $\mathsf{PureSuperQMA}$ with exponential precision and even with perfect precision. This allows us to obtain the following corollary.

Corollary 1.9.

If $\mathsf{Precise\mathchar 45\relax PureCLDM}$ is $\mathsf{PreciseQMA(2)}$ -hard, then $\mathsf{PSPACE}=\mathsf{NEXP}$ .

This corollary can be interpreted either as evidence that $\mathsf{PureCLDM}$ is not $\mathsf{QMA}(2)$ -hard, or as a barrier to a hardness proof: any such proof must fail in the precise case, assuming that $\mathsf{PSPACE}\neq\mathsf{NEXP}$ .

Furthermore, by combining Propositions 1.5 and 1.3 we conclude that $\mathsf{PureCLDM}$ can only be $\mathsf{QMA}(2)$ -complete if a polynomial number of constraints give the same power as exponentially many constraints.

Corollary 1.10.

If $\mathsf{PureSuperQMA}(\mathrm{poly},\frac{1}{\mathrm{poly}},\frac{1}{\mathrm{% poly}})\subsetneq\mathsf{PureSuperQMA}(\exp,\frac{1}{\mathrm{poly}},\frac{1}{% \mathrm{poly}})$ , then $\mathsf{PureCLDM}$ is not $\mathsf{QMA}(2)$ -hard.

Lastly, the fact that $\mathsf{QMA}(2)$ contains $\mathsf{NP}$ already with $\log$ -size proofs is sometimes taken as evidence that $\mathsf{QMA}(2)$ could be equal to $\mathsf{NEXP}$ . We argue that our results imply that this is not evidence at all. Indeed, $\mathsf{PureSuperQMA}$ also contains $\mathsf{NP}$ with $\log$ -size proofs but is contained in $\mathsf{PSPACE}$ .

Figure 1: Diagram of the complexity classes discussed in this paper. Theorem 1.8 shows

\mathsf{PureSuperQMA}\subseteq\mathsf{PSPACE}

.

\mathsf{BellPureSymQMA}

is discussed in the full version [18]. Proposition 1.5 shows

\mathsf{PureSuperQMA}(\exp,\frac{1}{\mathrm{poly}},\frac{1}{\mathrm{poly}})% \subseteq\mathsf{QMA}(2)

.

\mathsf{PSPACE}=\mathsf{PreciseQMA}

is shown in [11]. The third level of the quantum polynomial hierarchy,

\mathsf{Q\Sigma}_{3}

, is between

\mathsf{QMA}(2)

and

\mathsf{NEXP}

[12].

\mathsf{NEXP}=\mathsf{PreciseQMA(2)}

is shown in [6, 26]. The relationship between

\mathsf{PSPACE}

and

\mathsf{QMA}(2)

remains a major open problem.

1.1.4 Solving systems of quadratic equations efficiently in parallel

To prove Theorem 1.8 we rely on techniques by Grigoriev and Pasechnik [14] for solving certain polynomials. We call such polynomials GP systems.

Definition 1.11 (GP system (informal)).

A GP system is a polynomial of the form $p(Q(X))$ , where $p\colon\mathbb{R}^{k}\to\mathbb{R}$ is a degree $d$ polynomial in “few” variables, and $Q\colon\mathbb{R}^{N}\to\mathbb{R}^{k}$ is quadratic in “many” variables. We assume the coefficients of $p$ and $Q$ are integers of bit size at most $L$ . A solution to the system is a point $X^{*}\in\mathbb{R}^{N}$ such that $p(Q(X^{*}))=0$ .

Grigoriev and Pasechnik give an algorithm that can compute a set of univariate representation of solutions of $p(Q(X))$ that intersects all connected components of the solution set [14, Theorem 1.2]. Their algorithm requires $(dN)^{O(k)}$ arithmetic operations.

We show how to write a $\mathsf{PureSuperQMA}$ verifier as a GP system with $k=\mathrm{poly}(n)$ and $N,L=2^{\mathrm{poly}(n)}$ such that the system has a solution iff the verifier accepts some pure proof. The results by Grigoriev and Pasechnik then immediately imply $\mathsf{PureSuperQMA}\subseteq\mathsf{EXP}$ . To prove containment in $\mathsf{PSPACE}$ we modify the algorithm to work efficiently in parallel. The techniques we develop turn out to be much more general. They also show that solving quadratic systems with few constraints is in $\mathsf{NC}$ , or Nick’s Class, which captures efficient parallel computation.

Definition 1.12 (Nick’s Class [3]).

The $i$ -th level of $\mathsf{NC}$ , $\mathsf{NC}^{i}$ , consists of all languages decidable in time $O(\log^{i}(n))$ using $\mathrm{poly}(n)$ parallel processors. $\mathsf{NC}$ is the union of $\mathsf{NC}^{i}$ over all $i\in\mathbb{N}$ .³³3Equivalently, $\mathsf{NC}^{i}$ can be defined as the class of languages decidable by an $O(\log^{i}n)$ -depth circuit of size $\mathrm{poly}(n)$ .

The class $\mathsf{NC}(\mathrm{poly})$ of all decision problems decidable in $\mathrm{poly}(n)$ time on $\exp(n)$ processors is equal to $\mathsf{PSPACE}$ [7]. Our modification of Grigoriev and Pasechnik’s algorithm yields:

Theorem 1.13.

Let $p, Q$ be a GP system. There is a parallel algorithm for deciding whether $p(Q(X))$ has a root. The algorithm uses $L^{2}(k^{2}Nd)^{O(k)}$ parallel processors and needs $\mathrm{poly}(\log N,\log d,k,\log L)$ time. In particular, if $\log N,\log d,\log L,k\leq\mathrm{poly}(n)$ the computation can be done in $\mathsf{NC}(\mathrm{poly})=\mathsf{PSPACE}$ . If $N,d,L\leq\mathrm{poly}(n)$ and $k=O(1)$ then the algorithm is in $\mathsf{NC}$ .

We further build upon [14] and consider the following optimization problem which includes the task of quantifying how inconsistent local density matrices are.

Definition 1.14 (OptGP).

An OptGP instance consists of a degree $\leq d$ polynomial $r\colon\mathbb{R}^{k}\to\mathbb{R}$ and a GP system $p(Q(X))$ with bounded solution set $Z=\{X\in\mathbb{R}^{N}\colon p(Q(X))=0\}$ . The task is to compute or approximate $\theta=\min_{X\in Z}r(Q(X))$ .

We give a parallel algorithm for approximating the optimum of a OptGP system as well as approximating a witness to this optimum.

Theorem 1.15.

Let $r, p, Q$ be an OptGP instance. There is a parallel algorithm that computes a $\delta$ -approximation to $\theta=\min_{X\in Z}r(Q(X))$ and to some $X^{*}$ with $r(Q(X^{*}))=\theta$ and $p(Q(X^{*}))=0$ . The algorithm uses $\mathrm{poly}\bigl(L,|\log\delta|,(kNd)^{O(k^{2})}\bigr)$ parallel processors and needs $\mathrm{poly}(\log N,\log d,k,\log L,\log|\log\delta|)$ time.

Grigoriev and Pasechnik [14, Theorem 1.5] also state a theorem with a sequential algorithm for the optimization problem that also applies to unbounded $Z$ , but their proof is not yet available to the best of our knowledge.

Finally, we showcase the applicability of the developed algorithms. The formal treatment of these applications are deferred to the full version [18] but we already state the results.

First, we improve upon a result by Shi and Wu. In [30] they give a $\mathsf{PSPACE}$ algorithm for optimizing the energy of “decomposable” Hamiltonians over separable states. Using our framework we are able to reprove this fact, and even get a better runtime dependence on the error.

Second, we show that deciding if there exists a unique⁴⁴4We say a state $\lvert\phi\rangle$ is the unique state consistent with some local density matrices if any state that is orthogonal to $\lvert\phi\rangle$ is far from consistent. pure state that is consistent with given local density matrices is also in $\mathsf{PSPACE}$ . In other words, we can decide in $\mathsf{PSPACE}$ whether the local density matrices fully describe the physics of the system.

Third, we show how to decide a variant of $\mathsf{PureCLDM}$ , where the input only specifies the spectrum of the local density matrices. This version is sometimes referred to as the quantum marginal problem, although others use that name for our $\mathsf{PureCLDM}$ .

Fourth, we consider a pure-state variant of $\mathsf{BellSymQMA}(\mathrm{poly})$ . This class (see [1, 8]) captures $\mathsf{QMA}$ protocols where Merlin promises to send $\mathrm{poly}$ many copies of a proof in tensor product, but Arthur has measure each copy independently and then decide to accept or reject based on the classical measurement outcomes. It turns out that $\mathsf{BellSymQMA}(\mathrm{poly})$ is actually equal to $\mathsf{QMA}$ [8]. The variant we consider, $\mathsf{BellPureSymQMA}(\mathrm{poly})$ adds the additional promise that the proof is pure and does not obviously equal $\mathsf{QMA}$ . It is easily seen that $\mathsf{PureSuperQMA}\subseteq\mathsf{BellPureSymQMA}(\mathrm{poly})$ as Arthur can approximate the acceptance probability of the checks by doing many independent measurements. We slightly strengthen Theorem 1.8 by proving that also $\mathsf{BellPureSymQMA}(\mathrm{poly})\subseteq\mathsf{PSPACE}$ .

Lastly, we consider an entirely classical problem: quadratic programming with few constraints. A quadratically constrained quadratic program (QCQP) is an optimization problem of the form


$\displaystyle\min_{x\in\mathbb{R}^{n}}$	$\displaystyle x^{\mathsf{T}}A_{0}x+a_{0}^{\mathsf{T}}x$	(1a)
subject to	$\displaystyle x^{\mathsf{T}}A_{i}x+a_{i}^{\mathsf{T}}x\leq b_{i}\quad\forall i% \in[m].$	(1b)

As a final application of the GP framework, we show that QCQPs can be solved in $\mathsf{NC}$ if the number of constraints $m$ is constant. Note that we do not require any assumptions on the $A_{i}$ such as positivity, symmetry or bounds on the condition number.

1.2 Proof techniques

Sketches of our proof can be found in Sections 4, 5, and 6. The formal proofs can be found in the full version [18].

1.3 Related work

The computational complexity of (mixed) $\mathsf{CLDM}$ and $N\mathchar 45\relax\mathsf{Representability}$ has previously been studied by Liu, Broadbent and Grilo, as mentioned before. Liu [22] proves that (mixed) $\mathsf{CLDM}$ is contained in $\mathsf{QMA}$ and hard under Turing reductions. Similar results for $N\mathchar 45\relax\mathsf{Representability}$ are proven in [23]. This was improved by Broadbent and Grilo who proved (among other results regarding zero-knowledge proof systems) that (mixed) $\mathsf{CLDM}$ is also $\mathsf{QMA}$ -hard under Karp reductions, thereby fully resolving its complexity [9]. Both Liu, and Broadbent and Grilo do not intensively study $\mathsf{PureCLDM}$ , although [23] does show containment of fermionic $\mathsf{Pure}\mathchar 45\relax N\mathchar 45\relax\mathsf{Representability}$ in $\mathsf{QMA}(2)$ , leaving hardness as an open question. A similar containment for bosonic $\mathsf{Pure}\mathchar 45\relax N\mathchar 45\relax\mathsf{Representability}$ was shown in [31].

That does not mean that $\mathsf{PureCLDM}$ and $\mathsf{Pure}\mathchar 45\relax N\mathchar 45\relax\mathsf{Representability}$ have not been studied before. There is a large body of work focussing on finding necessary and/or sufficient conditions for reduced density matrices to be consistent with a global state. Among these works is [21], which focuses on the case where the reduced density matrices are non-overlapping. The paper establishes conditions that are necessary and sufficient for the existence of a consistent pure state in this case. Mazziotti [25] derives necessary conditions for a two-fermion density matrix to have a consist global $N$ -fermion pure state.

[32] rewrite $\mathsf{PureCLDM}$ as an optimization problem over separable state. They then apply the method of symmetric extensions to this notoriously hard problem to describe $\mathsf{PureCLDM}$ as a hierarchy of SDP’s. That is, they describe SDP’s depending on a parameter $N$ such that any “No” instance will be discovered by the SDP for sufficiently large $N$ . They do not, however, prove any upper bounds on the size of $N$ required.

In [4], the authors consider $\mathsf{QMA}$ with an internally separable proof. They prove that when this proof is mixed, the class is contained in $\mathsf{EXP}$ , whereas it is equal to $\mathsf{NEXP}$ if the proof is pure. This provides the, to our knowledge first, instance where pure proofs are provably stronger than mixed proofs, modulo standard complexity theoretic assumptions.

An algorithm for solving polynomial systems more general than those considered in Theorem 1.13 is given in [13]. It shows that a system of $k$ polynomials of degree $d$ in $n$ variables can be solved in time $\mathrm{poly}\bigl(n^{d^{3k}}\bigr)$ . One downside to this algorithm is that it finds a solution over the complex numbers instead of the reals. This makes it hard to constrain the norm of variables, as the complex conjugate is not a polynomial.

1.4 Discussion and open questions

Our work sheds some more light on the complexity of $\mathsf{Pure}\mathchar 45\relax N\mathchar 45\relax\mathsf{Representability}$ and $\mathsf{PureCLDM}$ . However, the story is far from complete as the relation between $\mathsf{PureSuperQMA}$ and $\mathsf{QMA}$ or $\mathsf{PSPACE}$ remains poorly understood. We conjecture

Conjecture 1.16.

$\mathsf{QMA}\subsetneq\mathsf{PureSuperQMA}\subsetneq\mathsf{QMA}(2)$ .

We give some evidence that $\mathsf{PureSuperQMA}$ differs from $\mathsf{QMA}(2)$ . Indeed, we prove that their precise versions are equal only if $\mathsf{PSPACE}=\mathsf{NEXP}$ . However, this does not necessarily carry over from the precise setting to the “standard” setting. It would therefore be nice to see more evidence that $\mathsf{PureSuperQMA}\subsetneq\mathsf{QMA}(2)$ , such as an oracle separation. Of course, separating $\mathsf{PureSuperQMA}$ from $\mathsf{QMA}(2)$ relative to an oracle is at least as hard as separating $\mathsf{QMA}$ from $\mathsf{QMA}(2)$ in this way, something that has been eluding researchers to this date. Perhaps, however, the new perspective offered by $\mathsf{PureSuperQMA}$ can lead to new insights.

Recently, it has been suggested that purity testing is at the heart of $\mathsf{QMA}(2)$ ’s power [4]. While we provide evidence that $\mathsf{PureCLDM}$ is not $\mathsf{QMA}(2)$ -hard, that does not mean the end for this suggestion. One way to formalize the idea that $\mathsf{QMA}(2)$ ’s power derives from purity would be to prove that $\mathsf{QMA}(2)=\mathsf{PureSuperQMA}(\exp,\frac{1}{\mathrm{poly}},\frac{1}{% \mathrm{poly}})$ . Note that our results do not provide evidence against this equality, as the $\mathsf{PSPACE}$ upper bound crucially relies on there being only polynomially many constraints.

The relationship between $\mathsf{QMA}$ and $\mathsf{PureSuperQMA}$ with a constant number of checks could also be interesting. It can be shown that with a single check $\mathsf{PureSuperQMA}(1,\frac{1}{\mathrm{poly}},0)=\mathsf{QMA}$ as there is no single check passed by a mixed state but not by a pure state⁵⁵5If there exists a mixed state passing the check then there exist pure states $\lvert\psi\rangle,\lvert\phi\rangle$ such that $\lvert\phi\rangle$ is accepted with probability $\leq 1/2$ and $\lvert\psi\rangle$ is accepted with probability $\geq 1/2$ . By interpolating between these states and the Intermediate Value Theorem it follows that there exists some pure state accepted with probability exactly $1/2$ . We have been unable to find a set of 2 constraints with a consistent mixed state but no consistent pure state but leave $\mathsf{PureSuperQMA}(2,\frac{1}{\mathrm{poly}},0)\stackrel{{\scriptstyle?}}{{% =}}\mathsf{QMA}$ as an open question.

Lastly, it would be nice to see if the GP system framework used for our $\mathsf{PSPACE}$ upper bound can find other uses. An approach one could take here is to try to use it for a $\mathsf{PSPACE}$ or $\mathsf{EXP}$ upper bound on $\mathsf{QMA}(2)$ . There are two main obstacles here. Firstly, any such approach needs to make essential use of the promise gap in order to work for $\mathsf{QMA}(2)$ but not for $\mathsf{QMA}(2)_{\mathsf{exp}}$ (assuming $\mathsf{PSPACE}\neq\mathsf{NEXP}$ ). Secondly, naively converting a $\mathsf{QMA}(2)$ instance into polynomials yields degree 3, for which the techniques from [14] no longer work.

2 Preliminaries

The main object of study in this paper is the $k\mathchar 45\relax\mathsf{PureCLDM}$ problem on qubits.

Definition 2.1 ( $k\mathchar 45\relax\mathsf{PureCLDM}$ ).

We are given a set of reduced density matrices $\rho_{1},\dots,\rho_{m}$ with $\mathrm{poly}(n)$ bits of precision, where each $\rho_{i}$ acts on qubits $C_{i}\subseteq[n]$ with $\lvert C_{i}\rvert\leq k$ , as well as thresholds $\alpha,\beta$ with $\beta-\alpha\geq 1/\mathrm{poly}(n)$ . Decide:

$\blacksquare$

YES: There exists a state $\lvert\psi\rangle\in\mathbb{C}^{2^{n}}$ such that $\lVert\operatorname{Tr}_{\overline{C_{i}}}(\lvert\psi\rangle\langle\psi\rvert)% -\rho_{i}\rVert\leq\alpha$ for all $i\in[m]$ .
$\blacksquare$

NO: For all states $\lvert\psi\rangle\in\mathbb{C}^{2^{n}}$ , there exists an $i\in[m]$ such that $\lVert\operatorname{Tr}_{\overline{C_{i}}}(\lvert\psi\rangle\langle\psi\rvert)% -\rho_{i}\rVert\geq\beta$ .

For $\alpha=0$ , we denote the problem by $k\mathchar 45\relax\mathsf{PureCLDM}_{1}$ . Define $k\mathchar 45\relax\mathsf{CLDM}$ and $k\mathchar 45\relax\mathsf{CLDM}_{1}$ analogously, but allowing a mixed state in place of $\lvert\psi\rangle$ .

Note that $\mathsf{PureCLDM}$ and (mixed) $\mathsf{CLDM}$ are indeed different. The following example shows that a consistent mixed state may exist even if no consistent pure state exists.

Example 2.2.

Let $\rho=\frac{1}{n}\sum_{i=1}^{n}\lvert\psi_{i}\rangle\langle\psi_{i}\rvert$ , where $\lvert\psi_{i}\rangle=\lvert 0^{i-1}10^{n-i}\rangle\in\mathbb{C}^{2^{n}}$ . Then all $2$ -local reduced density matrices of $\rho$ are $\rho_{ij}=\frac{n-2}{n}\lvert 00\rangle\langle 00\rvert+\frac{1}{n}\lvert 01% \rangle\langle 01\rvert+\frac{1}{n}\lvert 10\rangle\langle 10\rvert$ . Assume there exists a pure state $\sigma=\lvert\phi\rangle\langle\phi\rvert$ such that $\sigma_{ij}=\rho_{ij}$ for all $i,j\in[n]$ . Then $\lvert\phi\rangle\in\operatorname{Span}\{\lvert 0^{n}\rangle,\lvert\psi_{1}% \rangle,\dots,\lvert\psi_{n}\rangle\}$ since $\rho$ has no overlap with any string of Hamming weight $\geq 2$ . Hence, $\lvert\phi\rangle$ must be of the form $\lvert\phi\rangle=\sum_{i=1}^{n}a_{i}\lvert\psi_{i}\rangle$ with $\lvert a_{i}\rvert=\sqrt{1/n}$ . Then $\sigma_{12}=\frac{2}{n}\lvert\eta\rangle\langle\eta\rvert+\frac{n-2}{n}\lvert 0% 0\rangle\langle 00\rvert$ , where $\lvert\eta\rangle=\sqrt{n/2}(a_{1}\lvert 10\rangle+a_{2}\lvert 01\rangle)$ . However, then $\sigma_{12}\neq\rho_{12}$ since their rank differs, which contradicts the choice of $\lvert\phi\rangle$ .

3 PureSuperQMA

In this section we define the complexity class $\mathsf{PureSuperQMA}$ . Following the definition we prove that $\mathsf{PureSuperQMA}$ contains $\mathsf{PureCLDM}$ and some other properties of the class, suggesting it can be thought of as a “light” version of $\mathsf{QMA}(2)$ . We end the section by establishing a canonical form for $\mathsf{PureSuperQMA}$ , cleaning up the definition. This canonical form will be important in the next section, where we use it for the hardness proof.

Definition 3.1 ( $\mathsf{PureSuperQMA}$ , c.f. [2]).

A promise problem $A$ is in $\mathsf{PureSuperQMA}(m,\varepsilon,\delta)$ if there exists a uniformly generated super-verifier⁶⁶6Our definition of a super verifier here might seem slightly different from Aharanov and Regev’s definition. Note that their definition can be recovered from our by repeating the same constraint as necessary. $\mathcal{V}=\{(V_{x,i},r_{x,i},s_{x,i})\}_{i\in[m]}$ on $n_{1}(n)\in n^{O(1)}$ proof qubits and $n_{2}(n)\in n^{O(1)}$ ancilla qubits ( $n=\lvert x\rvert$ ) such that

$\blacksquare$

$\forall x\in A_{\textup{yes}}\;\exists\lvert\psi\rangle\in\mathcal{P}\colon\Pr% _{i}(\lvert p(V_{x,i},\psi)-r_{x,i}\rvert\leq s_{x,i})=1$ ,
$\blacksquare$

$\forall x\in A_{\textup{no}}\;\forall\lvert\psi\rangle\in\mathcal{P}\colon\Pr_% {i}(\lvert p(V_{x,i},\psi)-r_{x,i}\rvert\leq s_{x,i}+\varepsilon)\leq 1-\delta$ ,

where $\mathcal{P}$ is the set of unit vectors on $n_{1}(n)$ qubits, $i\in[m]$ is drawn uniformly at random, and $p(V,\psi)\coloneq\operatorname{Tr}(\Pi_{\mathrm{acc}}V\lvert\psi,0^{n_{2}}% \rangle\langle\psi,0^{n_{2}}\rvert V^{\dagger})$ denotes the acceptance probability of $V$ on input $\lvert\psi\rangle$ .⁷⁷7Here and in the following, we use $\psi$ to denote the density operator $\lvert\psi\rangle\langle\psi\rvert$ . We call each triple $(V_{x,i},r_{x,i},s_{x,i})$ a constraint or a check. Let

\mathsf{PureSuperQMA}=\bigcup_{m\in n^{O(1)},\varepsilon,\delta\in n^{-O(1)}}% \mathsf{PureSuperQMA}(m,\varepsilon,\delta).

(2)

Lemma 3.2.

$k\mathchar 45\relax\mathsf{PureCLDM}\in\mathsf{PureSuperQMA}$ for $k\leq O(\log n).$

The proof is analogous to the containment of $\mathsf{Pure}\mathchar 45\relax N\mathchar 45\relax\mathsf{Representability}$ in $\mathsf{QMA}(2)$ [23] and can be found in the full version [18].

Proposition 1.5. [Restated, see original statement.]

$\mathsf{QMA}\subseteq\mathsf{PureSuperQMA}\subseteq\mathsf{PureSuperQMA}(\exp,% \frac{1}{\mathrm{poly}},\frac{1}{\mathrm{poly}})\subseteq\mathsf{QMA}(2)$ .

Proof sketch.

First note that $\mathsf{QMA}\subseteq\mathsf{PureSuperQMA}$ follows by setting $r=1$ and $s=\frac{1}{\exp(n)}$ in the definition of $\mathsf{PureSuperQMA}$ . For the other inclusion we use the fact that $\mathsf{QMA}(2)=\mathsf{QMA}(\mathrm{poly})$ [16]. With probability $1/2$ each, the verifier performs one of the following tests: (i) Run swap tests between random disjoint pairs of the registers to ensure the input state is close to a state of the form $\lvert\psi\rangle^{\otimes k}$ . (ii) Pick $i\in[m]$ uniformly at random and run $V_{x,i}$ on all $k$ proofs, recording the outcomes as $y_{1},\dots,y_{k}\in\{0,1\}$ , and let $\mu=\frac{1}{k}\sum_{i=1}^{k}y_{k}$ . Accept if $\lvert\mu-r_{x,i}\rvert\leq s_{x,i}+\varepsilon/2$ . For sufficiently large $k\in n^{O(1)}$ , we can use Hoeffding’s inequality to prove completeness and soundness. $\hfill\blacktriangleleft$

Note that we still get containment in $\mathsf{QMA}(2)$ , even with an exponential number of constraints, as long as in the NO-case the acceptance probability deviates from $r_{x,i}$ for a significant fraction of constraints. However, we do have some reason to believe that $k\mathchar 45\relax\mathsf{PureCLDM}$ is only hard for $\mathsf{PureSuperQMA}$ with a polynomial number of constraints since the hardness proof works for any precision parameter and $k\mathchar 45\relax\mathsf{PureCLDM}\in\mathsf{PSPACE}$ (see Theorem 1.13) even for exponentially small precision. In contrast, if we have both an exponential number of constraints and exponential precision, then $\mathsf{PureSuperQMA}$ contains $\mathsf{NEXP}$ .

See 1.6 Following [6]’s proof of containment of $\mathsf{NP}$ in $\mathsf{QMA}(2)$ with $\log$ -size proofs, the idea behind the proof is verify a $3$ -coloring instance by having the prover send a state of the form $\lvert\psi\rangle=\frac{1}{\sqrt{n}}\sum_{v\in V}\lvert v\rangle_{V}\lvert C(v% )\rangle_{C}$ . To forcing the prover to send a proof of this form we design constraints to force every vertex to show up in the superposition and to have exactly one color associated to it. For the technical details, see the full version [18].

A similar proof using succinct $3$ -coloring rather than normal $3$ -coloring shows the following result.

Proposition 1.7. [Restated, see original statement.]

$\mathsf{PureSuperQMA}(\exp,\frac{1}{\exp},\frac{1}{\exp})=\mathsf{NEXP}$

Since $\mathsf{PureSuperQMA}(\exp,\frac{1}{\exp},\frac{1}{\exp})\subseteq\mathsf{QMA}% (2)_{\exp}$ (i.e. $\mathsf{QMA}(2)$ with exponentially small promise gap) by the same argument as Proposition 1.5, we also recover the following known result:

Corollary 3.3 ([6, 26]).

$\mathsf{QMA}(2)_{\exp}=\mathsf{NEXP}$ , where $\mathsf{QMA}(2)_{\exp}$ denotes $\mathsf{QMA}(2)$ with exponentially small promise gap.

To prove that $2\mathchar 45\relax\mathsf{PureCLDM}$ is $\mathsf{PureSuperQMA}$ -complete, we will use a simplified but equivalent definition:

Definition 3.4 ( $\mathsf{PSQMA}$ ).

A promise problem $A$ is in $\mathsf{PSQMA}(m,\varepsilon)$ if there exists a uniformly generated super-verifier $\mathcal{V}=\{V_{x,i}\}_{i\in[m]}$ on $n_{1}(n)\in n^{O(1)}$ proof qubits and $n_{2}(n)\in n^{O(1)}$ ancilla qubits ( $n=\lvert x\rvert$ ) such that

$\blacksquare$

$\forall x\in A_{\textup{yes}}\;\exists\lvert\psi\rangle\in\mathcal{P}\;\forall i% \in[m]\colon\left\lvert\operatorname{Tr}(\Pi_{\mathrm{acc}}V_{x,i}\lvert\psi,0% ^{n_{2}}\rangle\langle\psi,0^{n_{2}}\rvert V_{x,i}^{\dagger})-\frac{1}{2}% \right\rvert=0$ ,
$\blacksquare$

$\forall x\in A_{\textup{no}}\;\forall\lvert\psi\rangle\in\mathcal{P}\;\exists i% \in[m]\colon\left\lvert\operatorname{Tr}(\Pi_{\mathrm{acc}}V_{x,i}\lvert\psi,0% ^{n_{2}}\rangle\langle\psi,0^{n_{2}}\rvert V_{x,i}^{\dagger})-\frac{1}{2}% \right\rvert\geq\varepsilon$ ,

where $\mathcal{P}$ is the set of unit vectors on $n_{1}(n)$ qubits.

Let $\mathsf{PSQMA}=\bigcup_{m\in n^{O(1)},\varepsilon\in n^{-O(1)}}\mathsf{PSQMA}(% m,\varepsilon)$ .

In other words, $\mathsf{PSQMA}$ is $\mathsf{PureSuperQMA}$ where all the $r$ ’s are set to $\frac{1}{2}$ and all the $s$ ’s to 0.

Lemma 3.5.

$\mathsf{PSQMA}=\mathsf{PureSuperQMA}$ .

4 2-PureCLDM is PureSuperQMA-complete

See 1.3 We give a proof sketch only. The complete proof can be found in the full version [18].

Proof sketch.

Containment holds by Lemma 3.2. It remains to prove that $k\mathchar 45\relax\mathsf{PureCLDM}_{1}$ is $\mathsf{PureSuperQMA}=\mathsf{PSQMA}$ -hard (Lemma 3.5). For simplicity, we only prove hardness of $2\mathchar 45\relax\mathsf{PureCLDM}_{1}$ , but $k>2$ is analogous since simulatability works for any $k$ .

Our proof closely follows the proof for the $\mathsf{QMA}$ -completeness of the (mixed) $\mathsf{CLDM}$ problem by Broadbent and Grilo [9] based on locally simulatable codes. The broad idea behind their proof is as follows: starting with a $\mathsf{QMA}$ verifier $V$ we can use Kitaev’s circuit-to-Hamiltonian construction to build a Hamiltonian $H$ that has low-energy state if and only if $V$ would accept. This low-energy state, the history state, encodes the behavior of the verifier. Broadbent and Grilo’s aim is to construct local density matrices that are consistent with the history state if $V$ accepts, and are inconsistent otherwise.

The main difficulty is that the behavior of the verifier, and hence the history state, depend on the proof given to the verifier. This is solved by considering a different verifier $V^{\prime}$ that mirrors the actions of $V$ but acts on encoded data. By choosing an $s$ -simulatable code for this encoding this has as crucial advantage that the $s$ -local density matrices at any point during the computation can be computed efficiently.⁸⁸8Note that these no longer depend on the proof. Intuitively, all information contained in the proof has been moved to the correlations between larger sets of qubits.

One technical detail that will be especially important to us is that the new verifier $V^{\prime}$ needs to check whether the proof it received is properly encoded. To ensure that the local density matrices can still be computed during this checking procedure, Broadbent and Grilo have the prover send the original proof encoded under a one-time pad and the one-time pad keys. It is this one-time pad constructions that causes the Broadbent Grilo proof to fail for $\mathsf{PureCLDM}$ as a cheating prover could send different pure states for each key, making the full state behave like a mixed state.

We will now sketch our construction. Highlighting especially where we deviate from Broadbent and Grilo. For the technical details and proofs we refer to the full version [18].

Consider a problem $A\in\mathsf{PSQMA}$ that is decided by a super-verifier $\mathcal{V}=\{V_{x,i}\}_{i\in[m]}$ on $n_{1}$ proof qubits and $n_{2}$ ancilla qubits. We will now describe how $\mathcal{V}$ is reduced to a $\mathsf{PureCLDM}$ instance that is consistent if the super-verifier accepts and inconsistent if it rejects.

First, we define a modified super-verifier $\mathcal{V}^{\mathsf{otp}}=\{V^{\mathsf{otp}}_{x,i}\}_{i\in[m^{\prime}]}$ that accepts a one-time padded proof. A crucial difference with Broadbent and Grilo is that we use the same key to encrypt every qubit. The expected proof will be of the form

\lvert\psi^{\mathsf{otp}}\rangle=\frac{1}{2}\sum_{a,b\in\{0,1\}}(X^{a}Z^{b})^{% \otimes n_{1}}\lvert\psi_{ab}\rangle\lvert abab\rangle,

(3)

where the $\lvert\psi_{ab}\rangle$ are proofs accepted by $\mathcal{V}$ that can (but do not have to) depend on $a, b$ . Every individual qubit will still be maximally mixed, but there are only $4$ different keys. By projecting the key register down to fixed values of $a, b$ , the modified super-verifier can check that $\lvert\psi_{ab}\rangle$ is indeed accepted by $\mathcal{V}$ . As there are only a 4 different key values (rather than exponentially many for BG), the super-verifier can include checks for each of the possible projections.

Next, we unify all constraints in $\mathcal{V}^{\mathsf{otp}}$ into a single circuit that we can apply a circuit-to-Hamiltonian construction to, and, following Broadbent and Grilo, make this circuit act on encoded data using an $s$ -simulatable code.

Definition 4.1 ( $s$ -simulatable code [9]⁹⁹9Our definition deviates from [9, Definition 4.1] in that it does not require transversal circuits for all gates. In fact the simulatable codes in [9] also use non-transversal gates for the $T$ -gadgets given in [9, Section 4.3].).

Let $\mathcal{C}$ be an $[[N,1,D]]$ -QECC, and $\mathcal{G}$ a universal gateset, such that for each logical gate $G\in\mathcal{G}$ on $k_{G}$ qubits, there exists a physical circuit $U_{1}^{(G)},\dots,U_{\ell}^{(G)}$ with $\ell\in\mathrm{poly}(N)$ that implements $G$ with the help of an $m_{G}$ -qubit magic state $\tau_{G}$ . We say $\mathcal{C}$ is $s$ -simulatable if there exists a deterministic $2^{O(N)}$ -time algorithm $\mathsf{Sim}_{\mathcal{C}}(G,t,S)$ with $G\in\mathcal{G}$ , $t\in\{0,\dots,\ell\}$ , $S\subseteq[N(m_{G}+k_{G})]$ , $\lvert S\rvert\leq s$ , and output $\rho(G,t,S)$ , such that for any $k_{G}$ -qubit state $\sigma$

\rho(G,t,S)=\operatorname{Tr}_{\overline{S}}\left(\bigl(U_{t}^{(G)}\dotsm U_{1% }^{(G)}\bigr)\operatorname{\mathsf{Enc}}(\sigma\otimes\tau_{G})\bigl(U_{t}^{(G% )}\dotsm U_{1}^{(G)}\bigr)^{\dagger}\right),

(4)

where $\operatorname{\mathsf{Enc}}(\rho)$ denotes the encoding of $\rho$ under $\mathcal{C}$ .

Lemma 4.2 ([15, 9]).

For every $k>\log(s+3)$ , the $k$ -fold concatenated Steane code is $s$ -simulatable.

The unified circuit $V_{x}^{(s)}$ expects the proof to be encoded with $\mathcal{C}$ , such that $\mathcal{C}$ is $(3s+2)$ -simulatable. $V_{x}^{(s)}$ has a proof register $B$ on $n_{1}^{\prime}$ logical qubits, and an ancilla register on $n_{2}^{\prime\prime}>n_{2}^{\prime}$ , where the additional ancilla qubits are used as resources for the $\mathsf{T}$ -gates. $V_{x}^{(s)}$ is defined in Figure 2

The way we combine the $V^{\mathsf{otp}}_{x,i}$ might seem puzzling at first: we run the encoded version of $V^{\mathsf{otp}}_{x,i}$ , decode its output qubit, encode it again and run the encoded version of ${V^{\mathsf{otp}}_{x,i}}^{\dagger}$ . While this acts as the identity, we will be able to extract the acceptance behavior of the $V^{\mathsf{otp}}_{x,i}$ from the history state of $V_{x}^{(s)}$ .

(a)

V_{x}^{(s)}

first checks whether the proof is encoded, then generates resource states, and finally checks all constraints of

\mathcal{V}^{\mathsf{otp}}

.

(b)

\mathsf{ChkEnc}

successively encodes and decodes each qubit. The annotation “

I/2

” denotes the expected reduced density matrix of that qubit.

U_{\mathsf{dec}}

is a unitary such that

U_{\mathsf{dec}}\operatorname{\mathsf{Enc}}(\lvert\psi\rangle)=\lvert\psi% \rangle\otimes\lvert 0^{N-1}\rangle

and

U_{\mathsf{enc}}=U_{\mathsf{dec}}^{\dagger}

.

(c) To verify

V^{\mathsf{otp}}_{x,i}

, first apply the verifier in the code space, then decode the output qubit, which is maximally mixed for acceptance probability

1/2

, and finally undo these steps again.

Figure 2: Super-verifier

V_{x}^{(s)}

. Wires represent logical qubits under

\mathcal{C}

. Note that while the

\mathsf{Chk}

procedures act as identity, their outcome can be read from the history state via the Extraction Lemma.

Unlike Broadbent and Grilo, we use the 2-local circuit-to-Hamiltonian construction from [19] to obtain a Hamiltonian $H$ .¹⁰¹⁰10Broadbent and Grilo use Kitaev’s original 5-local construction. Let us now briefly state an important property of the $2$ -local construction and the Extraction Lemma, which we use to extract the acceptance probabilities of the $V^{\mathsf{otp}}_{x,i}$ from the history state.

Lemma 4.3 (Variant of [19, Lemma 5.1]).

Let $V=U_{T}\dotsm U_{1}$ be a quantum circuit on $n$ qubits that only consists of $1$ -local gates and CZ gates followed and preceded by two $Z$ gates, $n_{1}\leq n$ , and $\varepsilon\in n^{-O(1)}$ . Then there exists a $2$ -local Hamiltonian $H$ on $n+T$ qubits and $\lVert H\rVert\in\mathrm{poly}(n)$ , such that $\langle\phi\rvert H\lvert\phi\rangle=0$ for all $\lvert\phi\rangle\in\mathcal{S}_{\textup{hist}}$ , and if $\operatorname{Tr}(H\rho)\leq 1$ , then there exists a state $\sigma$ in $\mathcal{S}_{\textup{hist}}$ (pure if $\rho$ is pure), such that $\lVert\rho-\sigma\rVert_{\mathrm{tr}}\leq\varepsilon$ , where for $\lvert\widehat{t}\rangle=\lvert 1^{t}\,0^{T-t}\rangle$ ,

\mathcal{S}_{\textup{hist}}:=\operatorname{Span}\left\{\sum_{t=0}^{T}U_{t}% \dotsm U_{1}\lvert x,0^{n_{2}}\rangle\lvert\widehat{t}\rangle\;\middle|\;x\in% \{0,1\}^{n_{1}}\right\}.

(5)

Note that circuits consisting of only $1$ -local gates and CZ gates followed and preceded by two $Z$ gates are universal. We can thus assume that all circuits we consider have this form.

Lemma 4.4 (Extraction Lemma).

Let $\lvert\psi_{\textup{hist}}\rangle=(T+1)^{-1/2}\sum_{t=0}^{T}\lvert\psi_{t}% \rangle\lvert\widehat{t}\rangle\in\mathcal{S}_{\textup{hist}}$ as defined in Lemma 4.3 with $\lvert\psi_{t}\rangle=U_{t}\dotsm U_{1}\lvert\phi,0^{n_{2}}\rangle$ for some $\lvert\phi\rangle\in\mathbb{C}^{2^{n_{1}}}$ . Let $i,j\in[T]$ , $U_{j}=I$ , $S=\{i,n+j\}$ , and $\rho=\operatorname{Tr}_{\overline{S}}(\lvert\psi_{\textup{hist}}\rangle\langle% \psi_{\textup{hist}}\rvert)$ . There exists a linear function $f_{\textup{ex}}$ (independent of the circuit) such that $f_{\textup{ex}}(\rho)=\operatorname{Tr}_{\overline{i}}(\lvert\psi_{j}\rangle% \langle\psi_{j}\rvert)$ and $\lVert f_{\textup{ex}}(A)\rVert_{\mathrm{tr}}\leq(T+1)\lVert A\rVert_{\mathrm{% tr}}$ for all $A$ .

Now suppose we have a state $\lvert\psi\rangle$ approximately consistent with a set of $2$ -local density matrices $\{\rho_{ij}\}$ that has low energy with respect to the $2$ -local Hamiltonian $H=\sum_{ij}H_{ij}$ of Lemma 4.3. Thus $\operatorname{Tr}(H\lvert\psi\rangle\langle\psi\rvert)\approx\sum_{ij}% \operatorname{Tr}(H_{ij}\rho_{ij})\leq 1$ and $\lvert\psi\rangle$ must be close to a history state. In general, we do not know how to compute local density matrices of an accepting history state. However, by the properties of the $s$ -simulatable code, these can be computed for the encoded portion of the circuit. Using the Extraction Lemma, we also know the $1$ -local density matrices of an output qubit after decoding.

Let $\lvert\psi^{(s)}_{\textup{hist}}\rangle$ be the history state for $V_{x}^{(s)}$ , such that the input $\lvert\psi^{\mathsf{otp}}\rangle$ satisfies every constraint in $\mathcal{V}^{\mathsf{otp}}$ perfectly:

\lvert\psi^{(s)}_{\textup{hist}}\rangle=\frac{1}{\sqrt{T+1}}\sum_{t=0}^{T}U_{t% }\dotsm U_{1}\lvert\psi^{\mathsf{otp}}\rangle\lvert 0^{n_{2}^{\prime\prime}}% \rangle\lvert\widehat{t}\rangle.

(6)

Using the properties of the simulatable code, it can be argued that reduced density matrices of $\lvert\psi^{(s)}_{\textup{hist}}\rangle$ can be classically efficiently computed.

Claim 4.5.

There exists a deterministic classical algorithm $\mathsf{Sim}_{V^{(s)}}(x,S)$ that outputs a classical description of $\operatorname{Tr}_{\overline{S}}(\lvert\psi^{(s)}_{\textup{hist}}\rangle% \langle\psi^{(s)}_{\textup{hist}}\rvert)$ for $S\subset[N(n_{1}^{\prime}+n_{2}^{\prime\prime})+T]$ with $\lvert S\rvert\leq s$ in time $\mathrm{poly}(2^{N},T)$ .

To apply the Extraction Lemma we would like to force any state consistent with the output of the reduction to be close to a history state. To achieve this we use the following trick: the reduction computes the energy of the reduced density matrices it would output (this is possible since $H$ is $2$ -local). If this energy is too high, the reduction simply outputs a trivial “No” instance¹¹¹¹11We would like to reject here, but as we are describing the reduction we cannot directly do this. Instead, we output a trivial “No” instance which has the same effect.. If the energy is sufficiently small, we can show that any consistent state must be close to a history state as desired.

We have now assembled all the pieces and are ready to sketch the actual reduction and hardness proof. Let $A\in\mathsf{PSQMA}=\mathsf{PureSuperQMA}$ be as at the beginning of Section 4, and let $V_{x}:=V_{x}^{(2)}=U_{T}\dotsm U_{1}$ be as defined below Lemma 4.2. Given an instance $x\in\{0,1\}^{n}$ , we compute a $2\mathchar 45\relax\mathsf{PureCLDM}$ instance as follows:

1.

Compute the Hamiltonian $H=\sum_{i,j\in[n^{\prime}]}H_{i,j}$ with $n^{\prime}:=N(n_{1}^{\prime}+n_{2}^{\prime\prime})+T$ by applying Lemma 4.3 to $V_{x}$ for $\varepsilon_{1}\in n^{-O(1)}$ (to be determined in the soundness proof).
2.

For all $i,j\in[n^{\prime}]$ , compute $\rho_{ij}=\mathsf{Sim}_{V^{(s)}}(x,\{i,j\})$ .
3.
Compute $E=\sum_{ij}\operatorname{Tr}(H_{ij}\rho_{ij})$ .
1. (a)
  
  If $E=0$ , output $\{\rho_{ij}\}_{i,j\in[n^{\prime}]}$ and $\beta$ (to be determined in the soundness proof).
2. (b)
  
  Otherwise, output a NO-instance for $2\mathchar 45\relax\mathsf{PureCLDM}$ .

This reduction clearly runs in $\mathrm{poly}(n)$ time.

If $x\in A_{\textup{yes}}$ , then the history state $\lvert\psi_{\textup{hist}}^{(2)}\rangle$ defined in Equation 6 is consistent with density matrices $\rho_{ij}$ by ˜4.5.

Using the Extraction Lemma it can be argued that if $x\in A_{\textup{no}}$ , that is, if there is a check that fails, and the $2$ -local density matrices are low-energy, then there is no consistent state, exactly as desired. Note that the fact that the local density matrices are low-energy is enforced by the reduction (if they are not, a trivial NO instance is output). $\hfill\blacktriangleleft$

5 $k\mathchar 45\relax\mathsf{PureCLDM}$ is in $\mathsf{PSPACE}$

In this section we set out to prove the containment of $\mathsf{PureSuperQMA}$ in $\mathsf{PSPACE}$ . However, the techniques we develop for this result turn out to be much more general and lead to a poly-logarithmic time parallel algorithm (i.e., $\mathsf{NC}$ ) for solving quadratic systems with few constraints.

See 1.8 At a high level, the proof consists of three steps. First, we reduce $\mathsf{PureSuperQMA}$ to deciding if $p(Q(X))$ has any zeros. Here $p\colon\mathbb{R}^{\mathrm{poly}(n)}\to\mathbb{R}$ is a degree $\mathrm{poly}(n)$ polynomial in $\mathrm{poly}(n)$ variables and $Q\colon\mathbb{R}^{\exp(n)}\to\mathbb{R}^{\mathrm{poly}(n)}$ is a quadratic polynomial. Next, we use results by Grigoriev and Pasechnik [14] that reduce finding zeros of $p(Q(X))$ to finding limits of zeros of smaller systems. There will be $\exp(n)$ smaller systems, each consisting of $\mathrm{poly}(n)$ equations of degree at most $\exp(n)$ . Crucially, these equation will have at most $\mathrm{poly}(n)$ variables. We modify this reduction to work in $\mathsf{PSPACE}$ . We then compute these limits efficiently in parallel using an algorithm for the first-order theory of the reals by Renegar [27], making the total computation a $\mathsf{PSPACE}$ computation and proving the theorem.

5.1 $\mathsf{PureSuperQMA}$ as a polynomial system

We first describe how to reduce $\mathsf{PureSuperQMA}$ to a GP system.

Definition 5.1 (Grigoriev-Pasechnik system (GP system) [14]).

A GP system is a polynomial of the form $p(Q(X))$ where $p\colon\mathbb{R}^{k}\to\mathbb{R}$ is a degree $d$ polynomial and $Q=(Q_{1},\dots,Q_{k})\colon\mathbb{R}^{N}\to\mathbb{R}^{k}$ is a quadratic map. Both are assumed to have coefficients in $\mathbb{Z}$ .¹²¹²12The techniques by Grigoriev and Pasechnik are valid in the more general case where $\mathbb{R}$ is replaced by an arbitrary real closed field $\mathbb{K}$ and $\mathbb{Z}$ with a computable subring of that field. We say a GP system is satisfiable if there exists $x\in\mathbb{R}^{N}$ such that $p(Q(x))=0$ .

Consider a super-verifier $\mathcal{V}=\{(V_{i},r_{i},s_{i})\}_{[k]}$ where $k=\mathrm{poly}(n)$ . In this section we will let $V_{i}$ denote the POVM measurement operator implemented by the circuit so that the acceptance probability $p(V,\psi)=\langle\psi\rvert V_{i}\lvert\psi\rangle$ . In the YES-case, there exists some quantum state $\lvert\psi\rangle\in\mathbb{C}^{2^{n}}$ such that for all $i$ ,

|\langle\psi\rvert V_{i}\lvert\psi\rangle-r_{i}|\leq s_{i}

(7)

whereas in the NO-case there will be at least one $i$ for which $|\langle\psi\rvert V_{i}\lvert\psi\rangle-r_{i}|>s_{i}$ . Note that depending on the $\delta$ parameter in Definition 3.1, there could be more such $i$ but this is not required for our methods. What is required for our method to work is that $k$ , the total number of different $(V_{i},r_{i},s_{i})$ the super-verifier could output, is polynomial.

To distinguish the two cases, we write the $n$ -qubit state $\lvert\psi\rangle$ as an exponentially long vector in $\mathbb{C}^{N}$ . Here and in the rest of this section $N=2^{n}$ . For each entry of the vector we introduce two variables: one for the real part and one for the complex part. That is, we write

\lvert\psi\rangle=\begin{pmatrix}a_{1}+b_{1}i\\ \vdots\\ a_{N}+b_{N}i.\end{pmatrix}

(8)

Note that for any assignment of the variables $(a_{1},b_{1},\dots,a_{N},b_{N})\in\mathbb{R}^{2N}$ we get an (unnormalized) vector in $(\mathbb{C}^{2})^{\otimes n}$ . We now construct a GP system that is satisfiable if and only if an accepting proof state exists.

First, to ensure that the $a_{j},b_{j}$ represent a normalized quantum state we define

Q_{0}(a_{1},b_{1},\dots,a_{N},b_{N})=\|\lvert\psi\rangle\|^{2}-1=\left(\sum_{j% =1}^{N}a_{j}^{2}+b_{j}^{2}\right)-1

(9)

Next, note that $\langle\psi\rvert V_{i}\lvert\psi\rangle$ is already a quadratic equations. Although $\lvert\psi\rangle$ can have a complex part $\langle\psi\rvert V_{i}\lvert\psi\rangle$ will be real since $V_{i}$ is positive semidefinite. We define

Q_{i}(a_{1},b_{1},\dots,a_{N},b_{N})=\langle\psi\rvert V_{i}\lvert\psi\rangle-% r_{i},\quad\text{for }i\in[k].

(10)

In order to handle the inequalities in Equation 7 we will add slack variables $c_{1},\dots c_{k}$ and define $Q_{k+i}=c_{i},\quad\text{for }1\leq i\leq k.$ We now put all constraints together and define

p(y_{0},\dots,y_{2k})=y_{0}^{2}+\sum_{j=1}^{k}(y_{j}^{2}+y_{k+j}^{2}-s_{j}^{2}% )^{2}.

(11)

We then have

p(Q(a_{1},b_{1}\dots,a_{N},b_{N},c_{1},\dots,c_{k}))=\left(\|\lvert\psi\rangle% \|^{2}-1\right)^{2}+\sum_{j=1}^{k}\left((\langle\psi\rvert V_{j}\lvert\psi% \rangle-r_{i})^{2}+c_{j}^{2}-s_{j}^{2}\right)^{2}.

(12)

Note that $p(Q(X))$ will be zero only when all component parts are zero. The first term enforces that the norm of $\lvert\psi\rangle$ is $1$ . Meanwhile, the $j$ -th term in the sum makes sure that $(\langle\psi\rvert V_{j}\lvert\psi\rangle-r_{j})^{2}$ can be made equal to $s_{j}^{2}$ by adding some nonnegative value $c_{j}^{2}$ . In other words, it ensures that $|\langle\psi\rvert V_{j}\lvert\psi\rangle-r_{j}|\leq s_{j}$ . We conclude that $p(Q(a_{1},b_{1}\dots,a_{N},b_{N},c_{1},\dots,c_{k}))$ has a zero if and only if there exists some quantum state $\lvert\psi\rangle$ such that for all $i$ , $|\langle\psi\rvert V_{i}\lvert\psi\rangle-r_{i}|\leq s_{i}$ , which is exactly as we set out to construct.

5.2 Reducing the number of variables

In this subsection, we consider a general GP system $p(Q(X))=\zeta$ and describe Grigoriev and Pasechnik’s methods for reducing the number of variables. The full version [18] of the work contains a quite thorough treatment of their methods, reproducing large parts of their construction. We hope this makes their methods easily accessible to other quantum theorists.

Without loss of generality, we can write $Q$ as

Q_{j}:X\mapsto\frac{1}{2}X^{\mathsf{T}}H_{j}X+b_{j}^{\mathsf{T}}X+c_{j},\quad j% \in[k],c_{j}\in\mathbb{Z},b_{j}\in\mathbb{Z}^{N},H_{j}=H_{j}^{\mathsf{T}}\in% \mathbb{Z}^{N\times N}.

(13)

Define $p_{i}=\frac{\partial p(Y)}{\partial Y_{i}}$ for all $i\in[k]$ .

For their main construction, Grigoriev and Pasechnik rely on some assumptions. These assumptions hold generically, but could fail in certain degenerate cases. We will later discuss how these assumptions are removed. We assume the following:

(1)

The set $Z=Z(p(Q(X)))$ of zeros of $p(Q(X))$ is bounded, i.e., there is some $r$ such that $\|X\|>r\implies p(Q(X))\neq 0$ . In our case, this assumption is trivially satisfied because of the normalization constraint Equation 9.
(2)

$\zeta$ is a regular value of $p(Q(x))$ and $p(Y)$ . That is, there exists no $X\in\mathbb{R}^{n}$ (respectively $Y\in\mathbb{R}^{k}$ ) with $p(Q(X))=\zeta$ (respectively $p(Y)=\zeta$ ) for which $\nabla p(Q(X))=0$ (respectively $\nabla p(Y)=0$ ).
(3)

The matrices $\hat{H}_{i}$ obtained from $H_{i}$ by deleting the first row are in $r$ -general position. I.e.,

$\operatorname{rk}\left(\sum_{i=1}^{k}t_{i}\hat{H}_{i}\right)\geq r,\qquad% \forall t\in\{(p_{1}(Q(X)),\dots,p_{k}(Q(X)))\mid X\in Z\}.$ (14)

Note that Assumption 2 implies that $t$ is never $0$ in the above.

We are now ready to summarize Grigoriev and Pasechnik’s construction as the following theorem.

Theorem 5.2 ([14, Theorem 4.5]).

Let $p, Q$ be a GP system satisfying the three assumptions above. Then, one can construct sets $V_{c}(U,W)$ , such that $\bigcup V_{c}(U,W)$ intersects every connected component of $Z$ .

The sets $V_{c}(U,W)$ , also called “pieces”, are indexed by row sets $U\subseteq\{2,\dots,N\}$ and column sets $W\subset[N]$ such that $r\leq\lvert U\rvert=\lvert W\rvert\leq N-1$ . For such a $W$ , let $\phi_{W}$ denote the polynomial

\phi_{W}:\mathbb{R}^{N}\to\mathbb{R}^{k+N-\lvert W\rvert},\quad X\mapsto\begin% {pmatrix}Q(X)\\ X_{\overline{W}}\end{pmatrix}.

(15)

Here $\overline{W}=[N]\backslash W$ . For each $V_{c}(U,W)$ , the set $\phi_{W}(V_{c}(U,W))\subseteq\mathbb{R}^{k}\times\mathbb{R}^{N-|W|}$ is defined as the set of points satisfying the following equations:


$\displaystyle p(Y)$	$\displaystyle=\zeta,$	(16a)
$\displaystyle\Omega\coloneq\det\Phi(Y)_{UW}$	$\displaystyle\neq 0,$	(16b)
$\displaystyle\Omega^{2}Y$	$\displaystyle=\Omega^{2}Q(\phi_{UW}^{-1}(Y,T)),$	(16c)
$\displaystyle\Omega b(Y)_{\overline{U}}$	$\displaystyle=\Omega\Phi(Y)_{\overline{U}W}\Phi(Y)^{-1}_{UW}\cdot b(Y)_{U},$	(16d)
$\displaystyle\det\Phi(Y)_{U^{\prime}W^{\prime}}$	$\displaystyle=0\quad\forall U^{\prime},W^{\prime}:\lvert U^{\prime}\rvert=% \lvert W^{\prime}\rvert=\lvert U\rvert+1,U\subset U^{\prime}\subset\{2,\dots,N\},$	(16e)
	$\displaystyle\phantom{=0\quad\forall U^{\prime},W^{\prime}:}\quad W\subset W^{% \prime}\subset[N].$

Here $\Phi(Y)=\sum_{j=1}^{k}p_{j}(Y)\hat{H}_{j}$ and $\phi_{UW}^{-1}(Y,T)$ is the inverse of $\phi_{W}$ on $\phi_{W}(V_{c}(U,W))$ , given by

\phi_{UW}^{-1}:\mathbb{R}^{k}\times\mathbb{R}^{N-|W|}\to\mathbb{R}^{N},\quad% \begin{pmatrix}Y\\ T\end{pmatrix}\mapsto\begin{pmatrix}\Phi(Y)^{-1}_{UW}(b(Y)_{U}-\Phi(Y)_{U% \overline{W}}T)\\ T\end{pmatrix}

(17)

If $r=N-k+1$ (which will be ensured later with Lemma 5.4), then there are $N^{O(k)}$ pieces, each defined by $O(k^{2})$ polynomials of degree $O(N)$ in $O(k)$ variables.

Lastly, if the coefficients of $p$ and $Q$ are integers of bit length at most $L$ , then $\phi^{-1}_{UW}$ and the equations defining the $V_{c}(U,W)$ can be computed from the coefficients of $Q$ and $p$ in time $\mathrm{poly}(\log N,\log d,k,\log L)$ using $(dN)^{O(k)}L^{O(1)}$ parallel processors.

$\blacktriangleright$ Remark 5.3.

Theorem 5.2 still holds with the same runtime and processor bounds when the GP system has coefficients in $\mathbb{Z}[C]$ of degree $O(1)$ (instead of $\mathbb{Z}$ ), for real constants $C=(C_{1},\dots,C_{m})\in\mathbb{R}^{m}$ and $m=O(k)$ . The algorithm then also outputs the equations for the pieces with coefficients in $\mathbb{Z}[C]$ . Note that the input and output representations treat these constants symbolically (i.e. like free variables), so that the output is independent of the actual value of $C$ . In the proof of Theorem 5.2 the additional constants can be handled just like the variables.

5.2.1 Removing the assumptions

We now turn to the removal of the assumptions made in Theorem 5.2. To do so, Grigoriev and Pasechnik use limit arguments. The key idea is that if we perturb the initial system of polynomials slightly, there will be at most finitely many values of the perturbation for which the assumptions fail. Hence, if the perturbation is sufficiently small, all assumptions will hold. They then argue that the solutions to our initial system are equal to the solutions of the perturbed system if we let the perturbation go to zero. The assumptions will hold in the limit. We will later discuss how we can compute these limits.

The following lemma deals with the general position assumption.

Lemma 5.4 ([14, Lemma 5.2]).

Let $p, Q$ be a GP system and write $Q$ as

Q_{j}:X\to\frac{1}{2}X^{\mathsf{T}}H_{j}X+b_{j}^{\mathsf{T}}X+c_{j},\quad j\in% [k],c_{j}\in\mathbb{Z},b_{j}\in\mathbb{Z}^{N},H_{j}=H_{j}^{\mathsf{T}}\in% \mathbb{Z}^{N\times N}.

(18)

Define $J(j)$ to be the $N\times N$ matrix with diagonal $(1^{j-1},2^{j-1},\dots,N^{j-1})$ and perturb $Q$ by defining

\tilde{Q}_{j}(X,\varepsilon)=Q_{j}(X)+\frac{\varepsilon}{2}X^{\mathsf{T}}J(j)X.

(19)

Then, there is some constant $\varepsilon^{\prime}$ such that for $0<\varepsilon<\varepsilon^{\prime}$ , the matrices $\tilde{H}_{j}(\varepsilon)$ obtained by deleting the first row of $H_{j}+\varepsilon J(j)$ will be in $N-k+1$ general position. In fact, for all $0\neq y\in\mathbb{R}^{k}$ the matrix

A(y,\varepsilon)=\sum_{j=1}Y_{j}(H_{j}+\varepsilon J(j))

(20)

will have $\operatorname{rk}(A)\geq N-k+1$ .

Next, Grigoriev and Pasechnik deal with the assumption 2 by showing that any $\zeta\neq 0$ that is sufficiently close to zero is a regular value of $p(Q(X))$ and $p(Y)$ .

Lemma 5.5 ([14, Lemma 5.3]).

Let $p\colon\mathbb{R}^{k}\to\mathbb{R}$ and $Q\colon\mathbb{R}^{n}\to\mathbb{R}^{k}$ be polynomials. Then $p(Y)$ and $p(Q(X))$ each have at most finitely many critical values.

We have now established that $p(\tilde{Q}(X,\varepsilon))-\zeta$ satisfies all assumptions required for Theorem 5.2 when $\varepsilon,\zeta$ are sufficiently small. In order to use this to find solutions to our original equation we need to relate $Z=Z(p(Q(X)))$ to $\tilde{Z}(\zeta,\varepsilon)=Z(p(\tilde{Q}(X,\varepsilon))-\zeta)$ . Clearly, if $\zeta$ and $\varepsilon$ are very small and $X^{*}$ is a zero of $p(\tilde{Q}(X,\varepsilon))-\zeta$ then $p(Q(X^{*}))$ will be close to zero. This could suffice for finding approximate solutions, but to solve the problem exactly we need something more. Grigoriev and Pasechnik provide this by proving that $Z$ coincides exactly with the limit of $\tilde{Z}(\zeta,\varepsilon)$ as $\zeta,\varepsilon\downarrow 0$ . They consider the solutions of $p(\tilde{Q}(X,\varepsilon))-\zeta$ as Puiseux series in $\zeta$ and $\varepsilon$ and prove that the limits of these are exactly the zeros of $p(Q(X))$ . For us, however, it will be more convenient to consider $\tilde{Z}(\zeta,\varepsilon)$ as sets depending on $\zeta$ and $\varepsilon$ and take the limit of these sets as $\zeta,\varepsilon\downarrow 0$ . In the rest of the paper we use the following notion of limits of sets. Strictly speaking, our definition is that of the Kuratowski limit inferior, which of course coincides with the Kuratowski limit if this exists.

Definition 5.6.

For $\varepsilon\in(0,1)$ let $S_{\varepsilon}\subseteq\mathbb{R}^{n}$ . Then we define

\lim_{\varepsilon\downarrow 0}S_{\varepsilon}=\{X\in\mathbb{R}^{n}\colon% \forall r\in\mathbb{R}_{>0}\exists\varepsilon_{0}\forall\varepsilon<% \varepsilon_{0}\exists Y\in S_{\varepsilon}\text{ s.t. }\left\lVert X-Y\right% \rVert<r\}.

(21)

Theorem 5.7 ([14, Theorem 5.4]).

For fixed $\varepsilon,\zeta$ , let $\tilde{Z}(\varepsilon,\zeta)$ be the zeros of $p(\tilde{Q}(X,\varepsilon))-\zeta$ and let $Z=Z(p(Q(X)))$ be the zeros of $p(Q(X))$ . Then we have

Z=\lim_{\zeta\downarrow 0}\lim_{\varepsilon\downarrow 0}\tilde{Z}(\varepsilon,% \zeta).

(22)

To test whether $Z$ is empty, it suffices to check whether there is a sequence of nonempty $\tilde{Z}$ .

Lemma 5.8.

$Z\neq\emptyset$ iff there exists a sequence $\zeta_{n},\varepsilon_{n}\to 0$ such that $\tilde{Z}(\varepsilon_{n},\zeta_{n})\neq\emptyset$ .

Proof.

If $Z\neq\emptyset$ , then by Theorem 5.7, for every sufficiently small $\zeta>0$ , there exists an $\varepsilon_{\zeta}$ , such that $\tilde{Z}(\varepsilon,\zeta)\neq 0$ for all $\varepsilon\in(0,\varepsilon_{\zeta}]$ . Thus, we can easily construct the sequence $\zeta_{n}=O(1/n),\varepsilon_{n}=\varepsilon_{\zeta_{n}}$ with $\tilde{Z}(\varepsilon_{n},\zeta_{n})\neq\emptyset$ .

Now given a sequence $\zeta_{n},\varepsilon_{n}$ with $\tilde{Z}(\varepsilon_{n},\zeta_{n})\neq\emptyset$ , we can select $X_{n}\in\tilde{Z}(\varepsilon_{n},\zeta_{n})$ , and since $\tilde{Z}(\varepsilon,\zeta)$ is bounded (for sufficiently small $\varepsilon,\zeta$ ), we can apply the Bolzano-Weierstrass theorem to pick a subsequence $X_{n}\to X^{*}$ . We have $p(\tilde{Q}(X_{n},\varepsilon_{n}))=\zeta_{n}$ . Due to continuity it follows $\lim_{n}p(\tilde{Q}(X_{n},\varepsilon_{n}))=p(Q(X^{*}))=0$ and $X^{*}\in Z$ . $\hfill\blacktriangleleft$

5.3 Solving the smaller systems using algorithms for the first-order theory of the reals

We now have a way to determine if $p(Q(X))$ has a zero: first, we consider the perturbed system $p(\tilde{Q}(X,\varepsilon))-\zeta$ . By Lemma 5.8 it suffices to check if there is a sequence of nonempty $\tilde{Z}$ . For sufficiently small $\zeta,\varepsilon$ we can use Theorem 5.2 with Remark 5.3 (setting $C\coloneq(\zeta,\varepsilon)$ ) to find sets $V_{c}(U,W,\zeta,\varepsilon)$ such that $\bigcup_{U,W}V_{c}(U,W,\zeta,\varepsilon)$ intersects all connected components of $\tilde{Z}(\zeta,\varepsilon)$ . In particular, a sequence of nonempty $\tilde{Z}$ exists iff there exists a sequence of nonempty $\phi_{W}(V_{c}(U,W,\zeta,\varepsilon),\varepsilon)$ . Here

\phi_{W}\colon(X,\varepsilon)\mapsto\begin{pmatrix}\tilde{Q}(X,\varepsilon)\\ X_{\overline{W}}\end{pmatrix}.

(23)

The sets $\phi_{W}(V_{c}(U,W,\zeta,\varepsilon),\varepsilon)$ will be defined as the solutions to


$\displaystyle p(Y)$	$\displaystyle=\zeta,$	(24a)
$\displaystyle\Omega\coloneq\det\Phi(Y,\varepsilon)_{UW}$	$\displaystyle\neq 0,$	(24b)
$\displaystyle\Omega^{2}Y$	$\displaystyle=\Omega^{2}\tilde{Q}(\phi_{UW}^{-1}(Y,T,\varepsilon),\varepsilon),$	(24c)
$\displaystyle\Omega b(Y)_{\overline{U}}$	$\displaystyle=\Omega\Phi(Y,\varepsilon)_{\overline{U}W}\Phi(Y,\varepsilon)^{-1% }_{UW}\cdot b(Y)_{U},$	(24d)
$\displaystyle\det\Phi(Y,\varepsilon)_{U^{\prime}W^{\prime}}$	$\displaystyle=0\quad\forall U^{\prime},W^{\prime}:\lvert U^{\prime}\rvert=% \lvert W^{\prime}\rvert=\lvert U\rvert+1,U\subset U^{\prime}\subset\{2,\dots,n\},$	(24e)
	$\displaystyle\phantom{=0\quad\forall U^{\prime},W^{\prime}:}\quad W\subset W^{% \prime}\subset[n],$

where we have written $\tilde{Q}_{j}(X,\varepsilon)=\frac{1}{2}X^{\mathsf{T}}H_{j}(\varepsilon)X+b_{j% }^{\mathsf{T}}X+c_{j}$ (see Lemma 5.4) and $\Phi(Y,\varepsilon)=\sum_{j=1}^{k}p_{j}(Y)\hat{H}_{j}(\varepsilon)$ for $\hat{H}_{j}(\varepsilon)$ the matrix $H_{j}(\varepsilon)$ with the first row deleted.

We will write the existence of such a sequence of $\phi_{W}(V_{c}(U,W,\zeta,\varepsilon),\varepsilon)$ as a sentence in the first-order theory of the reals.

Definition 5.9 (First-order theory of the reals).

The first-order theory of the reals is concerned with sentences of the form

Q_{1}x_{1}\in\mathbb{R}^{n_{1}}Q_{2}x_{2}\in\mathbb{R}^{n_{2}}\dots Q_{q}x_{q}% \in\mathbb{R}^{n_{q}}P(x_{1},\dots,x_{q}),

(25)

where

$\blacksquare$

the $Q_{i}$ are alternating quantifiers
$\blacksquare$

$P$ is a quantifier-free Boolean formula in atomic formulas of the form $f(x_{1},\dots,x_{q})\Delta 0$ . Here $f\colon\mathbb{R}^{n_{1}}\times\dots\times\mathbb{R}^{n_{q}}\to\mathbb{R}$ is a polynomial with integer coefficients and $\Delta$ is one of the relation symbols $\leq,<,=,>,\geq,\neq$ .

We write the set of all true sentences of this form as $\text{Th}(\mathbb{R})$ .

Theorem 5.10 ([27, Theorem 1.1]).

There is an algorithm that, given a sentence $\varphi$ of the form of Equation 25 involving only polynomials with integer coefficients¹³¹³13To deal with algebraic coefficients we can add additional variables and polynomials enforcing that these variables take the value of the required algebraic numbers., decides whether $\varphi\in\text{Th}(\mathbb{R})$ . The algorithm uses $L^{2}(md)^{2^{O(q)}\prod_{i=1}^{q}n_{i}}$ parallel processors and requires $\log(L)\left(2^{q}\left(\prod_{i=1}^{q}n_{i}\right)\log(md)\right)^{O(1)}+% \textup{Time}(P)$ time. Here $L$ denotes the maximal bit size of the coefficients of the polynomials in $\varphi$ , $m$ the number of polynomial (in)equalities in $\varphi$ , $d$ the maximal degree of these polynomials, and $\textup{Time}(P)$ the worst case time required for computing $P$ when the atomic formulas are substituted for Boolean values.

Combining this result with Lemma 5.8 we get the following result. See 1.13

Proof.

By Lemma 5.8, it suffices to check whether there exists a sequence of $\varepsilon,\zeta\to 0$ , such that $\tilde{Z}(\varepsilon,\zeta)\neq\emptyset$ . By Lemma 5.4, assumption (3) is satisfied for sufficiently small $\varepsilon$ (independent of $\zeta$ ). By Lemma 5.5, for every $\varepsilon$ there exist only a finite number of critical values (or “bad” $\zeta$ ). Thus, if there exist a suitable sequence $\varepsilon,\zeta$ , we may also assume that the assumptions of Section 5.2 hold. By Theorem 5.2, there must be a subsequence $(\varepsilon_{n},\zeta_{n})\to 0$ and $U, W$ such that $\tilde{Z}(\varepsilon_{n},\zeta_{n})\cap V_{c}(U,W,\varepsilon_{n},\zeta_{n})\neq\emptyset$ for all $n$ . Therefore $Z\neq\emptyset$ is equivalent to the following FOTR sentence being true for some $U, W$ , which we can test in parallel:

\Xi_{U,W}\coloneq\forall\gamma>0\;\exists\varepsilon,\zeta\in(0,\gamma)\;% \exists Y,T\colon(Y,T)\in\phi_{W}\bigl(V_{c}(U,W,\varepsilon,\zeta)\bigr),

(26)

where $(Y,T)\in\phi_{W}(V_{c}(U,W,\zeta,\varepsilon))$ is shorthand for $(Y,T)$ satisfies Equation 24, which then implies $\phi^{-1}_{UW}(Y,T,\varepsilon)\in\tilde{Z}(\varepsilon,\zeta)$ . We can test this sentence using Theorem 5.10. The complexity bounds follow from those of Theorems 5.10 and 5.2. $\hfill\blacktriangleleft$

The proof of Theorem 1.8 now follows directly from applying Theorem 1.13 to the discussion in Section 5.1.

6 Approximation and Optimization

In the previous section, we showed how to solve the (decision) $\mathsf{PureCLDM}$ problem. Next, we give a parallel polynomial time algorithm (i.e. (function) $\mathsf{NC}(\mathrm{poly})$ ) to compute an approximate description of the consistent state. It is worth emphasizing that our algorithm computes an approximation to an exactly consistent state, and not just a state that is approximately consistent.

If the density matrices are slightly perturbed, there may not be a perfectly consistent state. We can compute the state that minimizes the “error” (e.g. the minimum $\alpha$ such that the given instance is a YES-instance per Definition 2.1) by solving OptGP as defined in Definition 1.14.

Theorem 1.15. [Restated, see original statement.]

Let $r, p, Q$ be an OptGP instance. There is a parallel algorithm that computes a $\delta$ -approximation to $\theta=\min_{X\in Z}r(Q(X))$ and to some $X^{*}$ with $r(Q(X^{*}))=\theta$ and $p(Q(X^{*}))=0$ . The algorithm uses $\mathrm{poly}\bigl(L,|\log\delta|,(kNd)^{O(k^{2})}\bigr)$ parallel processors and needs $\mathrm{poly}(\log N,\log d,k,\log L,\log|\log\delta|)$ time.

6.1 Computing the minimum

The first step in solving the approximation problem of Theorem 1.15 is to compute $\theta$ . For that, we will use Renegar’s algorithm for finding approximate solutions to first-order theory of the reals formulas.

Theorem 6.1 ([29, Theorem 1.2]).

Let $\varphi(y)$ be a formula as in Equation 25 involving free variables $y\in\mathbb{R}^{l}$ , let $0<\varepsilon<r$ be powers of $2$ and define $sol(\varphi,r)=\{y\in\mathbb{R}^{l}\colon\varphi(y)\wedge\|y\|\leq r\}$ . Then there exists an algorithm that constructs a set $\{y_{i}\}_{i}$ , such that for every connected component of $sol(\varphi,r)$ , there is at least one $y_{i}$ within distance $\varepsilon$ of the component.

The algorithm can be implemented using $(L+|\log\varepsilon|+|\log r|)^{O(1)}(md)^{2^{O(q)}l\prod_{j=1}^{q}n_{j}}$ parallel processors. It then requires time $\bigl[2^{q}l\bigl(\prod_{j=1}^{q}n_{j}\bigr)\log\left(mdL+|\log\varepsilon|+|% \log r|\right)\bigr]^{O(1)}+\textup{Time}(P).$ Here $m$ is the number of polynomials in $\varphi$ , $d$ their maximum degree, $L$ the maximum bit length of the coefficients of these polynomials, $q$ the number of quantifiers and $\textup{Time}(P)$ the worst case parallel time to compute $P$ when the atomic formulas are substituted for Boolean values.

It is relatively straightforward to compute $\theta$ with the above theorem. To that end, define $p_{\theta}(Y)\coloneq(p(Y))^{2}+(r(Y)-\theta)^{2}$ . We will compute $\theta$ by finding the minimum $\theta$ for which $Z_{\theta}\coloneq Z(p_{\theta}(Q(X)))\neq\emptyset$ . Since $Z$ is compact, the minimum $\theta=\min_{X\in Z}r(Q(X))$ must exist. Hence, there must exist a piece $U, W$ , such that the FOTR sentence $\Xi_{U,W}(\theta)$ is true, where $\Xi_{U,W}(\theta)$ is defined as in Equation 26, but with the additional parameter $\theta$ (see Remark 5.3). Note that since $\theta$ is minimal, $\Xi_{U,W}(\theta^{\prime})\wedge\theta^{\prime}<\theta$ cannot hold. Formally, $\theta$ is minimal iff the sentence following sentence is true:

\Xi_{U,W}\wedge\forall\theta^{\prime}\colon\Xi_{U,W}(\theta^{\prime})% \rightarrow(\theta^{\prime}\geq\theta)

(27)

Since $t$ is a free variable in the above sentence, we can approximate it using Theorem 6.1 for all pieces in parallel, and then take the minimum.

6.2 Computing the solution vector

Next, we are going to show how to compute $X^{*}$ such that $p(Q(X^{*}))=0$ and $r(Q(x^{*}))=\theta$ and thereby prove Theorem 1.15. Naively, we could use Theorem 6.1 to compute $X^{*}$ . However, that will not lead to the desired runtime since the dimension of $X$ is exponentially large. We modify $\Xi_{U,W}$ from Equation 26 to find “good enough” $(\tilde{Y},\tilde{T})\in\tilde{Z}(\varepsilon,\zeta)$ with $\tilde{X}\coloneq\phi^{-1}_{U,W}(\tilde{Y},\tilde{T},\varepsilon)$ , such that there exists some $X\in Z$ with $\lVert X-\tilde{X}\rVert\leq\delta$ for some desired accuracy parameter $\delta$ , which can be chosen exponentially small in $N$ . The existence of $\tilde{Y},\tilde{T}$ follows by a similar to the proof of Lemma 5.8.

We will use a univariate representation to compute $\tilde{Y},\tilde{T}$ exactly and then Theorem 6.1 to obtain approximations to the entries of $\tilde{X}$ in parallel. ¹⁴¹⁴14One could also compute $\tilde{X}$ numerically, but then numerical errors need to be considered. The next theorem shows how to compute univariate representations of the solutions to an FOTR sentence. It is a straightforward combination of [27, Proposition 2.3.1 and 3.8.1] and [28, Proposition 6.2.2].

Theorem 6.2.

Let $\varphi(y)$ be a formula of the form Equation 25 with free variables $y\in\mathbb{R}^{l}$ . Then, there exists a set $\cal{P}(\varphi)$ of $(md)^{2^{O(q)}l\prod_{j}n_{j}}$ pairs of polynomials $(p,F)$ where $p\colon\mathbb{R}\to\mathbb{R}$ and $F\colon\mathbb{R}\to\mathbb{R}^{l+1}$ with the following property. For every connected component $C$ of $\{y\in\mathbb{R}^{l}\colon\varphi(y)\}$ , there is a $(p,F)\in\cal{P}(\varphi)$ such that for some root $t^{*}$ of $p$ , $\operatorname{Aff}(F(t^{*}))$ is well defined and in $C$ . Here $\operatorname{Aff}(F(t^{*}))$ denotes the affine image $\frac{1}{F_{l+1}(t^{*})}(F_{1}(t^{*}),\dots,F_{l}(t^{*}))$

The sets $\cal{P}(\varphi)$ can be constructed in parallel using $L^{2}(md)^{2^{O(q)}l\prod_{j=1}^{q}n_{j}}$ processors and time $(\log L)\left(2^{q}l\left(\prod_{j=1}^{q}n_{j}\right)\log(md)\right)^{O(1)}$ . Here $m$ is the number of polynomial (in)equalities appearing in $\varphi$ , and $d$ is their maximum degree.

We have now established all the components to prove Theorem 1.15. The proof can be found in the full version [18].

References

[1] Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. The power of unentanglement. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 223–236, 2008. doi:10.1109/CCC.2008.5.
[2] D. Aharonov and O. Regev. A lattice problem in quantum NP. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 210–219, 2003. doi:10.1109/SFCS.2003.1238195.
[3] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, April 2009. doi:10.1017/cbo9780511804090.
[4] Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, and Pei Wu. Quantum Merlin-Arthur with an internally separable proof, 2024. doi:10.48550/arXiv.2410.19152.
[5] Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. Quantum Merlin-Arthur and proofs without relative phase. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2024.9.
[6] Hugue Blier and Alain Tapp. A quantum characterization of NP. computational complexity, 21(3):499–510, September 2012. doi:10.1007/s00037-011-0016-2.
[7] Allan Borodin. On relating time and space to size and depth. SIAM Journal on Computing, 6(4):733–744, 1977. doi:10.1137/0206054.
[8] Fernando G. S. L. Brandão and Aram W. Harrow. Quantum de finetti theorems under local measurements with applications. Communications in Mathematical Physics, 353(2):469–506, July 2017. doi:10.1007/s00220-017-2880-3.
[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, 2022. doi:10.1137/21M140729X.
[10] A. J. Coleman. Structure of fermion density matrices. Rev. Mod. Phys., 35:668–686, July 1963. doi:10.1103/RevModPhys.35.668.
[11] Bill Fefferman and Cedric Lin. Quantum Merlin Arthur with exponentially small gap, 2016. arXiv:1601.01975.
[12] Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). computational complexity, 31(2):13, September 2022. doi:10.1007/s00037-022-00231-8.
[13] Dima Grigoriev. Polynomial complexity of solving systems of few algebraic equations with small degrees. In Vladimir P. Gerdt, Wolfram Koepf, Ernst W. Mayr, and Evgenii V. Vorozhtsov, editors, Computer Algebra in Scientific Computing, pages 136–139, Cham, 2013. Springer International Publishing. doi:10.1007/978-3-319-02297-0_11.
[14] Dima Grigoriev and Dmitrii V. Pasechnik. Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Comput. Complex., 14(1):20–52, April 2005. doi:10.1007/s00037-005-0189-7.
[15] Alex B. Grilo, William Slofstra, and Henry Yuen. Perfect zero knowledge for quantum multiprover interactive proofs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 611–635, 2019. doi:10.1109/FOCS.2019.00044.
[16] Aram W. Harrow and Ashley Montanaro. Testing product states, quantum Merlin-Arthur games and tensor optimization. J. ACM, 60(1), February 2013. doi:10.1145/2432622.2432625.
[17] Fernando Granha Jeronimo and Pei Wu. The power of unentangled quantum proofs with non-negative amplitudes. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1629–1642, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585248.
[18] Jonas Kamminga and Dorian Rudolph. On the complexity of pure-state consistency of local density matrices, 2025. arXiv:2411.03096.
[19] 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.
[20] A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation. American Mathematical Society, May 2002. doi:10.1090/gsm/047.
[21] Alexander Klyachko. Quantum marginal problem and representations of the symmetric group, 2004. arXiv:quant-ph/0409113.
[22] Yi-Kai Liu. Consistency of local density matrices is QMA-complete. In Josep Díaz, Klaus Jansen, José D. P. Rolim, and Uri Zwick, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 438–449, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. doi:10.1007/11830924_40.
[23] Yi-Kai Liu, Matthias Christandl, and F. Verstraete. Quantum computational complexity of the $N$ -representability problem: QMA complete. Phys. Rev. Lett., 98:110503, March 2007. doi:10.1103/PhysRevLett.98.110503.
[24] Chris Marriott and John Watrous. Quantum Arthur–Merlin games. computational complexity, 14(2):122–152, June 2005. doi:10.1007/s00037-005-0194-x.
[25] David A Mazziotti. Pure-N-representability conditions of two-fermion reduced density matrices. Physical Review A, 94(3):032516, 2016.
[26] Attila Pereszlényi. Multi-prover quantum Merlin-Arthur proof systems with small gap, 2012. arXiv:1205.2761.
[27] James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part I: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of Symbolic Computation, 13(3):255–299, 1992. doi:10.1016/S0747-7171(10)80003-3.
[28] James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part II: The general decision problem. preliminaries for quantifier elimination. Journal of Symbolic Computation, 13(3):301–327, 1992. doi:10.1016/S0747-7171(10)80004-5.
[29] James Renegar. On the computational complexity of approximating solutions for real algebraic formulae. SIAM Journal on Computing, 21(6):1008–1025, 1992. doi:10.1137/0221060.
[30] Yaoyun Shi and Xiaodi Wu. Epsilon-net method for optimizations over separable states. Theoretical Computer Science, 598:51–63, 2015. doi:10.1016/j.tcs.2015.03.031.
[31] Tzu-Chieh Wei, Michele Mosca, and Ashwin Nayak. Interacting boson problems can be QMA hard. Phys. Rev. Lett., 104:040501, January 2010. doi:10.1103/PhysRevLett.104.040501.
[32] Xiao-Dong Yu, Timo Simnacher, Nikolai Wyderka, H. Chau Nguyen, and Otfried Gühne. A complete hierarchy for the pure state marginal problem in quantum mechanics. Nature Communications, 12(1):1012, February 2021. doi:10.1038/s41467-020-20799-5.

[bib.bib1] [1] Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. The power of unentanglement. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 223–236, 2008. doi:10.1109/CCC.2008.5.

[bib.bib2] [2] D. Aharonov and O. Regev. A lattice problem in quantum NP. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 210–219, 2003. doi:10.1109/SFCS.2003.1238195.

[bib.bib3] [3] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, April 2009. doi:10.1017/cbo9780511804090.

[bib.bib4] [4] Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, and Pei Wu. Quantum Merlin-Arthur with an internally separable proof, 2024. doi:10.48550/arXiv.2410.19152.

[bib.bib5] [5] Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. Quantum Merlin-Arthur and proofs without relative phase. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2024.9.

[bib.bib6] [6] Hugue Blier and Alain Tapp. A quantum characterization of NP. computational complexity, 21(3):499–510, September 2012. doi:10.1007/s00037-011-0016-2.

[bib.bib7] [7] Allan Borodin. On relating time and space to size and depth. SIAM Journal on Computing, 6(4):733–744, 1977. doi:10.1137/0206054.

[bib.bib8] [8] Fernando G. S. L. Brandão and Aram W. Harrow. Quantum de finetti theorems under local measurements with applications. Communications in Mathematical Physics, 353(2):469–506, July 2017. doi:10.1007/s00220-017-2880-3.

[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, 2022. doi:10.1137/21M140729X.

[bib.bib10] [10] A. J. Coleman. Structure of fermion density matrices. Rev. Mod. Phys., 35:668–686, July 1963. doi:10.1103/RevModPhys.35.668.

[bib.bib11] [11] Bill Fefferman and Cedric Lin. Quantum Merlin Arthur with exponentially small gap, 2016. arXiv:1601.01975.

[bib.bib12] [12] Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). computational complexity, 31(2):13, September 2022. doi:10.1007/s00037-022-00231-8.

[bib.bib13] [13] Dima Grigoriev. Polynomial complexity of solving systems of few algebraic equations with small degrees. In Vladimir P. Gerdt, Wolfram Koepf, Ernst W. Mayr, and Evgenii V. Vorozhtsov, editors, Computer Algebra in Scientific Computing, pages 136–139, Cham, 2013. Springer International Publishing. doi:10.1007/978-3-319-02297-0_11.

[bib.bib14] [14] Dima Grigoriev and Dmitrii V. Pasechnik. Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Comput. Complex., 14(1):20–52, April 2005. doi:10.1007/s00037-005-0189-7.

[bib.bib15] [15] Alex B. Grilo, William Slofstra, and Henry Yuen. Perfect zero knowledge for quantum multiprover interactive proofs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 611–635, 2019. doi:10.1109/FOCS.2019.00044.

[bib.bib16] [16] Aram W. Harrow and Ashley Montanaro. Testing product states, quantum Merlin-Arthur games and tensor optimization. J. ACM, 60(1), February 2013. doi:10.1145/2432622.2432625.

[bib.bib17] [17] Fernando Granha Jeronimo and Pei Wu. The power of unentangled quantum proofs with non-negative amplitudes. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1629–1642, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585248.

[bib.bib18] [18] Jonas Kamminga and Dorian Rudolph. On the complexity of pure-state consistency of local density matrices, 2025. arXiv:2411.03096.

[bib.bib19] [19] 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.bib20] [20] A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation. American Mathematical Society, May 2002. doi:10.1090/gsm/047.

[bib.bib21] [21] Alexander Klyachko. Quantum marginal problem and representations of the symmetric group, 2004. arXiv:quant-ph/0409113.

[bib.bib22] [22] Yi-Kai Liu. Consistency of local density matrices is QMA-complete. In Josep Díaz, Klaus Jansen, José D. P. Rolim, and Uri Zwick, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 438–449, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. doi:10.1007/11830924_40.

[bib.bib23] [23] Yi-Kai Liu, Matthias Christandl, and F. Verstraete. Quantum computational complexity of the $N$ -representability problem: QMA complete. Phys. Rev. Lett., 98:110503, March 2007. doi:10.1103/PhysRevLett.98.110503.

[bib.bib24] [24] Chris Marriott and John Watrous. Quantum Arthur–Merlin games. computational complexity, 14(2):122–152, June 2005. doi:10.1007/s00037-005-0194-x.

[bib.bib25] [25] David A Mazziotti. Pure-N-representability conditions of two-fermion reduced density matrices. Physical Review A, 94(3):032516, 2016.

[bib.bib26] [26] Attila Pereszlényi. Multi-prover quantum Merlin-Arthur proof systems with small gap, 2012. arXiv:1205.2761.

[bib.bib27] [27] James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part I: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of Symbolic Computation, 13(3):255–299, 1992. doi:10.1016/S0747-7171(10)80003-3.

[bib.bib28] [28] James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part II: The general decision problem. preliminaries for quantifier elimination. Journal of Symbolic Computation, 13(3):301–327, 1992. doi:10.1016/S0747-7171(10)80004-5.

[bib.bib29] [29] James Renegar. On the computational complexity of approximating solutions for real algebraic formulae. SIAM Journal on Computing, 21(6):1008–1025, 1992. doi:10.1137/0221060.

[bib.bib30] [30] Yaoyun Shi and Xiaodi Wu. Epsilon-net method for optimizations over separable states. Theoretical Computer Science, 598:51–63, 2015. doi:10.1016/j.tcs.2015.03.031.

[bib.bib31] [31] Tzu-Chieh Wei, Michele Mosca, and Ashwin Nayak. Interacting boson problems can be QMA hard. Phys. Rev. Lett., 104:040501, January 2010. doi:10.1103/PhysRevLett.104.040501.

[bib.bib32] [32] Xiao-Dong Yu, Timo Simnacher, Nikolai Wyderka, H. Chau Nguyen, and Otfried Gühne. A complete hierarchy for the pure state marginal problem in quantum mechanics. Nature Communications, 12(1):1012, February 2021. doi:10.1038/s41467-020-20799-5.

The Pure-State Consistency of Local Density Matrices Problem: In PSPACE and Complete for a Class Between QMA and QMA(2)

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

1.1 Our results

Definition 1.1 (k−𝖯𝗎𝗋𝖾𝖢𝖫𝖣𝖬, informal).

1.1.1 𝗣𝘂𝗿𝗲𝗖𝗟𝗗𝗠 is complete for 𝗣𝘂𝗿𝗲𝗦𝘂𝗽𝗲𝗿𝗤𝗠𝗔

Definition 1.2 (𝖯𝗎𝗋𝖾𝖲𝗎𝗉𝖾𝗋𝖰𝖬𝖠, informal).

Theorem 1.3.

Corollary 1.4.

1.1.2 𝗣𝘂𝗿𝗲𝗦𝘂𝗽𝗲𝗿𝗤𝗠𝗔 as a “light” version of 𝗤𝗠𝗔⁢(𝟐)

Proposition 1.5.

Proposition 1.6.

Proposition 1.7.

1.1.3 𝗣𝘂𝗿𝗲𝗦𝘂𝗽𝗲𝗿𝗤𝗠𝗔 is upper bounded by 𝗣𝗦𝗣𝗔𝗖𝗘

Theorem 1.8.

Corollary 1.9.

Corollary 1.10.

1.1.4 Solving systems of quadratic equations efficiently in parallel

Definition 1.11 (GP system (informal)).

Definition 1.12 (Nick’s Class [3]).

Theorem 1.13.

Definition 1.14 (OptGP).

Theorem 1.15.

1.2 Proof techniques

1.3 Related work

1.4 Discussion and open questions

Conjecture 1.16.

2 Preliminaries

Definition 2.1 (k−𝖯𝗎𝗋𝖾𝖢𝖫𝖣𝖬).

Example 2.2.

3 PureSuperQMA

Definition 3.1 (𝖯𝗎𝗋𝖾𝖲𝗎𝗉𝖾𝗋𝖰𝖬𝖠, c.f. [2]).

Lemma 3.2.

Proposition 1.5. [Restated, see original statement.]

Proof sketch.

Proposition 1.7. [Restated, see original statement.]

Corollary 3.3 ([6, 26]).

Definition 3.4 (𝖯𝖲𝖰𝖬𝖠).

Lemma 3.5.

4 2-PureCLDM is PureSuperQMA-complete

Proof sketch.

Definition 4.1 (s-simulatable code [9]999Our definition deviates from [9, Definition 4.1] in that it does not require transversal circuits for all gates. In fact the simulatable codes in [9] also use non-transversal gates for the T-gadgets given in [9, Section 4.3].).

Lemma 4.2 ([15, 9]).

Lemma 4.3 (Variant of [19, Lemma 5.1]).

Lemma 4.4 (Extraction Lemma).

Claim 4.5.

5 𝒌−𝗣𝘂𝗿𝗲𝗖𝗟𝗗𝗠 is in 𝗣𝗦𝗣𝗔𝗖𝗘

5.1 𝗣𝘂𝗿𝗲𝗦𝘂𝗽𝗲𝗿𝗤𝗠𝗔 as a polynomial system

Definition 5.1 (Grigoriev-Pasechnik system (GP system) [14]).

5.2 Reducing the number of variables

Theorem 5.2 ([14, Theorem 4.5]).

▶ Remark 5.3.

5.2.1 Removing the assumptions

Lemma 5.4 ([14, Lemma 5.2]).

Lemma 5.5 ([14, Lemma 5.3]).

Definition 5.6.

Theorem 5.7 ([14, Theorem 5.4]).

Lemma 5.8.

Proof.

5.3 Solving the smaller systems using algorithms for the first-order theory of the reals

Definition 5.9 (First-order theory of the reals).

Theorem 5.10 ([27, Theorem 1.1]).

Proof.

6 Approximation and Optimization

Theorem 1.15. [Restated, see original statement.]

6.1 Computing the minimum

Theorem 6.1 ([29, Theorem 1.2]).

6.2 Computing the solution vector

Theorem 6.2.

References

Definition 1.1 ( $k\mathchar 45\relax\mathsf{PureCLDM}$ , informal).

1.1.1 $\mathsf{PureCLDM}$ is complete for $\mathsf{PureSuperQMA}$

Definition 1.2 ( $\mathsf{PureSuperQMA}$ , informal).

1.1.2 $\mathsf{PureSuperQMA}$ as a “light” version of $\mathsf{QMA}(2)$

1.1.3 $\mathsf{PureSuperQMA}$ is upper bounded by $\mathsf{PSPACE}$

Definition 2.1 ( $k\mathchar 45\relax\mathsf{PureCLDM}$ ).

Definition 3.1 ( $\mathsf{PureSuperQMA}$ , c.f. [2]).

Definition 3.4 ( $\mathsf{PSQMA}$ ).

Definition 4.1 ( $s$ -simulatable code [9]⁹⁹9Our definition deviates from [9, Definition 4.1] in that it does not require transversal circuits for all gates. In fact the simulatable codes in [9] also use non-transversal gates for the $T$ -gadgets given in [9, Section 4.3].).

5 $k\mathchar 45\relax\mathsf{PureCLDM}$ is in $\mathsf{PSPACE}$

5.1 $\mathsf{PureSuperQMA}$ as a polynomial system

$\blacktriangleright$ Remark 5.3.