guarantee a probability of at most 1/2 + e for any fixed choice
of a constant e > 0.)
A common question about quantum interactive proof
systems having the above form is this: Why cannot the
prover simply prepare three registers X, Y0, and Y1, send all
three to the verifier in a single message, and allow the verifier to measure (X, Y0) or (X, Y1) 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 pos-
sible values of the random bit a. That is, for any two K2 × K 2
density matrices r0 and r1, one may ask whether it is possi-
ble for the prover to follow a strategy that will leave the veri-
fier with the state r0 for the pair (X, Y) when the random bit
takes the value a = 0, and with the state r1 when a = 1; and the
set of all possible such choices for r0 and r1 is simple to char-
acterize. It is precisely the set of all K2 × K 2 density matrices
r0 and r1 for which
Partial Trace(r0) = Partial Trace(r1).
( 1)
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
1
–
2
Trace (∏01r0) + 1– 2 Trace (∏11r1) ( 2)
subject to the conditions that r0 and r1 are K 2 × K 2 density
matrices satisfying Equation 1.
3. PSPaCE anD BooLEan CiRCui TS
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 1/2.
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. 5 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
figure 1. a decision problem is solvable in polynomial space if and
only if it can be computed by a family of Boolean circuits, one for
each input length n, whose size may be exponential in n but whose
depth is polynomial in n. (The circuits must also satisfy a uniformity
constraint that limits the computational difficulty of computing each
circuit’s description.)
Problem input (n bits)
exponentially large
Boolean circuit C
Depth
polynomial
in n
Problem output ( 1 bit)
Problem input (n bits)
figure 2. an illustration of the two-stage process for solving any
problem in QiP by a bounded-depth Boolean circuit. The circuit C1
transforms the input string into an exponentially large description
of the verifier’s measurements {P00, P01} and {P10, P1 1}, and the circuit
C2 implements a parallel algorithm for approximating the optimal
value of the associated optimization problem.
C1
Description of {Π00, Π10} and {Π01, Π11}
C2