QIP = PSPACE

Introduction

Efficient proof verification is a fundamental notion in computational complexity theory. The most direct complexity-theoretic abstraction of efficient proof verification is represented by the complexity class NP, wherein a deterministic polynomial-time verification procedure decides whether a given polynomial-length proof string is valid for a given input. One cannot overstate the importance of this class and its presently unknown relationship to P, the class of problems solvable deterministically in polynomial time. This problem, which is known as the P versus NP problem, is one of the greatest of all unsolved problems in mathematics.

In the early to mid 1980’s, Babai [Bab85] and Goldwasser, Micali, and Rackoff [GMR85] introduced a computational model that extends the notion of efficient proof verification to interactive settings. (Journal versions of these papers appeared later as [BM88] and [GMR89].) In this model, which is known as the interactive proof system model, a computationally bounded verifier interacts with a prover of unlimited computation power. The interaction comprises one or more rounds of communication between the prover and verifier, and the verifier may make use of randomly generated bits during the interaction. After the rounds of communication are finished, the verifier makes a decision to accept or reject based on the interaction.

A decision problem $A$ is said to have an interactive proof system if there exists a verifier, always assumed to run in polynomial time, that meets two conditions: the completeness condition and the soundness condition. The completeness condition formalizes the requirement that true statements can be proved, which in the present setting means that if an input string $x$ is a yes-instance of $A$, then there exists a course of action for the prover that causes the verifier to accept with high probability. The soundness condition formalizes the requirement that false statements cannot be proved, meaning in this case that if an input string $x$ is a no-instance of $A$, then the verifier will reject with high probability no matter what course of action the prover takes. One denotes by IP the collection of decision problems having interactive proof systems. (Here, and throughout the rest of the paper, we take the term problem to mean promise problem, and consider that all complexity classes to be discussed are classes of promise problems. Promise problems were defined by Even, Selman and Yacobi [ESY84], and readers unfamiliar with them are referred to the survey of Goldreich [Gol05].)

The expressive power of interactive proof systems was not initially known when they were first defined, but it was soon determined to coincide with PSPACE, the class of problems solvable deterministically in polynomial space. The containment $\textup{IP}\subseteq\textup{PSPACE}$, which is generally attributed to Feldman [Fel86], is fairly straightforward—and readers not interested in proving this fact for themselves can find a proof in [HO02]. Known proofs [LFKN92, Sha92, She92] of the reverse containment $\textup{PSPACE}\subseteq\textup{IP}$, on the other hand, are not straightforward, and make essential use of a technique commonly known as arithmetization. This technique involves the extension of Boolean formulas to multivariate polynomials over large finite fields whose 0 and 1 elements are taken to represent Boolean values. Through the use of randomness and polynomial interpolation, verifiers may be constructed for arbitrary PSPACE problems.

Many variants of interactive proof systems have been studied, including public-coin interactive proofs [Bab85, BM88, GS89], multi-prover interactive proofs [BOGKW88], zero-knowledge interactive proofs [GMR89, GMW91], and competing-prover interactive proofs [FK97]. The present paper is concerned with quantum interactive proof systems, which were first studied a decade after $\textup{IP}=\textup{PSPACE}$ was proved [Wat99, KW00]. The fundamental notions of this model are the same as those of classical interactive proof systems, except that the prover and verifier may now process and exchange quantum information. Similar to the classical case, several variants of quantum interactive proof systems have been studied (including those considered in [HKSZ08, KKMV09, KM03, Kob08, MW05, Wat09]).

One of the most interesting aspects of quantum interactive proof systems, which distinguishes them from classical interactive proof systems (at least to the best of our current knowledge), is that they can be parallelized to three messages. That is, quantum interactive proof systems consisting of just three messages exchanged between the prover and verifier already have the full power of quantum interactive proofs having a polynomial number of messages [KW00]. Classical interactive proofs are not known to hold this property, and if they do the polynomial-time hierarchy collapses to the second level [BM88].

The complexity class QIP is defined as the class of decision problems having quantum interactive proof systems. QIP trivially contains IP, as the ability of a verifier to process quantum information is never a hindrance—a quantum verifier can simulate a classical verifier, and a computationally unbounded prover can never use quantum information to an advantage against a verifier behaving classically. The inclusion $\textup{PSPACE}\subseteq\textup{QIP}$ is therefore immediate. The best upper bound on QIP known prior to the present paper was $\textup{QIP}\subseteq\textup{EXP}$, which was proved in [KW00] through the use of semidefinite programming. The optimal probability with which a given verifier can be made to accept in a quantum interactive proof system can be represented as an exponential-size semidefinite program, and known polynomial-time algorithms for semidefinite programming provide the required tool to prove the containment. It has been an open problem for the last decade to establish more precise bounds on the class QIP.

It was recently shown in the paper [JUW09] that $\textup{QIP}(2)$, the class of problem having 2-message quantum interactive proof systems, is contained in PSPACE. That paper made use of a parallel algorithm, based on a method known as the matrix multiplicative weights update method, to approximate optimal solutions for a class of semidefinite programs that represent the maximum acceptance probabilities for verifiers in two-message quantum interactive proofs. In this paper we extend this result to all of QIP, establishing the relationship $\textup{QIP}=\textup{PSPACE}$. Similar to [JUW09], we use the matrix multiplicative weights update method, together with parallel methods for matrix computations.

The multiplicative weights method is a framework for algorithm design having its origins in various fields, including learning theory, game theory, and optimization. Its matrix variant, as discussed in the survey paper [AHK05] and the PhD thesis of Kale [Kal07], gives an iterative way to approximate the optimal value of semidefinite programs [AK07, WK06]. In addition to its application in [JUW09], it was applied to quantum complexity in [JW09] to prove the containment of the complexity class QRG(1) in PSPACE. The key strength of this method for these applications is that it can be parallelized for some special classes of semidefinite programs.

A key result that allows our technique to work for the entire class QIP is the characterization $\textup{QIP}=\textup{QMAM}$ proved in [MW05]. This characterization, which is described in greater detail in the next section, concerns a restricted notion of interactive proof systems known as Arthur–Merlin games. An Arthur–Merlin game is an interactive proof system wherein the verifier can only send uniformly generated random bits to the prover. Following Babai [Bab85], one refers to the verifier as Arthur and to the prover as Merlin in this setting. It is also typical to refer to the individual bits of Arthur’s messages as coins, given that they are each uniformly generated like the flip of a fair coin. The restriction that Arthur sends only uniformly generated bits to Merlin, and therefore does not have the option to base his messages on private information unknown to Merlin, would seem to limit the power of Arthur–Merlin games in comparison to ordinary interactive proof systems. But in fact this is known not to be the case, both for classical [GS89] and quantum [MW05] interactive proof systems. In the quantum setting, this characterization admits a significant simplification in the semidefinite programs that capture the complexity of the class QIP.

The remainder of this paper has the following organization. Section 2 includes background information, notation, and other preliminary discussions that are relevant to the remainder of the paper. Section 3 describes a semidefinite programming problem that captures the complexity of the class QIP based on quantum Arthur–Merlin games, and Section 4 presents the main algorithm that solves this problem. Finally, Section 5 discusses a parallel approximation to the algorithm from Section 4 and explains how its properties lead to the containment $\textup{QIP}\subseteq\textup{PSPACE}$.

Preliminaries

This section contains a summary of the notation and terminology on linear algebra, quantum information, semidefinite programming, quantum Arthur–Merlin games, and bounded-depth circuits that is used later in the paper. For the most part, these discussions are intended only to make clear the notation and terminology that we use, and not to provide introductions to these topics. We assume that the reader already has familiarity with complexity theory and quantum computing, and refer readers who are not to [AB09] and [NC00].

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

to denote the eigenvalues of $A$ sorted from largest to smallest.

Every Hermitian operator $A$ can be expressed uniquely as $A=P-Q$ for positive semidefinite operators $P$ and $Q$ satisfying $\left\langle P,Q\right\rangle=0$. The operator $P$ is said to be the positive part of $A$, while $Q$ is the negative part.

The set $\Gamma$ is the set of measurement outcomes, and when such a measurement is performed on $\mathsf{V}$ while it is in the state $\rho$, each outcome $b\in\Gamma$ occurs with probability $\left\langle P_{b},\rho\right\rangle$.

The Golden-Thompson Inequality (see Section IX.3 of [Bha97]) states that, for any two Hermitian operators $A$ and $B$ on $\mathcal{V}$, we have

2 Semidefinite programming

A semidefinite program over complex vector spaces $\mathcal{V}$ and $\mathcal{W}$ is a pair of optimization problems as follows.

It is typical that semidefinite programs are stated in forms that do not explicitly describe $\Psi$, $C$ and $D$, and the same is true for the semidefinite programs we will consider. It is, however, routine to put them into the above form.

With the above optimization problems in mind, one defines the primal feasible set $\mathcal{P}$ and the dual feasible set $\mathcal{D}$ as

Operators $X\in\mathcal{P}$ and $Y\in\mathcal{D}$ are also said to be primal feasible and dual feasible, respectively. The functions $X\mapsto\left\langle C,X\right\rangle$ and $Y\mapsto\left\langle D,Y\right\rangle$ are called the primal and dual objective functions, and the optimal values associated with the primal and dual problems are defined as

Semidefinite programs have associated with them a powerful theory of duality, which refers to the special relationship between the primal and dual problems. The property of weak duality, which holds for all semidefinite programs, states that $\alpha\leq\beta$. This property implies that every dual feasible operator $Y\in\mathcal{D}$ provides an upper bound of $\left\langle D,Y\right\rangle$ on the value $\left\langle C,X\right\rangle$ that is achievable over all choices of a primal feasible $X\in\mathcal{P}$, and likewise every primal feasible operator $X\in\mathcal{P}$ provides a lower bound of $\left\langle C,X\right\rangle$ on the value $\left\langle D,Y\right\rangle$ that is achievable over all choices of a dual feasible $Y\in\mathcal{D}$.

It is not always the case that $\alpha=\beta$ for a given semidefinite program, but in most natural cases it does hold. The situation in which $\alpha=\beta$ is known as strong duality, and several conditions have been identified that imply strong duality. One such condition is strict dual feasibility: if $\alpha$ is finite and there exists an operator $Y>0$ such that $\Psi^{\ast}(Y)>C$, then $\alpha=\beta$. The symmetric condition of strict primal feasibility also implies strong duality.

3 Single-coin quantum Arthur–Merlin games

Quantum Arthur–Merlin games were proposed in [MW05] as a natural quantum variant of classical Arthur–Merlin games. Here, one simply mimics the classical definition in requiring that Arthur’s messages to Merlin consist of uniformly generated random bits. Merlin’s messages to Arthur, however, may be quantum; and after all of the messages have been exchanged Arthur is free to perform a quantum computation when deciding to accept or reject.

Of particular interest to us are quantum Arthur–Merlin games in which three messages are exchanged, and where Arthur’s only message consists of a single bit. In more precise terms, such an interaction takes the following form:

Merlin sends a quantum register $\mathsf{W}$ to Arthur. Merlin is free to initialize this register to any quantum state of his choice, and may entangle it with a register of his own if he chooses.

After receiving $\mathsf{W}$ from Merlin, Arthur chooses a bit $a\in\{0,1\}$ uniformly at random. Merlin learns the value of $a$.

Merlin sends Arthur a second quantum register $\mathsf{Y}$. He does this after step 2, so he has the option to condition the state of $\mathsf{Y}$ upon the value of $a$. The register $\mathsf{Y}$ could, of course, be entangled with $\mathsf{W}$ in any way that quantum information theory permits.

After receiving $\mathsf{Y}$, Arthur performs one of two binary-valued measurements, determined by the value of the random bit $a$, on the pair $(\mathsf{W},\mathsf{Y})$. The measurement outcome 1 is interpreted as acceptance, while 0 is interpreted as rejection.

Arthur’s measurements must of course be efficiently implementable. This notion is formalized by requiring that the measurements are implementable by polynomial-time generated families of quantum circuits, which naturally requires the registers $\mathsf{W}$ and $\mathsf{Y}$ to consist of a number of qubits that is polynomial in the length of the input. Further details may be found in [MW05].

The result of [MW05] that we make use of is that every problem $A\in\textup{QIP}$ has a single-coin Arthur–Merlin game as just described. The game is such that if $x$ is a yes-instance of the problem $A$, then Arthur accepts with probability 1, whereas if the input $x$ is a no-instance of the problem then Arthur accepts with probability at most $1/2+\varepsilon$, for any desired constant $\varepsilon>0$. (In the construction given in [MW05], Arthur’s measurements are always nontrivial projective measurements. This implies that even for no-instance inputs, Merlin can cause Arthur to accept with probability at least 1/2 by simply guessing in advance Arthur’s random bit.)

4 Bounded-depth circuit complexity

In the last section of the paper, we will require the definitions of two complexity classes based on bounded-depth circuit families: NC and $\textup{NC}(\mathit{poly})$. It is convenient for us to define these as classes of functions rather than decision problems, and when we wish to view them as classes of decision problems we simply restrict our attention to binary-valued functions. The class NC contains all functions computable by logarithmic-space uniform Boolean circuits of polylogarthmic depth, and $\textup{NC}(\mathit{poly})$ contains all functions that can be computed by polynomial-space uniform families of Boolean circuits having polynomial-depth. For decision problems it is known [Bor77] that $\textup{NC}(\mathit{poly})=\textup{PSPACE}$, and the proof of our main result will make use of this fact.

There are two fundamental properties of $\textup{NC}(\mathit{poly})$ that we will take advantage of. The first is that functions in NC and $\textup{NC}(\mathit{poly})$ compose well, and the second is that many computational problems involving matrices are in NC. In more precise terms, the first property is as follows. 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 straightforward way of composing the families of circuits that compute $F$ and $G$.

To discuss the second property, it will be helpful to make clear our assumptions concerning matrix computations. We will always assume that the matrices on which computations are performed have entries with rational real and imaginary parts, and that the rational numbers are represented as pairs of integers in binary notation. Unless it is explicitly noted otherwise, any other rational numbers involved in our computations will be represented in a similar way.

With these assumptions in place, we first note that elementary matrix operations, including inverses and iterated sums and products of matrices, are known to be in NC. There is an extensive literature on this topic, and we refer the reader to von zur Gathen’s survey [Gat93] for more details. We also note that matrix exponentials and spectral decompositions can be approximated to high accuracy in NC. In more precise terms, the following two problems are in NC.

The reader will note that in these problems, the description of the error parameter $\eta$ could require as few as $O(\log(1/\eta))$ bits. This implies that highly accurate approximations, for instance where $\eta=2^{-n}$, are possible in NC. The fact that matrix exponentials can be approximated in NC follows by truncating the series

to a number of terms linear in $k+\log(1/\eta)$. (From a numerical point of view this is not a very good way to compute matrix exponentials [ML03], but it is arguably the simplest way to prove that the stated problem is in NC.) The fact that spectral 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].

A semidefinite programming formulation of the problem

Consider Arthur’s verification procedure for a given single-coin QMAM protocol on a fixed input string $x$. Arthur first receives a register $\mathsf{W}$, then generates a random bit $a\in\{0,1\}$, and then receives a second register $\mathsf{Y}$. He then measures $(\mathsf{W},\mathsf{Y})$ with respect to a binary-valued measurement

There is, of course, a constraint on Merlin’s choice of $\rho_{0}$ and $\rho_{1}$, which is that they must agree on $\mathsf{W}$, as Merlin cannot touch the register $\mathsf{W}$ at any point after Arthur chooses the random bit $a$. In more precise terms, it must hold that

Now, we note that the condition (2) implies that

for $a\in\{0,1\}$ satisfy the conditions (1) and (2). It follows that the following semidefinite program represents the optimal probability with which Merlin can convince Arthur to accept.

and consider the following semidefinite program.

It is clear that this semidefinite program has the same optimal value as the previous one.

We will be interested in the optimal value of this semidefinite program in the case that $\lVert\mspace{1.0mu}Q^{-1}\mspace{1.0mu}\rVert$ is upper-bounded by a fixed constant and where there is a promise on the optimal value. The promise, which will come from the properties of the quantum Arthur–Merlin games under consideration, is that the optimal value does not lie in the interval $(5/8,\,7/8)$, and the goal is to determine whether the optimal value is larger than $7/8$ or smaller than $5/8$.

For readers familiar with the semidefinite program for $\textup{QIP}(2)$ presented in [JUW09], we note that there are two essential differences between it and the one above. The first difference is that the semidefinite program in [JUW09] effectively replaces the density operator $\sigma$ with the scalar value 1, which would seem to suggest added difficulty for the case at hand. The second difference is that $\mathcal{X}$ is two-dimensional for the semidefinite program above, whereas it has arbitrary size in [JUW09]. This second difference more than compensates for the difficulty induced by the first, and we find that the above semidefinite program is actually much easier to solve than the one for $\textup{QIP}(2)$.

The main algorithm and its analysis

We now present the main algorithm for the semidefinite programming problem from the previous section. The algorithm, which is described in Figure 1, takes as input an operator

It is assumed that $Q$ is invertible and satisfies $\lVert\mspace{1.0mu}Q^{-1}\mspace{1.0mu}\rVert\leq 64$. (The algorithm could easily be adapted to handle any other fixed constant in place of 64, but this choice is sufficient for our needs.) Moreover, it is assumed that the optimal value of the semidefinite program in Section 3 that is defined by $Q$ does not lie in the interval $(5/8,\,7/8)$. Our goal is to prove that the algorithm accepts when the optimal value is at least $7/8$ and rejects when the optimal value is at most $5/8$.

Here we present the correctness of the algorithm under the assumption that all computations are performed exactly. Issues that arise due to inaccuracies in the computation are discussed in the next section.

Assume first that the algorithm accepts, and write

for $t\in\{0,\ldots,T-1\}$ corresponding to the iteration in which acceptance occurs. For the sake of clarity, let us note explicitly that

We wish to prove that the optimal value of our semidefinite program is at least $7/8$, and we will do this by constructing a primal feasible solution that achieves an objective value strictly larger than $5/8$.

By the definition of $\Pi$, it holds that

and by Lemma 1 (which is stated and proved below) it holds that

Combining the equations (5) and (6) one has

represent a feasible solution to the primal problem under consideration, achieving the objective value

Now assume that the algorithm rejects, and consider the operator

We claim that $Y$ is dual feasible and achieves an objective value that is strictly smaller than $7/8$. This will imply that the optimal value of the semidefinite program is at most $5/8$.

by the Golden–Thompson inequality. As each $\Pi_{t}$ is a projection operator, we have

where we have used the sub-multiplicativity of the spectral norm to obtain the inequality. Given that $\beta_{t}>\varepsilon$ in the case at hand, it follows that $\left\lVert\mspace{1.0mu}\delta\Phi^{\ast}(\Pi_{t}/\beta_{t})\mspace{1.0mu}\right\rVert<1$. By Lemma 2 (also presented below) it therefore follows that

As each $W_{t}$ is positive semidefinite, we obtain

Substituting $\rho_{t}=W_{t}/\operatorname{Tr}(W_{t})$ yields

where the equality follows from $\left\langle\rho_{t},\Phi^{\ast}(\Pi_{t})\right\rangle=\left\langle\Phi(\rho_{t}),\Pi_{t}\right\rangle=\beta_{t}$ and the last inequality follows from the fact that $1+z\leq\exp(z)$ for all real numbers $z$. As $\operatorname{Tr}(W_{0})=N$, it follows that

Using the inequality $\exp(-\varepsilon)-\varepsilon^{2}/4>1-\varepsilon$, and substituting the value of $T$ specified by the algorithm, we have

Now it remains to establish an upper bound on the dual objective value achieved by $Y$. A similar method to the one used to prove the feasibility of $Y$ above will provide a suitable bound. We begin by observing, for each $t=0,\ldots,T-1$, that

and using the fact that $\beta_{t}>\epsilon$ in the case at hand, it follows that $\left\lVert\mspace{1.0mu}\delta\operatorname{Tr}_{\mathcal{X}}(\Pi_{t}/\beta_{t})\mspace{1.0mu}\right\rVert<1$. We now apply Lemma 2 to obtain

As each $Z_{t}$ is positive semidefinite it follows that

Substituting $\xi_{t}=Z_{t}/\operatorname{Tr}(Z_{t})$ gives

Thus, $Y$ is a dual feasible solution whose objective value is smaller than $7/8$, and we conclude that the optimal value of our semidefinite program is at most $5/8$ as required.

It remains to state and prove the two lemmas that were required in the analysis above. They are as follows.

Let $\sigma_{x}$, $\sigma_{y}$ and $\sigma_{z}$ denote the Pauli operators on $\mathcal{X}$. In matrix form they are

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

from which the first inequality follows. Similarly, there exists a value $\lambda_{0}\in(0,\lambda)$ such that

Proof that QIP is contained in PSPACE

With the algorithm from the previous section in hand, the proof that $\textup{QIP}\subseteq\textup{PSPACE}$ follows the same approach used in [JUW09] to prove $\textup{QIP}(2)\subseteq\textup{PSPACE}$. The proof is described in the two subsections that follow.

Let $A=(A_{\text{yes}},A_{\text{no}})$ be a promise problem in QIP. Our goal is to prove that $A\in\textup{PSPACE}$. Given that $\textup{PSPACE}=\textup{NC}(\mathit{poly})$, as was mentioned in Section 2.4, it suffices to prove $A\in\textup{NC}(\mathit{poly})$.

Using Theorem 5.4 of [MW05] we have that there exists a single-coin QMAM-protocol for $A$ with perfect completeness and soundness probability $1/2+\varepsilon$, for $\varepsilon=1/64$. (Of course any other sufficiently small positive constant would do, and in fact one can replace $\varepsilon$ with an exponentially small value—but this choice is sufficient for our needs.) We will make a small modification in Arthur’s specification so that he always accepts outright with probability $4\varepsilon$, and otherwise measures the registers sent by Merlin according to his original specification. With this modification in place, we have that if $x\in A_{\text{yes}}$, then Arthur can be made to accept with certainty, while if $x\in A_{\text{no}}$ then the maximum probability with which Arthur can be made to accept is smaller than $1/2+3\varepsilon$. It also holds that every strategy of Merlin causes Arthur to accept with probability at least $4\varepsilon$.

Now, for any fixed choice of an input string $x\in A_{\text{yes}}\cup A_{\text{no}}$, let $Q$ be the operator defined from this modified specification of Arthur on the input $x$ as was described in Section 3. Give that Arthur always accepts with probability at least $4\varepsilon$, it follows that the smallest eigenvalue of $Q$ is at least $2\epsilon$. Therefore, $Q$ is invertible and satisfies $\lVert\mspace{1.0mu}Q^{-1}\mspace{1.0mu}\rVert\leq 1/(2\varepsilon)$. Moreover, the semidefinite program defined by $Q$, as described in Section 3, has an optimal value that is equal to 1 when $x\in A_{\text{yes}}$ and smaller than $1/2+3\varepsilon$ when $x\in A_{\text{no}}$.

Next, consider a two-step computation as follows:

Compute from a given input string $x$ an explicit description of the operator $Q$ specified above.

Run an NC implementation of the algorithm from Section 4 on $Q$.

The first step of this computation can be performed in $\textup{NC}(\mathit{poly})$ using an exact computation. This follows from the fact that in $\textup{NC}(\mathit{poly})$ one can first compute explicit matrix representations of all of the gates in the quantum circuit specifying Arthur’s measurements, and then process these matrices using elementary matrix operations to obtain $Q$. Note that, without loss of generality, the description of $Q$ has length polynomial in $N$, which (as defined in the algorithm) is the dimension of the space on which it acts.

The second step of the computation, which is an NC implementation of the algorithm from Section 4, is not quite as straightforward as the first step. In fact, it is only possible for us to approximate this algorithm in NC, as we only know how to approximate the operator $Q^{-1/2}$, the matrix exponentials, and the spectral decompositions needed to obtain the projection operators $\Pi_{0},\ldots,\Pi_{T-1}$. Nevertheless, we claim that such an approximation is possible in NC, with sufficient accuracy to distinguish the two cases $x\in A_{\text{yes}}$ and $x\in A_{\text{no}}$. This fact is argued in the subsection following this one.

Under the assumption that the second step is performed in NC, we have that the composition of the two steps is an $\textup{NC}(\mathit{poly})$ computation. We therefore obtain that $A\in\textup{NC}(\mathit{poly})$ as required.

2 A high precision NC implementation of the algorithm

It remains to argue that the algorithm from Section 4 can be approximated by an NC computation with sufficient accuracy to distinguish the cases $x\in A_{\text{yes}}$ and $x\in A_{\text{no}}$ as described above. It will be evident from the discussion that follows that obtaining sufficient accuracy in NC is not a significant challenge; and one could, in fact, demand much greater accuracy (by an order of magnitude) and still be able to perform the computation in NC.

The first step in the implementation of the algorithm is to approximate $Q^{-1/2}$. In more precise terms, we first compute an operator $R$ such that $R^{2}$ is a close approximation to $Q$, and then compute $R^{-1}$ in NC using an exact computation. To compute $R$, we may compute a spectral decomposition of $Q$, and then take $R$ to be the operator that results by replacing each eigenvalue in this decomposition with its square root. It is straightforward to perform high-precision approximations of these computations in NC with sufficient accuracy so that $\left\lVert\mspace{1.0mu}Q-R^{2}\mspace{1.0mu}\right\rVert\leq\varepsilon$ and $\left\lVert\mspace{1.0mu}R^{-1}\mspace{1.0mu}\right\rVert\leq 1/\varepsilon$. Now, if we compare two semidefinite programs, one defined by $Q$ as specified in Section 3 and the other defined similarly with $Q$ replaced by $R^{2}$, we find that the optimal values are close. More specifically, given that $\left\lVert\mspace{1.0mu}Q-R^{2}\mspace{1.0mu}\right\rVert\leq\varepsilon$, the optimal values of the two semidefinite programs can differ by at most $2\varepsilon$. Thus, the optimal value of the semidefinite program for $R^{2}$ is at least $1-2\varepsilon>7/8$ in case $x\in A_{\text{yes}}$ and at most $1/2+5\varepsilon<5/8$ in case $x\in A_{\text{no}}$.

In the interest of clarity, to avoid introducing a new variable $R$ into the analysis that follows, let us simply redefine $Q$ at this point to be $R^{2}$. Thus, $Q^{-1/2}=R^{-1}$ is known exactly by our implementation of the algorithm and all of the requirements on $Q$ are in place—which are that $\left\lVert\mspace{1.0mu}Q^{-1/2}\mspace{1.0mu}\right\rVert\leq 1/\varepsilon=64$ and the optimal value of the semidefinite program in Section 3 defined by $Q$ is at least $7/8$ if $x\in A_{\text{yes}}$ and at most $5/8$ if $x\in A_{\text{no}}$.

Next, let us focus on the projection operators

that are to be computed in the course of the algorithm. We will choose an integer $K$ that we take to represent the number of bits of accuracy with which these operators are stored. In more precise terms, the algorithm will store the real and imaginary parts of each of the entries of the above operators (13) and (14) as integers divided by $2^{K}$. It will suffice to take $K=c\lceil\log(N)\rceil$, for a suitable choice of a constant $c$, although one could in fact afford to take $K$ to be polynomial in $N$ rather than logarithmic. As each entry of these operators has absolute value at most 1, the total number of bits needed to represent the entire collection of operators is $O(TKN^{2})$, which is polynomial in $N$.

In addition to the above operators, the algorithm will store the scalar values $\beta_{0},\ldots,\beta_{T-1}$. These values do not need to be approximated; each value $\beta_{t}$ is computed exactly as the rational number defined by the operators $\rho_{t}$ and $\Pi_{t}$ stored by the algorithm. We will not consider that the operators $W_{1},\ldots,W_{T}$ and $Z_{1},\ldots,Z_{T}$ are stored by the algorithm at all, as their only purpose in the computation is to specify the density operators $\rho_{1},\ldots,\rho_{T}$ and $\xi_{1},\ldots,\xi_{T}$.

We will also take $\mu$ to be a small constant, say $\mu=2^{-10}$, that will represent an error parameter for the computation. Similar to the choice of $K$, we could afford to take $\mu$ to be significantly smaller than this and still be able to perform the computation in NC.

Now, consider the two steps (a) and (b) that are performed within each iteration of the loop in step 2 of the algorithm. We must approximate these steps, and we demand the following accuracy requirements when doing this. For step (a), we will require that the projection operator $\Pi_{t}$ computed by the algorithm satisfies the condition

In these inequalities we do not consider that $W_{t+1}$ and $Z_{t+1}$ are stored by the algorithm, but rather we consider that they are operators defined by the equations

for the particular operators $\Pi_{0}/\beta_{0},\ldots,\Pi_{t}/\beta_{t}$ that are stored by the algorithm. The algorithm’s approximations of $W_{t+1}$ and $Z_{t+1}$ determine the density operators $\rho_{t+1}$ and $\xi_{t+1}$. As the matrix exponentials are to be computed for operators having norm bounded by $T=O(\log N)$, it is clear that $\rho_{t+1}$ and $\xi_{t+1}$ with the required properties can be computed in NC.

Finally, we have that the total number of iterations in the algorithm is $T=O(\log N)$. Given that each of the iterations of the algorithm can be performed in NC, and that the total number of bits that must be stored from one iteration to the next is polynomial in $N$, we have that the composition of these $T$ iterations can be performed in NC as well.

It remains only to show that the approximations (15) and (16) are sufficient to guarantee that the algorithm accepts or rejects correctly. This analysis is done in almost exactly the same way as was presented in Section 4. Even though the operators

do not necessarily satisfy the precise equations that were assumed in Section 4, they may nevertheless be used to construct primal and dual solutions to the semidefinite program that satisfy the required bounds.

In the case that the algorithm accepts, a consideration of the operators $\rho=\rho_{t}$, $\Pi=\Pi_{t}$, and $\xi=\xi_{t}$ as before allows for the construction of a primal feasible solution with a large objective value. In place of (7), we have

which allows for a lower bound of $1/(\gamma+2\varepsilon+\mu)$ for the primal objective function. For our choice $\mu=2^{-10}$ of an error bound, this quantity is still lower-bounded by $5/8$, which implies that the algorithm has operated correctly in this case.

A similar analysis to the one before holds for the case of rejection as well. We consider the operators

When proving the dual feasibility of $Y$ we are no longer free to substitute $\rho_{t}=W_{t}/\operatorname{Tr}(W_{t})$, but instead we must introduce a small error term due to the fact that $\rho_{t}$ is just an approximation to $W_{t}/\operatorname{Tr}(W_{t})$. By the first inequality of (16) above we may conclude that

and by substituting this into (11) and following a similar argument to the one from before we obtain

Thus, dual feasibility holds for $Y$. Along similar lines, by using (15) and (16), one finds again that the dual objective value achieved by $Y$ less than $7/8$, and therefore the algorithm operates correctly in this case as well.

Acknowledgments

We thank Xiaodi Wu for helpful discussions. Rahul Jain’s research is supported by the internal grants of the Centre for Quantum Technologies, which is funded by the Singapore Ministry of Education and the Singapore National Research Foundation. Zhengfeng Ji’s research at the Perimeter Institute is supported by the Government of Canada through Industry Canada and by the Province of Ontario through the Ministry of Research & Innovation. Sarvagya Upadhyay’s research is supported in part by Canada’s NSERC, CIFAR, MITACS, QuantumWorks, Industry Canada, Ontario’s Ministry of Research and Innovation, and the U.S. ARO. John Watrous’s research is supported by Canada’s NSERC and CIFAR.

References