Communications of the ACM

Research highlights

QIP = PSPACE

By Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous
Communications of the ACM, December 2010, Vol. 53 No. 12, Pages 102-109
10.1145/1859204.1859231
Comments

The interactive proof system model of computation has been studied extensively in computational complexity theory and theoretical cryptography for more than 25 years, and has driven the development of interesting new techniques and insights in those fields. This work considers the quantum interactive proof system model, which is the classical model's natural quantum computational analog. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable with an ordinary classical computer using at most a polynomial amount of memory (or QIP = PSPACE in complexity-theoretic terminology). One striking implication of this characterization is that it implies quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems.

Back to Top

1. Introduction

The notion of a proof has fundamental importance in the theory of computation. Indeed, the foundational work of Alonzo Church and Alan Turing in the 1930s, which produced the first formal models of computation (λ-calculus and Turing machines), was principally motivated by questions concerning proofs in formal logic. The theory of NP-completeness, developed in the 1970s by Stephen Cook, Leonid Levin, and Richard Karp, provides another example. It is built on the notion of efficient proof verification, and is arguably the most widely applicable discovery ever made in the theory of computation.

This paper is concerned with the potential advantages offered by quantum computation in the setting of proofs, and in particular its advantages when applied to the interactive proof system model of computation. Considered by many to be a cornerstone of modern computational complexity theory, the interactive proof system model was first introduced in the mid-1980s, and its quantum computational variant has been an object of study in quantum computing for more than a decade.

The main result to be presented herein is that quantum computation does not enhance the expressive power of interactive proof systems at all: quantum and classical interactive proof systems are equivalent in power, both coinciding with the complexity class PSPACE of computational problems solvable using an amount of memory scaling polynomially in the length of the input to the problem. This resolves a fundamental question about the quantum interactive proof system model that has been open since its introduction.

 1.1. Randomness and interaction in proofs

When speaking of proofs, one typically has a traditional notion in mind where, at least in an abstract sense, the proof itself is a string of symbols to be verified by some form of computation. In the theory of NP-completeness, a proof is generally a string of bits certifying that a given object has a property of interest, such as a graph having a three-coloring. In mathematics, proofs appear in journal papers and books, to be verified by mathematicians with interest in the claimed theorems. Although it is not done, one imagines that in principle—and undoubtedly through monumental effort—such proofs could be transformed into a purely symbolic form verifiable by a computer, presumably in accordance with axiomatic set theory.

There are, however, other interesting notions of proofs that extend the traditional notion in various ways. For instance, randomness may be used in the verification process to gather statistical evidence for or against a given claim. For example, if a coin is flipped 1,000 times, and heads come up 975 times, one can be reasonably sure that the coin is biased toward heads—and although the claim has not been proved in the sense of formal logic, it would be foolish to hold out any hope that the coin is actually fair. Allowing for an interaction in the process of verification, where the proof takes the form not of a static string of symbols, but as a process that may receive input and produce output, is another extension. The interactive proof system model, first proposed by Shafi Goldwasser et al.⁸ and László Babai² in 1985, combines both the extensions of randomness and interaction into a formal computational model.

One variant of a well-known, often-repeated, and highly informal example illustrating a benefit of interaction and randomness in proofs is as follows. Suppose that you can taste the difference between Coke and Pepsi, and that you wish to convince a person that is skeptical of this claim. You cannot reasonably hope, for a variety of reasons, to succeed in this task through the traditional notion of a proof, but it is easily achieved through the use of interaction and randomness. In particular, you may allow the skeptic to subject you to a "blind taste test," where you are offered Coke or Pepsi in an unmarked can—and when you are able to repeatedly make the correct identification, over the course of many independent random tests, the skeptic should be convinced that you can taste the difference. The negligible—but never-theless nonzero—probability that every single identification was made through luck rather than an actual difference in taste is accepted: the formal definition of the model requires a high probability, but not absolute certainty, of correct outcomes.

As a computational model, interactive proof systems are not typically considered for single, isolated statements such as "Coke and Pepsi taste different"—irrespective of that example's informality. Rather, as is done in the theory of NP-completeness, interactive proof systems are connected to computational decision problems where input strings are to be classified as yes-inputs and no-inputs. A particular decision problem is said to have an interactive proof system if there exists a computationally efficient verification procedure (called the verifier) with two properties that capture the essence of what it means to be a proof:

1. Completeness. This property represents the requirement that true statements can be proved. Here, the requirement is that for any yes-input string x, there exists a behavior of the entity the verifier interacts with (called the prover) that causes the verifier to believe that x is indeed a yes-input. This situation may be indicated by the verifier outputting 1 (or accept) after interacting with the prover.
2. Soundness. This property represents the complementary requirement to completeness, which is that false statements cannot be proved. In the current situation, the requirement is that the probability that the verifier will be convinced to output 1 given a no-input is negligible, regardless of the prover's actions. Instead, the verifier outputs 0 (or reject) with probability very close to 1, indicating the prover's failure to convince it otherwise.

While the verifier is restricted to be computationally efficient (or more formally to be describable as a polynomial-time probabilistic Turing machine), no such restriction is placed on the prover. These assumptions serve to place an emphasis on efficient verification, as opposed to efficient construction of proofs.

It must be stressed that there is an inherent asymmetry between the completeness and soundness conditions: when the verifier outputs 0 (or reject), it is not necessarily convinced that the input is a no-input, but only that the prover has failed to convince it that the input is a yes-input. This is analogous to the traditional notion of a proof: one would not be convinced that a particular mathematical statement is false by seeing an incorrect proof claiming it is true.

The most fundamental question, from the viewpoint of complexity theory, about the interactive proof system model is: which computational decision problems have interactive proof systems? The answer is known: a decision problem has an interactive proof system if and only if it is solvable by an ordinary computer (or deterministic Turing machine) that requires an amount of memory that scales at most polynomially in its input length. A more succinct expression of this fact is given by the equation IP = PSPACE. In this equation, IP denotes the set of decision problems having interactive proof systems, PSPACE represents the set of decision problems solvable using polynomial memory (or space), and of course the equality expresses the fact that the two sets are equal, meaning that the two descriptions give rise to precisely the same set of problems.

Like all set equalities, there are two subset relations represented by the equation IP = PSPACE. One of the two relations, IP Í PSPACE, is easy to prove: the typical proof involves a fairly straightforward recursive traversal of a game tree whose edges represent messages exchanged between the prover and verifier, which can be performed in a space-efficient way. The other relation, PSPACE Í IP, was proved by Adi Shamir¹⁴ in 1990, based on work of Carsten Lund et al.¹⁰ It is a landmark result that established the powerful proof technique of arithmetization as a standard tool in computational complexity.

 1.2. Quantum computation in proofs

The idea of quantum computation was born in the early 1980s when Richard Feynman⁷ asked a brilliant question: If quantum mechanics is so hard to simulate with a classical computer, why not build a computer based on quantum mechanics to simulate quantum mechanics more directly? Feynman's ideas on the subject led David Deutsch⁶ to define the quantum Turing machine model and to investigate its computational power. Driven in large part by Peter Shor's subsequent discoveries of polynomial-time algorithms for factoring and computing discrete logarithms on a quantum computer,¹⁵ quantum computation has developed into an active field of study within theoretical computer science and both theoretical and experimental physics.

Large-scale quantum computers do not currently exist, and it is universally agreed that at the very least their realization will be an enormous technological challenge. However, it must also be appreciated that quantum mechanics is a remarkably accurate theory that has never been refuted—and with the theory suggesting that quantum computing should be possible, scientists are naturally compelled to test the theory by attempting to build a quantum computer. Efforts to do this are underway in many laboratories around the world.

Within the theoretical study of quantum computation, it is natural to consider quantum computational variants of interesting classical models, including those based on the notion of proofs. The quantum interactive proof system model, which was first introduced in 1999,¹⁷ represents a natural quantum computational analog to the (classical) interactive proof system model. In simple terms, the quantum model allows the verifier and prover in an interactive proof system to perform quantum computations and exchange quantum information, but is otherwise similar to the classical model.

The potential advantages of quantum computation in the setting of interactive proof systems are not limited to the fact that the verifier is able to perform a potentially wider range of computations. The nature of quantum information is such that it has striking benefits in a variety of information-processing tasks, such as secret key exchange³ and distributed computational tasks allowing limited communication.¹³ A known benefit of quantum computation in the interactive proof system model is that it allows for a major reduction in the number of messages that must be exchanged: quantum interactive proof systems allowing just three messages to be exchanged between the prover and verifier have the full power of those allowing any polynomial number of messages.⁹ It is not known if the analogous fact holds for classical interactive proof systems, but it is conjectured not to hold. (It would, in particular, send complexity theorists reeling from the collapse of the polynomial-time hierarchy if it were true.)

It is not difficult to show that quantum interactive proof systems are at least as powerful as classical ones—due, in essence, to the fact that quantum computers can mimic classical computers. This implies PSPACE Í QIP. Unlike the subset relation IP Í PSPACE, however, it is not straightforward to prove QIP Í PSPACE, and prior to the work presented in this paper this relationship was not known. The remainder of this paper is devoted to a presentation of this result.

Back to Top

2. Quantum Proof Systems

This section aims to provide readers with a basic understanding of quantum information and the quantum interactive proof system model, narrowly focused on material that is required for the subsequent sections of this paper. The standard text, Nielsen and Chuang,¹² is recommended to those readers interested in a more comprehensive presentation of the much more broad field of quantum information and quantum computation.

 2.1. States and measurements

Quantum information is described in the language of matrices and linear algebra in way that is reminiscent of probabilistic models such as Markov chains.

Consider a physical device X whose possible states are the binary strings of length k for some fixed choice of a positive integer k. For brevity, one may say that X is a k-bit register, or a k-qubit register in the quantum setting, as a way of suggesting that X is a device used for storing and processing information.

One way to represent one's knowledge of X in a probabilistic setting, where the states are changed through a randomized process of some sort, is by a vector v of probabilities: the value v[x] represents the probability that X takes the state x for each binary string x of length k. The vector v is therefore a K-dimensional vector for K = 2^k.

In quantum information, the K-dimensional vector v of probabilities is replaced by a K × K matrix ρ with complex number entries, known as a density matrix. (It is traditional in quantum physics to use lower-case Greek letters, often ρ, σ, and ξ, to represent density matrices.) It is reasonable to view that the diagonal entries of a density matrix ρ represent probabilities, so that a "standard measurement" of the register X would yield each possible state x with probability ρ[x, x]. The off-diagonal entries of ρ are not easily connected to classical intuitions, but they do have great significance with respect to their role in calculations. Informally speaking, for distinct choices of binary strings x and y, the off-diagonal entries ρ[x, y] and ρ[y, x] provide information about the degree to which the states x and y are in "superposition" in X, or alternately the degree to which these states could interfere with one another in processes involving X.

Although they are not as intuitive as vectors of probabilities, density matrices are very simple objects in a mathematical sense: they are positive semidefinite matrices whose diagonal entries sum to 1 (i.e., whose trace is 1). A matrix ρ is positive semidefinite if and only if it satisfies (i) the condition that for all choices of x and y (with denoting the complex conjugate of α), and (ii) the constraint that all of its eigenvalues are nonnegative.

Quantum states of independent registers are represented by tensor products of density matrices. For instance, if X and Y are k-qubit registers independently prepared in the quantum states represented by the K × K density matrices σ and ξ, then the quantum state of the pair (X, Y) is described by the K² × K² density matrix

where the binary strings of length k indexing the entries of σ have been indicated by the integers they represent in binary notation.

Of course, not every state of a pair of registers (X, Y) can be expressed as a tensor product in this way, representing the fact that there may be dependencies between X and Y. Two such examples for the case k = 1 are the following density matrices:

The first density matrix ρ₀ represents a simple situation in which X and Y are randomly correlated: the two registers take the same state, chosen to be 0 or 1 uniformly at random. The second density matrix ρ₁ is similar to ρ₀ in the sense that it represents a joint state with a strong correlation between X and Y. It so happens, however, that the two non-zero off-diagonal entries endow ρ₁ with the characteristic of entanglement, which is one of the most remarkable features of quantum information. (Quantum teleportation⁴ provides a well-known example of the use of the entangled state ρ₁ as a resource in an information-processing task.)

For every possible quantum state of a pair of registers (X, Y), whether correlated or not, there is a uniquely determined reduced state of the register X that, in essence, would describe the state of X if Y were to suddenly be destroyed or lost. This is analogous to the marginal probability distribution of X in the probabilistic case. In mathematical terms the reduced state is defined by an operation known as the partial trace. If it is the case that the state of the pair (X, Y) is described by a K² × K² density matrix ρ, which may be written as a block matrix of the form

for K × K matrices M_{i, j}, then the K × K reduced density matrix for the register X is defined as

For the states ρ₀ and ρ₁ defined previously, for example, it holds that

One can consider other variants of this notion, such as one defining the reduced state of Y rather than X or one for the situation when X and Y have different sizes, but the case presented above is sufficient for the needs of this paper.

Now suppose one has a k-qubit register X in their possession, and that the state of X is described by the density matrix ρ. Much like the probabilistic case, there is a limit to the amount of information about ρ that can be gained by looking at a single copy of X. Any information must be obtained by a measurement, which will generally result in a probabilistic outcome.

In more precise terms, a measurement of X that results in one of the outcomes 0, 1,..., m - 1 (for some choice of m) is described by a collection of positive semidefinite matrices {Π₀, Π₁,..., Π_{m - 1}} that satisfy the condition Π₀ + ... + Π_m-1 = 1, where 1 represents the K × K identity matrix. Often the matrices Π₀,..., Π_m-1 are projection matrices, meaning that in addition to being positive semidefinite their only eigenvalues are 0 and 1. This is not a requirement, but every measurement considered in this paper may be assumed to have this property.

Now, when ρ is measured with respect to the measurement {Π₀,..., Π_m-1}, each outcome a {0,..., m - 1} is obtained with probability Trace(Π_aρ). The condition that ρ and Π_a are positive semidefinite implies that the resulting probabilities are nonnegative, and the conditions that Trace(ρ) = 1 and Π₀ + ... + Π_m-1 = 1 imply that the probabilities sum to 1. According to the simplest definition, the register X is destroyed by the act of measurement, so there is no opportunity to gain further information about ρ unless additional independent copies of it are made available.

One example of a measurement, referred to as the "standard measurement" in passing above, is obtained by taking m = K, associating the possible outcomes 0,..., K - 1 with the length k binary strings with respect to binary notation, and taking Π_x to be the matrix with a single 1 in the (x, x) diagonal entry and 0 for all other entries. As suggested before, this measurement results in each outcome x with probability ρ[x, x]. The measurements that will be of interest in this paper have a somewhat different nature, in that they are binary-valued measurements resulting from hypothetical quantum computations performed on registers. They are, nevertheless, still describable within the framework just explained.

One additional component of quantum information theory that has not been mentioned above is the description of transformations of quantum registers according to physical processes (such as computations). These changes are described mathematically by linear mappings known as channels, and are of great interest to the theory. It is, however, not necessary to make use of this notion in this paper, so it is not discussed further.

 2.2. Quantum interactive proofs simplified

Taken in its most general form, the quantum interactive proof system model can allow for complicated and mathematically unwieldy interactions involving the exchange of quantum messages over the course of many rounds. By the nature of quantum information, such an interaction cannot generally be described by the sort of game tree that describes a classical interaction—the possibility of entanglement among the prover, verifier, and message registers prohibits this.

It is, however, always possible^{9, 11} to transform a given quantum interactive proof system into one with the following conceptually simple form:

1. The prover sends the verifier a k-qubit register X, for some choice of a positive integer k—which must be polynomially related to the length of the input string x. Upon receiving X, the verifier sets it aside without interacting with it.
2. The verifier chooses a bit a {0, 1}, uniformly at random, and sends a to the prover.
3. The prover sends the verifier a second k-qubit register Y. The state of Y may of course be dependent on the random bit a, given that the prover learned a before sending Y to the verifier, but its correlation with X is limited by the fact that the prover did not have access to X after seeing a.
4. The verifier measures the pair (X, Y) with respect to one of two binary-outcome measurements: {Π⁰₀, Π⁰₁} in case a = 0 and {Π¹₀, Π¹₁} in case a = 1. The measurement outcome is interpreted as the verifier's output: 1 means the proof is accepted, 0 means it is rejected.

The verifier's measurements {Π⁰₀, Π¹₁} and {Π¹₀, Π¹₁} will, naturally, be dependent on the input string x to the decision problem under consideration. In accordance with the definition of the quantum interactive proof system model, these measurements must be efficiently implementable by a quantum computation to be performed by the verifier.

It is beyond the scope of this paper to describe how a general quantum interactive proof system can be transformed into one having the above form, but it is not overly complex. The transformation is such that the verifier's measurements can be forced to output 1 with certainty when the input is a yes-input, while the maximum probability for the output 1 can be made arbitrarily close to ½ when the input is a no-input. (More formally speaking, the transformation can guarantee a probability of at most ½ + ε for any fixed choice of a constant ε > 0.)

A common question about quantum interactive proof systems having the above form is this: Why cannot the prover simply prepare three registers X, Y₀, and Y₁, send all three to the verifier in a single message, and allow the verifier to measure (X, Y₀) or (X, Y₁) depending on its choice of the random bit a? This would seem to eliminate the need for interaction, as the verifier would never send anything to the prover. The reason is that entanglement prevents this from working: in order for the two measurements to result in the output 1 with high probability, the registers X and Y will generally need to be highly entangled. One of the curious features of entanglement, however, is that any single quantum register is highly constrained with respect to the degree of entanglement it may simultaneously share with two or more other registers. (This phenomenon was colorfully named the monogamy of entanglement by Charles Bennett.) Thus, again in the general case, the only way for the prover to cause the verifier to output 1 is to prepare X in a highly entangled state with a register of its own, and then use this entanglement to prepare Y once the random bit a has been received.

There are many strategies that a prover could potentially employ in an attempt to cause a verifier to output 1 in the type of proof system described above—but they can all be accounted for by considering the possible states of the pair (X, Y) that the verifier measures, conditioned on the two possible values of the random bit a. That is, for any two K² × K² density matrices ρ₀ and ρ₁, one may ask whether it is possible for the prover to follow a strategy that will leave the verifier with the state ρ₀ for the pair (X, Y) when the random bit takes the value a = 0, and with the state ρ₁ when a = 1; and the set of all possible such choices for ρ₀ and ρ₁ is simple to characterize. It is precisely the set of all K² × K² density matrices ρ₀ and ρ₁ for which

The necessity of this condition follows immediately from the fact that the prover cannot touch X at any point after learning a, while the sufficiency of the condition requires an analysis based on standard mathematical tools of quantum information theory.

It follows that the maximum probability for a prover to cause the verifier to output 1 in the type of proof system described above is the maximum of the quantity

subject to the conditions that ρ₀ and ρ₁ are K² × K² density matrices satisfying Equation 1.

Back to Top

3. PSPACE and Boolean Circuits

Based on the claims of the previous section, the characterization QIP = PSPACE follows from the existence of a polynomial-space algorithm for approximating the prover's optimal success probability in a quantum interactive proof system of the highly restricted form described above. The accuracy of this approximation may, in fact, be very coarse: it is only necessary for the algorithm to distinguish an optimal probability of 1 from one very close to ½.

The design of space-bounded algorithms is an unnatural task for most algorithm designers. When one cares only about space-efficiency, and not about time-efficiency, programming techniques that would be ridiculous in a practical situation become useful. For example, rather than storing bits used frequently in a given computation, one may instead opt to recompute and then discard those bits every time they are used. Taking such schemes to an extreme, it becomes possible to implicitly perform computations on numbers and matrices that are themselves exponentially larger than the total memory used for the entire computation.

Fortunately, in the late 1970s, Alan Borodin described a simple way to translate the task of highly space-efficient algorithm design into one that is arguably much more natural and intuitive for algorithm designers.⁵ For the particular case of PSPACE algorithms, Borodin's result states that a given decision problem is in PSPACE if and only if it can be computed by a collection of Boolean circuits having the form illustrated in Figure 1. The primary appeal of this reformulation is that it allows one to make use of extensive work on parallel algorithms for performing various computational tasks when designing PSPACE algorithms.

Now, the task at hand is to prove that any decision problem having a quantum interactive proof system can be decided by a family of polynomial-depth circuits. There is a natural two-stage process associated with this task that is illustrated in Figure 2. The first stage of this process turns out to be fairly straightforward, using elementary facts about quantum computations and bounded-depth circuits. The second stage is more difficult, and the algorithm for accomplishing it is representative of the main technical contribution of this work. The remainder of the paper is devoted to a discussion of this algorithm.

Back to Top

4. The Main Algorithm

The algorithm corresponding to the second stage of the computation illustrated in Figure 2 will now be described. As is required to prove QIP = PSPACE, it is a highly parallel algorithm for approximating the value of the optimization problem described at the end of Section 2. This optimization problem is an example of a semidefinite program (or SDP for short): it asks for the maximum value of a linear function of a collection of matrix variables that are subject to a collection of linear and positive semidefinite constraints.

SDPs are well studied and subject to an analytically powerful duality theory that will be useful in the section following this one. There do exist efficient algorithms to approximate solutions to most SDPs, including the theoretically important ellipsoid method and the more practical family of interior point methods. Unfortunately these algorithms do not parallelize, and there is a generally-believed complexity-theoretic conjecture (namely NC ≠ P) that implies that no other general and efficient algorithm will parallelize either: some SDPs seem to force algorithms that approximate them to be inherently sequential. For this reason, the algorithm to be presented below will, presumably by necessity, exploit the specific nature of the SDP at hand to allow for its parallelizability. It does not approximate solutions to general SDPs, only those arising from the specific type of quantum interactive proof system described in Section 2.

The algorithm employs a method from learning theory and combinatorial optimization sometimes known as the matrix multiplicative weights update method, and in particular makes use of a variant of this technique developed by Manfred Warmuth and Dima Kuzmin¹⁶ and Sanjeev Arora and Satyen Kale.¹

The algorithm is iterative in nature: for successive values of t = 0, 1, 2,..., the algorithm will generate K² × K² matrices σ^(t)₀ and σ^(t)₁ that, roughly speaking, correspond to guesses for ρ₀ and ρ₁ in the SDP. In addition, the algorithm also generates a K × K matrix σ^(t) for each t, which intuitively represents a common "target" state for

Like many iterative algorithms, there is a balance between the algorithm's rate of convergence and accuracy. It is essential for the parallelizability of the algorithm that ρ^(t)₀, ρ^(t)₁, and σ^(t) converge quickly to choices that reveal a near-optimal solution; but for the sake of the algorithm's accuracy it must not move too rapidly in any one direction, for fear of overreacting to poor choices that had the appearance of good ones within a small region of the search space.

To aid in this balance, it is helpful at a technical level to introduce two K² × K² penalty matrices

which have the effect of "inflating" density matrices ρ₀ and ρ₁ that would not yield a value of the objective function (2) close to 1. With a bit of algebra it can be shown that, for a sufficiently large value of α > 0, the optimal value of the original SDP will be close to the maximum value of

over all choices of positive semidefinite matrices Q₀ and Q₁, subject to the constraint that σ – PartialTrace (P₀Q₀P₀) and σ – PartialTrace (P₁Q₁P₁) are positive semidefinite for some choice of a density matrix σ. (The choice α = 4 happens to provide sufficient accuracy for the problem at hand.)

The input to the algorithm is the pair of K² × K² penalty matrices P₀ and P₁, which effectively specify the matrices Π⁰₀, Π⁰₁, Π¹₀, and Π¹₁. The algorithm also refers to constant values α = 4, γ = 4/3, ε = 1/64 and δ = ε/α², which, for the sake of clarity, are referred to by these names rather than their numerical values.

1. Set
     
     
     
     for 1 denoting the K × K identity matrix. (These matrices represent completely random quantum states, reflecting the fact that no information is present in the initial guesses for ρ₀, ρ₁, and σ.)
2. Set the maximum iteration number of the algorithm to
     
     
     
     and repeat the following steps for each t from 0 to T-1:
     
     (a) Compute the K × K matrices
     
     
     
     (b) Compute the K × K matrices Δ^(t)₀ and Δ^(t)₁ that project onto the negative eigenspaces of M^(t)₀ and M^(t)₁, respectively.
     
     (c) Compute
     
     
     
     and set then output 1 and stop.
     
     (d) Set
     
     
3. If the algorithm has not output 1 and stopped during any iteration of step 2(c), then output 0 and stop.

The correctness of the algorithm is certainly not obvious from its description, and is discussed in the section following this one. In addition to the algorithm's correctness, it is of course also necessary for it to have a highly parallel implementation. As the number of iterations is very small (at most O(log K), which is polynomially related to the problem size n), it suffices to observe that each iteration can itself be implemented by a highly parallel computation. This is possible through the use of known parallel algorithms for various matrix and algebraic problems.

Back to Top

5. Analysis of the Algorithm

 5.1. Intuition behind the algorithm

The SDP described in the previous section asks for the maximum trace of the average (Q₀ + Q₁)/2, over all positive semi-definite matrices Q₀ and Q₁ for which σ – PartialTrace (P₀Q₀P₀) and σ – PartialTrace (P₁Q₁P₁) are positive semidefinite—for some choice of a density matrix σ. While the formal analysis of the algorithm indeed makes use of the properties of this SDP, the algorithm itself is more naturally viewed as solving a feasibility problem.

In particular, for every iteration t the algorithm computes matrices ρ^(t)₀, ρ^(t)₁, and σ^(t) so that ρ^(t)₀ and ρ^(t)₀ have average trace equal to 1, but may fail to satisfy the constraint that

is positive semidefinite for b = 0, b = 1, or both. Successive iterations attempt to bring these matrices closer and closer to satisfying these constraints. If the constraints are "close enough" to being satisfied, the algorithm outputs 1, concluding that the optimal value of the SDP must be close to 1 by taking Q₀ and Q₁ close to ρ^(t)₀ and ρ^(t)₁. If the algorithm fails to make sufficient progress toward meeting the constraints, even after T iterations have passed, it outputs 0, concluding that the optimal value of the SDP cannot be close to 1.

Suppose, for a given iteration t, that the algorithm's current choices of ρ^(t)₀, ρ^(t)₁, and σ^(t) are far from satisfying the constraint (3) for b = 0, b = 1, or both. To be more precise, suppose that one of the matrices

fails to be positive semidefinite (for γ = 4/3). In this case, the subspace corresponding to the projection Δ^(t)_b onto the negative part of this matrix represents a part of the search space where ρ^(t)₀, ρ^(t)₁ and σ^(t) are inadequate: if progress toward meeting the constraints is to be made, σ must be made larger on this subspace while PartialTrace(P_bρ_bP_b) must be smaller.

In both cases, this modification is made by including an additional term in the argument to the matrix exponential that is normalized to produce the next iteration's choices ρ^(t+1)₀, ρ^(t+1)₁ and σ^(t+1). This has the effect of shifting the weight of ρ^(t)₀ and ρ^(t)₁ away from the parts of ρ^(t)₀, and ρ^(t)₁ that contributed to the constraint violations indicated by Δ^(t)₀, and Δ^(t)₁, respectively, and likewise shifting the weight of σ^(t+1) toward these parts of σ^(t). (A negative term in the exponential reduces weight while a positive term increases weight.)

 5.2. Comments on the formal algorithm analysis

That the algorithm works correctly is, of course, not as simple as the intuitive discussion above might suggest, due in large part to the complicated behavior of the exponential of a sum of matrices. A proper analysis of the algorithm is necessarily technical, and one can be found in the full version of this paper. This extended abstract will not present a detailed formal analysis, but will instead present just a high-level sketch of the analysis, intended only to provide the reader with its basic ideas.

A rigorous analysis of the algorithm makes use of the notion of semidefinite programming duality. Every semidefinite programming problem, stated as a maximization problem typically called the primal problem, has a corresponding dual problem, which is a minimization problem. The methodology for determining the dual problem corresponding to a given primal problem is standard, but will not be discussed here. Each possible value of the dual problem provides an upper bound on the optimal value of the primal problem.

For the particular SDP at hand, the dual problem is to minimize the largest eigenvalue of the average ½ R₀ + ½ R₁, over all K × K positive semidefinite matrices R₀ and R₁ obeying the constraint that every eigenvalue of P₀(R₀ ⊗ 1)P₀ and P₁(R₁ ⊗ 1)P₁ is at least 1, or equivalently that the matrices

are both positive semidefinite. (As before, 1 denotes the K × K identity matrix.)

The analysis works by constructing solutions to either the primal problem or dual problem based on the behavior of the algorithm, guaranteeing its correctness under the assumption that the optimal value of the primal problem is either very close to 1 or to ½.

The simpler case is that the algorithm outputs 1. This must happen during some particular iteration t, and for this choice of t one may consider the matrices

For an appropriate choice of σ, which can be constructed from ρ^(t)₀, ρ^(t)₁, σ^(t), Δ^(t)₀, Δ^(t)₁ and β^(t), it holds that both σ – PartialTrace (P₀Q₀P₀) and σ – PartialTrace (P₁Q₁P₁) are positive semidefinite. The trace of the average of Q₀ and Q₁ is at least 1/(γ + 4ε) > 5/8. It follows that the optimal value of the primal problem cannot be too close to ½, so it is necessarily close to 1.

The more difficult case is that the algorithm outputs 0. In this case, the matrices

form a solution to the dual problem satisfying the required constraints and achieving a value smaller than 7/8. Establishing that these matrices indeed satisfy the required constraints and achieve a value smaller than 7/8 is somewhat technical, but follows from a basic methodology that appeared in previous works (including Warmuth and Kuzmin¹⁶ and Arora and Kale¹). With a value of at most 7/8 for the dual problem, the same value has been established as an upper-bound for the primal problem. It follows that the optimal value for the primal problem is sufficiently far from 1 that it must be close to ½.

There is a small complication in the formal analysis that does not present a major obstacle, but is nevertheless worthy of note. The complication is that the algorithm cannot perform all of the required computations exactly, but must approximate some of them. (In particular, the matrix exponentials and the negative eigenspace projections can only be approximated, albeit with very high accuracy.) A slight modification of the analysis sketched above demonstrates, however, that the algorithm is not particularly sensitive to errors. The steps of the computation may, in fact, be performed with significantly less accuracy than is possible within the resource constraints required of the algorithm.

Back to Top

6. Conclusion

The characterization QIP = PSPACE implies that quantum computation does not provide an increase in the expressive power of interactive proof systems. It is tempting to view this fact as a negative result for quantum computing, but this view is not well justified. What is most interesting about quantum computation is its potential in a standard computational setting, where an algorithm (deterministic, probabilistic, or quantum) receives an input and produces an output in isolation, as opposed to through an interaction with a hypothetical prover. The main result of this paper has no implications to this fundamental question. A more defensible explanation for the equivalence of quantum and classical computing in the interactive proof system model is the model's vast computational power: all of PSPACE. That such power washes away the difference between quantum and classical computing is, in retrospect, perhaps not unexpected.

One future research direction that is clearly suggested by this paper is: what class of SDPs can be solved approximately by parallel algorithms? We do not have an answer to this question, and believe it is certainly deserving of further investigation. There are, in addition, still many open questions relating to variants of quantum interactive proof systems—the most notable being the multiprover quantum interactive proof system model. This model is, in fact, currently so poorly understood that it is not even known if every problem having a multiprover quantum interactive proof system is necessarily decidable.

Back to Top

Back to Top

Back to Top

Back to Top

Back to top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.

---

No entries found