Two-message quantum interactive proofs are in PSPACE

Introduction

Since their introduction roughly 25 years ago [Bab85, GMR85], interactive proof systems have become a fundamental notion in the theory of computational complexity. The expressive power of one of the most basic variant of the interactive proof system model, wherein a polynomial-time probabilistic verifier interacts with a computationally unbounded prover for a polynomial number of rounds, is characterized [LFKN92, Sha92] by the well-known relationship

Many variants of interactive proof systems have been studied, including public-coin interactive proof systems (or Arthur–Merlin games) [Bab85, BM88, GS89], zero-knowledge interactive proofs [GMR89, GMW91] and multi-prover interactive proofs [BOGKW88].

This paper is concerned primarily with quantum interactive proof systems, which are defined in a similar way to ordinary interactive proof systems except that the prover and verifier may perform quantum computations. Like their classical analogues, several variants of quantum interactive proof systems have been studied, including ordinary quantum interactive proofs [Wat03, KW00], public-coin quantum interactive proofs [MW05], zero-knowledge quantum interactive proofs [Wat02, Wat06, Kob08, HKSZ08], and multi-prover quantum interactive proofs [KM03, KKMV08]. The complexity class QIP of problems having quantum interactive proof systems is known [KW00] to satisfy

The containment $\textup{QIP}\subseteq\textup{EXP}$ follows from the existence of polynomial-time algorithms for approximately solving semidefinite programs [GLS93]. (Somewhat simpler proofs of the containment $\textup{QIP}\subseteq\textup{EXP}$ follow from the results of [BATS09, Wat09b], but these proofs still require efficient algorithms for solving convex/semidefinite programs.)

Quantum interactive proof systems have an interesting property that classical interactive proof systems are conjectured not to hold, which is that they can be parallelized to a constant number of rounds of interaction [KW00]. More precisely, it holds that $\textup{QIP}(3)=\textup{QIP}$, where in general $\textup{QIP}(m)$ denotes the class of problems having quantum interactive proof systems in which $m$ messages are exchanged between the prover and verifier (with the prover always sending the last message). This leaves four basic classes that are defined naturally by quantum interactive proof systems: $\textup{QIP}(0)=\textup{BQP}$, $\textup{QIP}(1)=\textup{QMA}$, $\textup{QIP}(2)$, and $\textup{QIP}(3)=\textup{QIP}$. Of these classes, $\textup{QIP}(2)$ seems to be the most mysterious. It is known that $\oplus\textup{MIP}^{\ast}\subseteq\textup{QIP}(2)$ [Weh06] and $\textup{QSZK}\subseteq\textup{QIP}(2)$ [Wat02, Wat06]. Here, $\oplus\textup{MIP}^{\ast}$ denotes the class of problems having one-round two-prover classical interactive proof systems in which the provers share quantum entanglement, answer one bit each, and the verifier accepts or rejects based on the parity of these bits; and QSZK denotes the class of problems having statistical zero-knowledge quantum interactive proof systems. No upper bound other than the trivial containment $\textup{QIP}(2)\subseteq\textup{QIP}$, which implies $\textup{QIP}(2)\subseteq\textup{EXP}$, was previously known.

In this paper we prove the new containment:

Similar to $\textup{QIP}\subseteq\textup{EXP}$, this containment is proved using semidefinite programming; but this time the containment is achieved by using an NC algorithm rather than a sequential polynomial-time algorithm. Our algorithm is based on the multiplicative weights update method, which was developed by several researchers and is described in the survey [AHK05] and in the PhD thesis of Kale [Kal07]. In particular, our algorithm is based on a general method that was independently discovered by Arora and Kale [AK07] and Warmuth and Kuzmin [WK06]. The key aspect of this approach that makes it useful for proving $\textup{QIP}(2)\subseteq\textup{PSPACE}$ is its parallelizability: it is an iterative method in which each iteration is easily parallelized, and is such that only a very small number of iterations is needed for an approximation that is accurate enough for our needs. A related approach was used by two of us [JW09] to prove the containment of a different quantum complexity class (called $\textup{QRG}(1)$) in PSPACE, but the specific technical details of the simulations are rather different.

The rest of this paper has the following structure. We begin with Section 2, which includes a brief discussion of background information needed for the rest of the paper, including linear algebra notation and parallel algorithms for matrix computations. Section 3 introduces two-message quantum interactive proof systems and establishes a simple fact concerning their robustness with respect to error bounds. In Section 4 we present a semidefinite programming formulation of the maximum probability with which a verifier in a two-message quantum interactive proof system can be made to accept, and the actual simulation of $\textup{QIP}(2)$ in PSPACE is split into the three sections that follow: Section 5 presents an overview of the simulation, while Sections 6 and 7 describe in more detail its two most technical parts. The precision requirements of the entire simulation are discussed in Section 8, and the paper concludes with Section 9.

Preliminaries

The following special types of operators are relevant to the paper:

Three operator norms are discussed in this paper: the trace norm, Frobenius norm, and spectral norm, defined as

for positive semidefinite operators $P$ and $Q$ of equal dimension.

The following special types of super-operators are relevant to the paper.

2 Remarks on NC and parallel matrix computations

To prove that $\textup{QIP}(2)$ is contained in PSPACE, we will make use of various facts concerning parallel computation. First, let us recall the definition of two complexity classes based on bounded-depth circuit families: NC and $\textup{NC}(\mathit{poly})$. The class NC contains all functions that can be computed by logarithmic-space uniform Boolean circuits of polylogarthmic depth, while the class $\textup{NC}(\mathit{poly})$ contains all functions that can be computed by polynomial-space uniform families of Boolean circuits having polynomial-depth. By restricting these classes to predicates we obtain classes of languages (or more generally promise problems).

There are a few facts about these classes that we will need. The first fact, which follows from [Bor77], is that for languages (or promise problems) we have $\textup{NC}(\mathit{poly})\subseteq\textup{PSPACE}$. (In fact it holds that $\textup{NC}(\mathit{poly})=\textup{PSPACE}$, but we only need a containment in one direction.) The second fact is that functions in these classes compose nicely. In particular, if $F:\{0,1\}^{\ast}\rightarrow\{0,1\}^{\ast}$ is a function in $\textup{NC}(\mathit{poly})$ and $G:\{0,1\}^{\ast}\rightarrow\{0,1\}^{\ast}$ is a function in NC, then the composition $G\circ F$ is also in $\textup{NC}(\mathit{poly})$. This follows from the most obvious way of composing the families of circuits that compute $F$ and $G$, along with the observation that $\left\lvert\mspace{1.0mu}F(x)\mspace{1.0mu}\right\rvert$ can be at most exponential in $\left\lvert\mspace{1.0mu}x\mspace{1.0mu}\right\rvert$.

Finally, we will make use of the fact that many computations involving matrices can be performed by NC algorithms. We will restrict our attention to matrix computations on matrices whose entries have rational real and imaginary parts. Numbers of this form, $\alpha=(a/b)+i(c/d)$ for integers $a$, $b$, $c$, and $d$, are sometimes referred to as Gaussian rationals. We assume any number of this form is encoded as a 4-tuple $(a,b,c,d)$ using binary notation, so that the length of $\alpha$ is understood to be the total number of bits needed for such an encoding.

It is known that elementary matrix operations, such as additions, multiplications, and inversions, can be performed in NC. (The survey [Gat93], for instance, describes NC algorithms for these tasks.) We will also make use of the fact that matrix exponentials and spectral decompositions can be approximated to high precision in NC. In more precise terms, we have that the following problems are in NC:

Note that in these problems, the description of $\varepsilon$ has roughly $\log(1/\varepsilon)$ bits, which means that highly accurate approximations are possible in NC. The fact that matrix exponentials can be approximated in NC as claimed follows by truncating the series

to a number of terms polynomial in $k$ and $\log(1/\varepsilon)$. (This is not a very practial way to compute matrix exponentials, but it establishes the fact we need.) The fact that spectral and singular value decompositions can be approximated in NC follows from a composition of known facts: in NC one can compute characteristic polynomials and null spaces of matrices, perform orthogonalizations of vectors, and approximate roots of integer polynomials to high precision [Csa76, BGH82, BCP83, BOFKT86, Gat93, Nef94].

Two-message quantum interactive proof systems

The purpose of this section is to introduce the class $\textup{QIP}(2)$, including its definition and a simple proof that it is robust with respect to error bounds. For a general discussion of quantum interactive proof systems, as opposed to the somewhat simplified case in which only two messages are exchanged, the reader is referred to [KW00] and [Wat09a].

To define the class $\textup{QIP}(2)$, we begin by defining a two-message quantum verifier $V$ as a classical polynomial-time algorithm that, on each input string $x$, outputs the description of two quantum circuits: $U_{x}$ and $V_{x}$. The circuit $U_{x}$ describes the verifier’s initial preparation of a state, part of which is sent to the prover, while the circuit $V_{x}$ describes the verifier’s actions upon receiving a response from the prover. For the sake of simplicity, and without loss of generality, we assume that for every input string $x$, the circuits $U_{x}$ and $V_{x}$ are both composed of gates from some finite, universal set of unitary quantum gates whose entries have rational real and imaginary parts. The number of qubits on which the circuits $U_{x}$ and $V_{x}$ act is assumed to be equal to $2p(n)$, where $n=\left\lvert\mspace{1.0mu}x\mspace{1.0mu}\right\rvert$ and $p$ is some polynomial-bounded function. The first $p(n)$ qubits represent the communication channel between the prover and verifier, while the remaining $p(n)$ qubits serve as the private memory of the verifier. (It is not really necessary that the number of message qubits and private memory qubits agree, but it causes no change in the computational power of the model.)

A two-message quantum prover $P$ is simply a collection of quantum operations (or, equivalently, completely positive and trace preserving super-operators) $\{\Psi_{x}\,:\,x\in\{0,1\}^{\ast}\}$. Such a prover is compatible with a given verifier $V$ if each operation $\Psi_{x}$ acts on $p(n)$ qubits for the function $p$ mentioned above.

An interaction between a two-message verifier $V$ and a compatible prover $P$ on an input $x$ proceeds as follows:

$2p(n)$ qubits are initialized in the $\ket{0}$ state.

The circuit $U_{x}$ is applied to all of the qubits.

The prover’s operation $\Psi_{x}$ is applied to the first $p(n)$ qubits.

The circuit $V_{x}$ is applied to all of the qubits.

The first qubit is measured with respect to the standard basis, with the outcome 1 indicating acceptance and 0 indicating rejection.

Figure 1 illustrates such an interaction.

Now, a promise problem $A=(A_{\text{yes}},A_{\text{no}})$ is in $\textup{QIP}(2)$ if and only if there exists a two-message verifier $V$ with the following completeness and soundness properties:

(Completeness) If $x\in A_{\text{yes}}$, then there exists a prover $P$ that causes $V$ to accept $x$ with probability at least 2/3.

(Soundness) If $x\in A_{\text{no}}$, then every prover $P$ that is compatible with $V$ causes $V$ to accept $x$ with probability at most 1/3.

2 Robustness of QIP(2) with respect to error bounds

It was proved in [KW00] that quantum interactive proof systems with negligible completeness error are amenable to parallel repetition. This allows for an exponential reduction in error for quantum interactive proof systems with three or more messages, because such proof systems can be transformed to have perfect completeness by a different method. However, this method does not work for two-message quantum interactive proof systems, because the perfect-completeness transformation requires the addition of messages. So, we will require a different method of error reduction.

Assume that $A$ is a promise problem in $\textup{QIP}(2)$ and that $(V,P)$ is a two-message quantum interactive proof system for $A$ with completeness and soundness probabilities bounded by $a$ and $b$, where $a-b\geq 1/q$ for some polynomial-bounded function $q$. We will define a new verifier $V^{\prime}$ that has completeness probability at least $1-2^{-r}$ and soundness probability at most $2^{-r}$, for any choice of a polynomial-bounded function $r$. A description of $V^{\prime}$ follows.

Let $s=2rq$ and let $t=8rq^{2}s$. Run $st$ independent, parallel executions of the protocol for $V$, one for each pair $(i,j)$ with $i\in\{1,\ldots,s\}$ and $j\in\{1,\ldots,t\}$. Measure the output qubit for each execution, and let the result of the measurement for execution $(i,j)$ be $y_{i,j}\in\{0,1\}$.

Accept if $\bigwedge_{i=1}^{s}z_{i}=1$, reject otherwise.

and thus the probability of rejection is at most $se^{-rs}<2^{-r}$.

We may view $z_{1},\ldots,z_{s}$ as being the outcomes of $s$ parallel executions of a quantum interactive proof system that accepts with probability at most $1-\frac{1}{2q}$. The verifier $V^{\prime}$ accepts if and only if all of these executions accept, and so by the result on parallel repetition proved in [KW00] we may conclude that the probability of acceptance of $V^{\prime}$ is at most

Thus, the verifier $V^{\prime}$ has been shown to have completeness and soundness probabilities as required, completing the proof.

Maximum acceptance probability as a semidefinite program

The maximum acceptance probability of a verifier in a quantum interactive proof system can be phrased as semidefinite programming problem [KW00]. For this paper a semidefinite programming formulation based on ones described in [GW07, Wat09b] will be used.

Suppose $V$ is a two-message verifier, and that an input string $x$ of length $n$ is being considered. Let us also define

In words, $\ket{\psi}$ denotes the quantum state initially prepared by the verifier, the first half of which is sent to the prover; and $\Pi$ denotes the projection operator corresponding to the accept outcome of the measurement that the verifier effectively performs after receiving the prover’s message.

We therefore find that the probability of acceptance (1) may alternately be written

The feasible region of this semidefinite program is well-bounded (in the sense of [GLS93]), and therefore its optimal value $\mu(Q)$ can be approximated to high precision in time polynomial in the size of $Q$ (which is exponential in $\left\lvert\mspace{1.0mu}x\mspace{1.0mu}\right\rvert$). This fact does not help us to prove $\textup{QIP}(2)\subseteq\textup{PSPACE}$, however. As is described in the next section, we will need an NC algorithm rather than just a polynomial-time algorithm to draw this conclusion.

The value $\mu(Q)$ is then seen to be the optimal value of the following semidefinite program:

Strong duality follows from strict feasibility, which is easily verified, and so the optimal primal and dual solutions are given by $\mu(Q)$.

Overview of the simulation

We will now explain, in high-level terms, our simulation of $\textup{QIP}(2)$ in PSPACE. To prove that $\textup{QIP}(2)\subseteq\textup{PSPACE}$, it will suffice to prove $\textup{QIP}(2)\subseteq\textup{NC}(\mathit{poly})$. This will be facilitated by the fact, discussed in Section 2.2, that many computations involving matrices, including elementary operations such as addition, multiplication, and inversion, as well as approximations of spectral decompositions, singular-value decompositions, and matrix exponentials, can be performed in NC.

For the remainder of this paper, assume that $A=(A_{\text{yes}},A_{\text{no}})$ is an arbitrary promise problem in $\textup{QIP}(2)$, and let $V$ be a two-message verifier for $A$ that has exponentially small completeness and soundness error. The goal of the simulation is to determine whether or not $V$ can be made to accept a given input string $x$ with high probability. The variable $n$ will always denote the input length $n=\left\lvert\mspace{1.0mu}x\mspace{1.0mu}\right\rvert$, and $p(n)$ will denote the number of qubits exchanged by the verifier and prover on each of the two messages as discussed in Section 3.

There are three main steps of the simulation:

Compute from $x$ an explicit description of $\ket{\psi}$ and $\Pi$.

Process the description of the vector $\ket{\psi}$ and the projection $\Pi$ into a well-conditioned interactive measurement operator $Q$ and positive rational numbers $\gamma$ and $\varepsilon$ satisfying

For some polynomial $q$ it will hold that $\kappa(Q)\leq q(n)$, where $\kappa(Q)=\left\lVert\mspace{1.0mu}Q\mspace{1.0mu}\right\rVert\lVert\mspace{1.0mu}Q^{-1}\mspace{1.0mu}\rVert$ denotes the condition number of $Q$. Moreover it will hold that $1/q(n)\leq\varepsilon$ and $1/q(n)\leq\gamma$.

Use a parallel algorithm, based on the multiplicative weights update method, to test whether $\mu(Q)$ is larger or smaller than $\gamma$.

The first step is easily performed in $\textup{NC}(\mathit{poly})$, using an exact computation. In particular, one may simply compute products of the matrices that describe the individual gates of the verifier’s circuits. Given that this step is straightforward, we will not comment on it further. The second and third steps are more complicated, and are described separately in Sections 6 and 7 below. Both correspond to NC computations (where the input size is exponential in $n$), and by composing these computations with the first step just described, we will obtain that $A$ is in $\textup{NC}(\mathit{poly})$, and therefore $\textup{QIP}(2)\subseteq\textup{PSPACE}$.

Preparing a well-conditioned interactive measurement operator

The quantity $\mu(R)$ is precisely the maximum acceptance probability of $V$ on input $x$, but nothing can be said about the condition number of $R$ (which may not even be invertible).

The interactive measurement operator $Q$ is well-conditioned: $\kappa(Q)\leq q(n)$.

The values $\gamma$ and $\varepsilon$ are non-negligible: $1/q(n)\leq\varepsilon$ and $1/q(n)\leq\gamma$.

The value $\mu(Q)$ satisfies the properties

The first step in this process is to replace $\ket{\psi}$ by a more uniform vector $\ket{\phi}\in\mathcal{X}_{0}\otimes\mathcal{Z}_{0}$ that is “similar enough” to $\ket{\psi}$ in the sense to be described. We will, in particular, take $\ket{\phi}$ to be maximally entangled over certain subspaces of $\mathcal{X}_{0}$ and $\mathcal{Z}_{0}$. This is done by performing the following operations:

be a Schmidt decomposition of $\ket{\psi}$.

For each positive integer $i$, define the interval $I_{i}=\left(2^{-i},2^{-i+1}\right]$, and define

Let $k=p(n)+1$ and choose $i\in\{1,\ldots,k\}$ so that

The fact that such an $i$ exists is proved below, and hereafter we write $\Sigma=\Sigma_{i}$ for this choice of $i$.

These are fairly loose bounds—but for the two extremes where $\mu(R)$ is exponentially close to 0 or 1, the corresponding values for $\mu(S)$ will be separated by the reciprocal of a polynomial, which is good enough for our needs.

Thus, there must exist a suitable choice of $i$ in step 3 so that

as claimed. A lower bound on the size of $\Sigma=\Sigma_{i}$ may be obtained by noting that

Now, the inner product of $\ket{\psi}$ and $\ket{\phi}$ is easily bounded from below as

and by combining this observation with the fact that $\ket{\psi}\!\bra{\psi}-\ket{\phi}\!\bra{\phi}$ is traceless we obtain

which establishes the lower bound on $\mu(S)$ claimed in (3) above.

To establish the upper bound on $\mu(S)$, which is the second inequality in (3), let us first choose an admissible super-operator $\Psi$ so that

Because $\Psi$ is admissible, we may therefore conclude that

Having obtained a uniform vector $\ket{\phi}$ that gives (when combined with $\Pi$) an interactive measurement operator $S$ satisfying (3), we must make a couple of additional modifications to be sure that a well-conditioned interactive measurement operator has been obtained.

Now let us verify that $Q$ has the properties we require of it. First let us consider the condition number $\kappa(Q)$. It is easily shown that

and therefore $\kappa(Q)\leq 64k$. It remains to define nonnegligible values $\gamma$ and $\varepsilon$, and to consider their relationship to $\mu(Q)$ in the two cases: $x\in A_{\text{yes}}$ and $x\in A_{\text{no}}$.

We have assumed that the original interactive proof system has exponentially small completeness and soundness errors, and therefore we may assume that for sufficiently large $n$ we have

(Alternately we may assume these bounds hold for all $n$ by hard-coding small inputs $x$ into the verifier.) Thus, by the bounds (4) above, we have

we therefore have the properties required.

Verifying maximum acceptance probability

We now describe and analyze a parallel algorithm, based on the multiplicative weights update method, to distinguish the two cases (2) from the previous section. The algorithm operates as described in Figure 2, and the super-operators $\Phi$ and $\Phi^{\ast}$ are as defined in Section 4.

We will need a few basic facts and three lemmas to analyze the algorithm described in Figure 2. We begin by noting two facts concerning matrix exponentials. First, the Golden-Thompson Inequality (see Section IX.3 of [Bha97]) states that, for any two Hermitian matrices $X$ and $Y$ of equal dimension, we have

Second is the following inequality concerning the matrix exponential of positive semidefinite matrices.

It is sufficient to prove the inequality for $P$ replaced by a scalar $\lambda\in$, for then the operator inequality follows by considering a spectral decomposition of $P$. If $\lambda=0$ then the inequality is trivial, so assume $\lambda>0$. By the Mean Value Theorem there exists a value $\lambda_{0}\in(0,\lambda)$ such that

by taking $\operatorname{vec}(\ket{i}\bra{j})=\ket{i}\ket{j}$ for each choice of $i\in\{0,\ldots,M-1\}$ and $j\in\{0,\ldots,N-1\}$.

By the monotonicity of the fidelity function, it must hold that $\operatorname{F}(R_{0},R_{1})\leq\operatorname{F}(P_{0},P_{1})$ for every choice of $R_{1}$ satisfying $\operatorname{Tr}_{\mathcal{Y}}(R_{1})=P_{1}$. It therefore suffices to show that equality can be achieved.

Lemma 7.2 is a fairly straightforward extension of Uhlmann’s Theorem [Uhl76]. (See also pages 410–411 of [NC00].)

purify $R_{0}$ and $R_{1}$, respectively, so by the monotonicity of the trace norm it holds that

which follows easily from the expressions of the trace and Frobenius norms in terms of singular values, along with the Cauchy–Schwarz inequality, we have

When $R_{0}=\rho_{0}$ and $R_{1}=\rho_{1}$ for density operators $\rho_{0}$ and $\rho_{1}$, we obtain the familiar inequality

which is one of the Fuchs-van de Graaf inequalities [FvdG99].

2 Analysis of the algorithm (ignoring precision)

Our algorithm cannot be implemented exactly using bounded-depth Boolean circuits: the spectral decompositions and matrix exponentials can only be approximated. However, for the sake of exposition, the issue of precision will be completely ignored in this subsection; meaning that we will imagine that all of the operations can be performed exactly. In the section that follows this one, the actual precision requirements of the algorithm are considered. As is shown there, it turns out that the algorithm is not particularly sensitive to errors, and in fact it is possible to perform all of the required computations in parallel with exponentially greater precision than would be required for the correctness of the algorithm.

The operator $X$ is defined as follows. First, let $R_{0}=Q^{-1/2}\rho Q^{-1/2}$, let $P_{0}=\operatorname{Tr}_{\mathcal{Y}}(R_{0})=\Phi(\rho)$, and let

It holds that $\operatorname{Tr}(P_{1})\leq\operatorname{Tr}(P_{0})$, and we also have

Therefore, given that $\operatorname{Tr}(P_{0})\leq\lVert\mspace{1.0mu}Q^{-1}\mspace{1.0mu}\rVert$, we have $\left\lVert\mspace{1.0mu}R_{0}-R_{1}\mspace{1.0mu}\right\rVert_{1}\leq\sqrt{8\delta}\lVert\mspace{1.0mu}Q^{-1}\mspace{1.0mu}\rVert$, and so

Second, given that $s>\delta\lVert\mspace{1.0mu}Q^{-1}\mspace{1.0mu}\rVert$ for the case at hand, we have

and therefore $\left\lVert\mspace{1.0mu}\delta\Phi^{\ast}(Y_{t})\mspace{1.0mu}\right\rVert<1$.

Now, for the sake of clarity, let us write $\eta=\varepsilon\gamma/2$. Note that, for $0\leq t\leq T-1$, it holds that

where we have used the Golden–Thompson Inequality. Given that $\left\lVert\mspace{1.0mu}\delta\Phi^{\ast}(Y_{t})\mspace{1.0mu}\right\rVert\leq 1$ we have by Lemma 7.1 that

(Here we have used the inequality $\exp(-\alpha)\geq 1-\alpha$, which holds for all real numbers $\alpha$, as well as the fact that $\operatorname{Tr}(AB)\leq\operatorname{Tr}(AC)$ whenever $A\geq 0$ and $B\leq C$). Repeating this argument, and substituting $\operatorname{Tr}(W_{0})=NM$, we have

Substituting the specified value of $T$, and using the fact that $\exp(-\eta)-\frac{\eta^{2}}{3}\geq 1-\eta$ (which holds for any $\eta\in$), we have

We therefore have that the algorithm works correctly, modulo the precision issues to be discussed in the section following this one. It remains only to observe that it can be implemented in NC (meaning that it results in an $\textup{NC}(\mathit{poly})$ computation when composed with the first two steps of the simulation). Some of the details required to argue this can be found below; but at a high level one sees that each iteration of the loop in step 3 can be performed with high precision in NC, and the total number of iterations required is polynomial in $n$ (and therefore polylogarithmic in the size of $Q$).

Precision requirements for the simulation

We now discuss the precision that is required for the simulation to yield a correct answer. It will turn out that the simulation is not particularly sensitive to errors, and one could in fact afford to take exponentially more precision than is required and still be within the class $\textup{NC}(\mathit{poly})$.

The first step of the simulation, in which an explicit description of $\ket{\psi}$ and $\Pi$ is obtained, can be performed exactly in $\textup{NC}(\mathit{poly})$ as has already been observed. So, let us move on to the second step, in which $\ket{\psi}$ and $\Pi$ are processed to obtain a well-conditioned interactive measurement operator $Q$. This step requires the approximation of one singular value decomposition (to approximate the Schmidt decomposition of $\ket{\psi}$), along with a few other operations that can be performed exactly or with high precision in NC.

For the moment let us denote by $\widetilde{Q}$ the actual operator that is computed by an NC implementation of this step, as opposed to the true operator $Q$ that would be output by an idealized, exact complex number algorithm. By computing the singular value decomposition to high precision, it is possible to take such an approximation so that

where $\mathit{poly}$ denotes any polynomial of our choice. It is not difficult to prove that the quantity $|\mu(Q)-\mu(\widetilde{Q})|$ is upper-bounded by $N$ times $\lVert\mspace{1.0mu}Q-\widetilde{Q}\mspace{1.0mu}\rVert$, and therefore we may take $\widetilde{Q}$ so that

again for $\mathit{poly}$ denoting any polynomial of our choice. We do not need this much precision: we only need a $1/\mathit{poly}(n)$ separation between the values of $\mu(\widetilde{Q})$ for the cases $x\in A_{\text{yes}}$ and $x\in A_{\text{no}}$, which requires that $\lVert\mspace{1.0mu}Q-\widetilde{Q}\mspace{1.0mu}\rVert$ is exponentially (rather than double-exponentially) small in $n$. So, to be concrete, we may decide to take sufficient precision so that

Hereafter we will return to writing $Q$ rather than $\widetilde{Q}$, with the understanding that $Q$ now represents an approximation that is stored by our algorithm. In addition, we will assume that $\sqrt{Q}$, and therefore $Q^{-1/2}$ as well, has Gaussian rational entries and is known precisely. This assumption is easily met by replacing $Q$ with the square of a high precision approximation to $\sqrt{Q}$. The point of this assumption is that we avoid having to consider an additional error term every time $\sqrt{Q}$ or $Q^{-1/2}$ is involved in any computation. (There is no reason beyond simplifying the analysis to make this assumption.)

Now suppose that the algorithm described in Section 7 is performed with limited precision. Consider first the case that the algorithm accepts, and let $\rho=\rho_{t}$ denote the density operator that is stored by the algorithm on the iteration $t$ in which acceptance occurs. Note that it is not necessary to view that $\rho$ is an approximation of something else: the simple fact that $\rho$ causes acceptance will allow us to conclude that $x\in A_{\text{yes}}$ in a similar way to the error-free analysis.

to denote the approximate value of the spectral decomposition, so that $\lVert\mspace{1.0mu}P_{0}-\widetilde{P}_{0}\mspace{1.0mu}\rVert$ represents the error in this approximation, and let us assume that sufficient accuracy is taken so that

As above, this is significantly less accuracy than is available—for we could take

if it were advantageous. Continuing on as before, let

Now let us consider the case that the algorithm rejects, and in particular let us focus on the operators $Y_{0},\ldots,Y_{T-1}$ that are computed over the course of the algorithm. As for the case of acceptance, these operators are not viewed as approximations to anything: the fact that these operators exist and cause rejection in the algorithm is enough to conclude that $x\in A_{\text{no}}$. Let us continue to write

and $\rho_{t}=W_{t}/\operatorname{Tr}(W_{t})$ for each $t=0,\ldots,T-1$; but we must keep in mind that the algorithm only computes approximations of these operators. The algorithm must also approximate the spectral decomposition of each $\Phi(\rho_{t})$, where the source of errors in this case comes from both the spectral decomposition computation and the fact that $\rho_{t}$ is approximated.

Now, in the error free analysis, the conditions

were proved, and these conditions allowed us to conclude that $Y$ satisfies

If we follow precisely the same proof, but with the condition $\left\langle\rho_{t},\Phi^{\ast}(Y_{t})\right\rangle=1$ replaced by

for some choice of $\alpha>0$, we once again find immediately that $\operatorname{Tr}(Y)\leq(1+\varepsilon)\gamma$. This time we have

Thus, given that the conditions $\operatorname{Tr}(Y_{t})\leq\gamma$ and $\left\lVert\mspace{1.0mu}\delta\Phi^{\ast}(Y_{t})\mspace{1.0mu}\right\rVert\leq 1$ follow from an inspection of the algorithm as before, it suffices to compute the matrix exponentials and spectral decompositions with sufficient accuracy that $\left\langle\rho_{t},\Phi^{\ast}(Y_{t})\right\rangle>1-\eta^{2}/12$. This is easily done: as the argument of the matrix exponentials have norm bounded by $T$, one is able to compute both the matrix exponentials and the spectral decompositions with exponentially greater accuracy in NC than is required.

Conclusion

We have proved that $\textup{QIP}(2)\subseteq\textup{PSPACE}$ using a semidefinite programming formulation of the maximum acceptance probability of two-message quantum interactive proof systems, along with the multiplicative weights update method for verifying these values. An obvious question remains: can this method be extended, or some other method devised, to prove $\textup{QIP}=\textup{PSPACE}$?

The research presented in this paper was supported by Canada’s NSERC, MITACS, the Canadian Institute for Advanced Research, and the US Army Research Office and National Security Agency; and was partially done while Rahul Jain was a member of the Institute for Quantum Computing and the School of Computer Science at the University of Waterloo.

References