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.

2. Quan Tum 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, 12 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 = 2k.

In quantum information, the K-dimensional vector v of probabilities is replaced by a K × K matrix r with complex number entries, known as a density matrix. (It is traditional in quantum physics to use lower-case Greek letters, often r, s, and x, to represent density matrices.) It is reasonable to view that the diagonal entries of a density matrix r represent probabilities, so that a “standard measurement” of the register X would yield each possible state x with probability r[x, x]. The off-diagonal entries of r 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 r[x, y] and r[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 r is positive semidefinite if and only if it satisfies (i) the condition that r[x, y] = r[ y, x] for all choices of x and y (with a denoting the complex conjugate of a), 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 s and x, then the quantum state of the pair (X, Y) is described by the K 2 × K 2 density matrix where the binary strings of length k indexing the entries of s have been indicated by the integers they represent in binary notation.