PDQMA = DQMA = NEXP: QMA with Hidden Variables and Non-Collapsing Measurements

Here we show a new example where non-collapsing measurements combined with one other resource yield extraordinary computational power – vastly more power than either resource in isolation.

The class $\mathrm{𝖰𝖬𝖠}$ (Quantum Merlin Arthur) is a well-known quantum generalization of $\mathrm{𝖭𝖯}$; it consists of all languages for which a “yes” answer can be verified in quantum polynomial time with the help of a polynomial-size quantum witness state. We define and study $\mathrm{𝖯𝖣𝖰𝖬𝖠}$ (Product Dynamical $\mathrm{𝖰𝖬𝖠}$), or $\mathrm{𝖰𝖬𝖠}$ augmented with non-collapsing measurements. Our main result is that $\mathrm{𝖯𝖣𝖰𝖬𝖠}=\mathrm{𝖭𝖤𝖷𝖯}$, even if $\mathrm{𝖯𝖣𝖰𝖬𝖠}$ is defined with a completeness/soundness gap of (say) $1-2^{-n}$ vs. $2^{-n}$ (Theorem 5).

Since the inclusion $\mathrm{𝖯𝖣𝖰𝖬𝖠}\subseteq \mathrm{𝖭𝖤𝖷𝖯}$ is straightforward, the interesting part is $\mathrm{𝖭𝖤𝖷𝖯}\subseteq \mathrm{𝖯𝖣𝖰𝖬𝖠}$. By the celebrated PCP theorem [14, 13], it suffices to show that a two-query PCP system (Definition 3) can be simulated by $\mathrm{𝖯𝖣𝖰𝖬𝖠}$. Our proof builds on Aaronson’s proof [6] that $\mathrm{𝖯𝖣𝖰𝖯}/\mathrm{𝗊𝗉𝗈𝗅𝗒}=\mathrm{𝖠𝖫𝖫}$, but with two key differences. First, to simulate a two-query PCP system, we need a witness state that can support at least two queries to an exponentially long truth table, rather than just one query. Second, we now need an analysis of soundness: why, for example, can the prover not cheat by sending a witness that causes the response to each query to depend on the other query? This problem seems particularly acute once we realize that we can no longer rely on the no-signaling principle of quantum mechanics when non-collapsing measurements are allowed. To address the first challenge, we extend Aaronson’s algorithm to support multiple queries to an exponentially long truth table. To address the second challenge, we show that one can use non-collapsing measurements to perform a low-degree test, ensuring that Merlin’s witness has the “error-correcting code” structure of an honest witness state.

Let us highlight our simulation of a classical PCP as additional motivation for our work. Specifically, simulating PCP systems is one of the few approaches to show that quantum Merlin-Arthur systems can solve $\mathrm{𝖭𝖤𝖷𝖯}$ (see e.g. [7, 22]). An important direction for future work is to adapt our simulation to quantum Merlin-Arthur systems that adhere to the laws of quantum mechanics (even if the verifier is allowed exponential time or to interact with the prover). We view any progress of this form as progress toward understanding more “reasonable” quantum Merlin-Arthur systems, such as $\mathrm{𝖰𝖬𝖠}(2)$.

We point out some implications of our result. First, combining with the Nondeterministic Time Hierarchy Theorem ($\mathrm{𝖭𝖯}\ne \mathrm{𝖭𝖤𝖷𝖯}$), we find that $\mathrm{𝖯𝖣𝖰𝖬𝖠}$ is unconditionally more powerful than $\mathrm{𝖭𝖯}$. Second, “scaling down by an exponential,” we find that when non-collapsing measurements are allowed, the problem of optimizing an acceptance probability over all $N$-dimensional quantum states jumps from easy (a principal eigenvector problem) to $\mathrm{𝖭𝖯}$-hard even to approximate.

Let us place our result in the context of previous work on generalizations of $\mathrm{𝖰𝖬𝖠}$. Aharonov and Regev [12] defined $\mathrm{𝖰𝖬𝖠}+$, a variant of $\mathrm{𝖰𝖬𝖠}$ where the verifier can directly obtain the probability a given two-outcome measurement will accept, and showed $\mathrm{𝖰𝖬𝖠}+=\mathrm{𝖰𝖬𝖠}$. More recently, Jeronimo and Wu [22] showed that ${\mathrm{𝖰𝖬𝖠}}^{+}(\mathrm{𝟤})=\mathrm{𝖭𝖤𝖷𝖯}$, where ${\mathrm{𝖰𝖬𝖠}}^{+}(\mathrm{𝟤})$ is $\mathrm{𝖰𝖬𝖠}$ with two unentangled proofs that have nonnegative real amplitudes. Bassirian, Fefferman, and Marwaha [16] improved this to show that ${\mathrm{𝖰𝖬𝖠}}^{+}=\mathrm{𝖭𝖤𝖷𝖯}$ – i.e., nonnegative amplitudes alone suffice for the jump to $\mathrm{𝖭𝖤𝖷𝖯}$. As of this writing, it remains a matter of avid speculation whether unentangled witnesses also suffice for the jump to $\mathrm{𝖭𝖤𝖷𝖯}$: that is, whether $\mathrm{𝖰𝖬𝖠}(\mathrm{𝟤})=\mathrm{𝖭𝖤𝖷𝖯}$. Of course, our result implies that it would suffice to simulate non-collapsing measurements using unentangled proofs – i.e., to show $\mathrm{𝖯𝖣𝖰𝖬𝖠}\subseteq \mathrm{𝖰𝖬𝖠}(\mathrm{𝟤})$.

One important observation about our $\mathrm{𝖯𝖣𝖰𝖬𝖠}$ protocol is that it only ever measures the witness state in the computational basis – and hence, one could say, never exploits quantum interference. So in particular, if we defined a complexity class $\mathrm{𝖯𝖣𝖬𝖠}$ (Product Dynamical Merlin-Arthur) in mathematical parallel to $\mathrm{𝖯𝖣𝖰𝖬𝖠}$, where the witness was a classical probability distribution $𝒟$, and one was allowed to sample from $𝒟$ with or without doing Bayesian updating to it, we would equally have $\mathrm{𝖯𝖣𝖬𝖠}=\mathrm{𝖭𝖤𝖷𝖯}$. The main difference here is simply that it seems hard to invent a story that motivates $\mathrm{𝖯𝖣𝖬𝖠}$.

In Section 4, we sharpen this point by defining and studying a class that we call $\mathrm{𝖣𝖰𝖬𝖠}$ (Dynamical $\mathrm{𝖰𝖬𝖠}$), or $\mathrm{𝖰𝖬𝖠}$ augmented by the ability to see the entire history of a hidden variable. In particular, the verifier can perform a $\mathrm{𝖣𝖰𝖯}$ (Dynamical Quantum Polynomial-Time) computation, a complexity class introduced by Aaronson to study hidden variable theories from a quantum computing perspective [4]. In short, $\mathrm{𝖣𝖰𝖯}$ captures computations where one evolves a state vector unitarily, but there is a deeper “hidden variable” in a definite state that evolves stochastically. At the end of the computation, the history of the hidden variable (i.e., the sequence of definite states it occupied at each step) can be viewed when making the final accept/reject decision. $\mathrm{𝖣𝖰𝖯}$ captures any hidden variable theory that satisfies a set of axioms (given in Section 4), including theories due to Dieks [19] and Schrödinger [26].

We show that $\mathrm{𝖣𝖰𝖬𝖠}=\mathrm{𝖭𝖤𝖷𝖯}$ (Theorem 16). Here the reasons really do depend on quantum mechanics. Specifically, they depend on the ability to “hide” crucial information in the phases of amplitudes, to prevent a hidden variable trajectory from remembering that information. If we tried to define the analogous class $\mathrm{𝖣𝖬𝖠}$ (Dynamical $\mathrm{𝖬𝖠}$), it would trivially coincide with $\mathrm{𝖬𝖠}$. Assuming $\mathrm{𝖬𝖠}=\mathrm{𝖭𝖯}$, as follows from a standard derandomization assumption, this has the amusing consequence that $\mathrm{𝖣𝖬𝖠}\ne \mathrm{𝖣𝖰𝖬𝖠}$ – that is, in the presence of both witness states and trajectory sampling, quantum can already be known to be stronger than classical. In the same section, we also observe that our techniques imply $\mathrm{𝖣𝖰𝖯}/\mathrm{𝗊𝗉𝗈𝗅𝗒}=\mathrm{𝖠𝖫𝖫}$ (Theorem 17), complementing Aaronson’s result that $\mathrm{𝖯𝖣𝖰𝖯}/\mathrm{𝗊𝗉𝗈𝗅𝗒}=\mathrm{𝖠𝖫𝖫}$ [6]. This result relies on quantum mechanics in the same way that our $\mathrm{𝖣𝖰𝖬𝖠}$ result does.

One might also wonder about other “fantasy” variants of $\mathrm{𝖰𝖬𝖠}$. In principle, any variant of $\mathrm{𝖡𝖰𝖯}$ can be combined with $\mathrm{𝖰𝖬𝖠}$ to yield a new complexity class. For example, consider a variant of $\mathrm{𝖡𝖰𝖯}$ that can clone states (i.e., perform the transformation $|\psi ⟩|0^n⟩\mapsto {|\psi ⟩}^{\otimes 2}$). It is easy to see that one can simulate $k$ non-collapsing measurements of a state by cloning the state $k$ times and then measuring each copy in the usual collapsing way. Hence, combining this $\mathrm{𝖡𝖰𝖯}$ variant with $\mathrm{𝖰𝖬𝖠}$ yields a complexity class equal to $\mathrm{𝖭𝖤𝖷𝖯}$ by our Theorem 5. Indeed, if one wants to alter Arthur’s powers without triggering a “Mentos and Coke” effect, they would need to find a $\mathrm{𝖡𝖰𝖯}$ variant that is only modestly more powerful, the way $\mathrm{𝖯𝖣𝖰𝖯}$ is.

We give a high-level overview of our proof that $\mathrm{𝖯𝖣𝖰𝖬𝖠}=\mathrm{𝖭𝖤𝖷𝖯}$ (Theorem 5). Informally, $\mathrm{𝖯𝖣𝖰𝖬𝖠}$ is like $\mathrm{𝖰𝖬𝖠}$ except the verifier can perform non-collapsing measurements in addition to the normal collapsing ones (see Definition 2 for a formal definition). The containment $\mathrm{𝖯𝖣𝖰𝖬𝖠}\subseteq \mathrm{𝖭𝖤𝖷𝖯}$ is straightforward because $\mathrm{𝖭𝖤𝖷𝖯}$ can guess the exponentially-long classical description of the $\mathrm{𝖯𝖣𝖰𝖬𝖠}$ witness and verify it in exponential time.

Thus, the challenge is proving $\mathrm{𝖭𝖤𝖷𝖯}\subseteq \mathrm{𝖯𝖣𝖰𝖬𝖠}$. We show this by simulating a two-query probabilistically checkable proof (PCP) system for $\mathrm{𝖭𝖤𝖷𝖯}$ (see Definition 3 and Theorem 4). In short, the celebrated PCP theorem [14, 13] tells us that languages in $\mathrm{𝖭𝖤𝖷𝖯}$ can be decided by a verifier that queries a PCP $\pi :{\{0,1\}}^n\to \mathrm{\Sigma }$ at two points of the verifier’s choosing, where $\mathrm{\Sigma }$ is a constant-sized alphabet. Hence, our result follows from simulating two queries to a $\pi$.

The honest witness is the same as in [6]:

where $p:{𝔽}_q^n\to {𝔽}_q$ is the unique degree-$n$ multilinear extension of the PCP $\pi :{\{0,1\}}^n\to \mathrm{\Sigma }$ and $q=O(n)$ is chosen to be sufficiently large. However, our setting differs from [6] in two key ways: (i) we must retrieve two values $\pi (w)$ and $\pi (w^{\prime })$ for our choice of $w$, $w^{\prime }$, rather than one, and (ii) the quantum witness can no longer be trusted (as it can be in the advice setting).

To explain how to handle the first difference, let us briefly recall how to simulate a single query. As discussed, given a point of interest $w\in {\{0,1\}}^n$, on which one wants to evaluate $\pi (w)$, Aaronson [6] measures $|\psi ⟩$ so as to collapse it to an equal superposition

over a random line $\mathrm{\ell }\subset {𝔽}_q^n$ that passes through $w$, minus the point $w$ itself. To recover two values $w,w^{\prime }\in {\{0,1\}}^n$, one can generalize Aaronson’s procedure so that the measurement on $|\psi ⟩$ collapses it to an equal superposition over an affine plane that contains the points $w$ and $w^{\prime }$, minus the unique affine line containing $w$ and $w^{\prime }$. (Indeed, this can be generalized to any $k$-dimensional affine subspace, where the measurement collapses $|\psi ⟩$ to a superposition over a random $k$-dimensional affine subspace containing points $w_1,\mathrm{\dots },w_k$ minus the unique $(k-1)$-dimensional affine subspace containing $w_1,\mathrm{\dots },w_k$.) Then, just as in [6], one performs enough non-collapsing measurements to recover $\pi (w)$ and $\pi (w^{\prime })$ via polynomial interpolation.

The only remaining issue is that Merlin can potentially cheat and send a quantum state that is far from the honest witness. To address this, we use the lines-point low-degree test (Lemma 1) given by Friedl and Sudan [20]. Recall that an affine line $\mathrm{\ell }\subset {𝔽}_q^n$ passing through points $x,y\in {𝔽}_q^n$ is the set ${\{x+(y-x)t\}}_{t\in {𝔽}_q^n}$, so a function $g:\mathrm{\ell }\to {𝔽}_q$ can be viewed as a univariate polynomial in $t$. The lines-point low-degree test says that if a function $f:{𝔽}_q^n\to {𝔽}_q$ restricted to a randomly chosen line agrees with a degree-$n$ univariate polynomial, then $f$ agrees with some degree-$n$ polynomial $h:{𝔽}_q^n\to {𝔽}_q$ on all of ${𝔽}_q^n$.

Observe that to perform this low-degree test, we need to make sure the function that Merlin encodes into his witness agrees with a low-degree polynomial on a randomly chosen affine line. Therefore, rather than interpolating a polynomial on a random affine plane containing the points $w$ and $w^{\prime }$ of interest, our verification procedure interpolates a polynomial on an affine cube. This affine cube contains the points $w,w^{\prime }\in {\{0,1\}}^n$ but we also ensure that it contains a point $w^{\prime \prime }\in {𝔽}_q^n$ that the verifier chooses uniformly at random. This ensures that the affine cube contains a uniformly random line independent of the points $w$ and $w^{\prime }$. Then, if the polynomial interpolation succeeds, we can (i) recover $\pi (w)$ and $\pi (w^{\prime })$ as desired and (ii) conclude that Merlin’s witness encoded a low-degree polynomial because it passed the lines-point low degree test (i.e., it agreed with a low-degree polynomial on a randomly chosen line).

To summarize, the procedure works as follows. First, Merlin commits to some witness state $|\psi ⟩$. Then the $\mathrm{𝖯𝖣𝖰𝖬𝖠}$ verifier simulates the $\mathrm{𝖯𝖢𝖯}$ verifier to obtain queries $w,w^{\prime }\in {\{0,1\}}^n$ and picks a uniformly random $w^{\prime \prime }\in {𝔽}_q^n$. The verifier measures Merlin’s witness state $|\psi ⟩$ to collapse it to a superposition over points in a random affine cube containing $w,w^{\prime }$, and $w^{\prime \prime }$ minus the affine plane containing $w$, $w^{\prime }$, and $w^{\prime \prime }$. Then the verifier uses non-collapsing measurements to collect all $(z,p(z))$ pairs in the affine cube (minus the affine plane) and interpolates a polynomial $u:{𝔽}_q^3\to {𝔽}_q$ that fits these pairs. If the polynomial interpolation succeeds, Merlin passes the lines-point low-degree test and the verifier can learn $\pi (w)$ and $\pi (w^{\prime })$ by evaluating the polynomial $u$.

In concurrent and independent work, Bassirian and Marwaha [17] show that $\mathrm{𝖰𝖬𝖠}$ with non-collapsing measurements equals $\mathrm{𝖭𝖤𝖷𝖯}$. They observe that the proof of ${\mathrm{𝖰𝖬𝖠}}^{+}=\mathrm{𝖭𝖤𝖷𝖯}$ [16] goes through even if one replaces the promise of a non-negative witness state with the ability for the verifier to perform non-collapsing measurements. [16] can prove a containment (for a constant completeness/soundness gap) using a constant number of non-collapsing measurements, whereas our verification procedure always uses $O(n\log n)$ non-collapsing measurements. Our approach readily extends to prove $\mathrm{𝖣𝖰𝖬𝖠}=\mathrm{𝖭𝖤𝖷𝖯}$ and $\mathrm{𝖣𝖰𝖯}/\mathrm{𝗊𝗉𝗈𝗅𝗒}=\mathrm{𝖠𝖫𝖫}$.

We give a formal definition of $\mathrm{𝖣𝖰𝖬𝖠}$. To do so, we must recall a few definitions related to the class $\mathrm{𝖣𝖰𝖯}$ (see [4] for more detail about this class).

We begin by defining hidden-variable theories. To aid intuition, one can think of hidden-variable theories like standard quantum mechanics where there is a state vector that evolves unitarily. However, there is also a deeper “hidden variable” in some definite state (i.e., not in superposition) that evolves stochastically in a manner determined by the state vector and the state vector’s unitary evolution. In the series of definitions that follow, we are building up to defining a model of computation where one evolves a state vector unitarily, and then (at the end of the computation) can inspect which states the hidden variable was in at each step of the computation.

That is, we take a hidden-variable theory to be a function that maps the unitary evolution of a state to a stochastic matrix that evolves one probability distribution to another. Conditioned on a hidden variable being in a state $|j⟩$, ${(S)}_{ij}$ is the probability that a hidden variable transitions to the $|j⟩$.

Aaronson [4] defined a number of axioms a hidden-variable theory could satisfy. We require three of these axioms to define $\mathrm{𝖣𝖰𝖯}$: the marginalization axiom, the indifference axiom, and the robustness axiom. In the following definitions, $S$ denotes the hidden-variable theory, $\rho$ a $d$-dimensional quantum state, and $U$ a $d\times d$ unitary matrix. Each axiom must hold for all $d\in \mathbb{N}$.

In words, the marginalization axiom says that the hidden-variable theory should make predictions that are consistent with quantum mechanics.

Physically, the indifference axiom says the following. Given any quantum state $\rho$ in a tensor product space ${\mathscr{H}}_A\otimes {\mathscr{H}}_B$ and any unitary $U$ acting nontrivially only on ${\mathscr{H}}_A$, the stochastic matrix $S(\rho ,U)$ acts nontrivially only on ${\mathscr{H}}_A$ as well.

Finally, we state the robustness axiom, for which we need the following notation. Let $P(\rho ,U)$ be the matrix of joint probabilities whose $(i,j)$ entry is ${(P)}_{ij}≔{(S)}_{ij}{(\rho )}_{ii}$.

The robustness axiom is necessary to prove that the class $\mathrm{𝖣𝖰𝖯}$ is not sensitive to the choice of gate set defining the class.

Next, we define the history of a hidden variable.

We can now define the complexity class $\mathrm{𝖣𝖰𝖬𝖠}$.

We conclude this section by proving $\mathrm{𝖣𝖰𝖬𝖠}=\mathrm{𝖭𝖤𝖷𝖯}$ and $\mathrm{𝖣𝖰𝖯}/\mathrm{𝗊𝗉𝗈𝗅𝗒}=\mathrm{𝖠𝖫𝖫}$. Recall that in the proof of $\mathrm{𝖯𝖣𝖰𝖬𝖠}=\mathrm{𝖭𝖤𝖷𝖯}$ (Theorem 5), the verifier uses non-collapsing measurements to sample $O(n\log n)$ values of a multivariate polynomial along an affine line of one’s choice and then does interpolation. To prove $\mathrm{𝖣𝖰𝖬𝖠}=\mathrm{𝖭𝖤𝖷𝖯}$, we use the same verification procedure, except we use the history of a hidden variable to collect the samples in place of non-collapsing measurements. Hence, to prove $\mathrm{𝖣𝖰𝖬𝖠}=\mathrm{𝖭𝖤𝖷𝖯}$ it suffices to explain how we collect these samples with the history of a hidden variable. We achieve this by generalizing the “juggle subroutine” due to Aaronson [4, Section VII].

We generalize this algorithm to work on states that are an equal superposition over polynomially many strings by reducing to the case of an equal superposition over two strings. Before explaining the generalization, we first must define (and give a simple fact about) pairwise independent families of hash functions, which are used in our reduction.