Communications - December 2010

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.