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.