assumption that the optimal value of the primal problem is
either very close to 1 or to 1/2.
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 s, which can be constructed
from r(t) 0, r(t) 1, s (t), ∆(t) 0, ∆(t) 1 and b (t), it holds that both s –
Partial Trace (P0Q0P0) and s – Partial Trace (P1Q1P1) are positive semidefinite. The trace of the average of Q0 and Q1 is at
least 1/(g + 4e) > 5/8. It follows that the optimal value of the
primal problem cannot be too close to 1/2, so it is necessarily close to 1.
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 isola-
tion, as opposed to through an interaction with a hypotheti-
cal 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 com-
putational power: all of PSPACE. That such power washes
away the difference between quantum and classical comput-
ing is, in retrospect, perhaps not unexpected.
References
1. arora, S., Kale, S. a combinatorial,
primal-dual approach to semidefinite
programs. in Proceedings of the 39th
Annual ACM Symposium on Theory
of Computing (2007), 227–236.
2. babai, l. trading group theory for
randomness. in Proceedings of the
17th Annual ACM Symposium on
Theory of Computing (1985), 421–429.
3. bennett, C., brassard, g. Quantum
cryptography: public key distribution
and coin tossing. in Proceedings of
the IEEE International Conference
on Computers, Systems, and Signal
Processing (1984), 175–179.
4. bennett, C., brassard, g., Crépeau,
C., jozsa, r., peres, a., Wootters, W.
teleporting an unknown quantum
state via dual classical and epr
channels. Phys. Rev. Lett. 70, 12
(1993), 1895–1899.
5. borodin, a. on relating time and space
to size and depth. SIAM J. Comput. 6
(1977), 733–744.
6. deutsch, d. Quantum theory, the
Church–turing principle and the
universal quantum computer. Proc.
R. Soc. Lond. A400 (1985), 97–117.
7. Feynman, r. Simulating physics with
computers. Int. J. Theor. Phys. 21, 6/7
(1982), 467–488.
8. goldwasser, S., micali, S., rackoff,
C. the knowledge complexity of
interactive proof systems. SIAM
J. Comput., 18, 1 (1989), 186–208.
a preliminary version appeared in
Proceedings of the 17th Annual ACM
Symposium on Theory of Computing
(1985), 291–304.
9. Kitaev, a., Watrous, j. parallelization,
amplification, and exponential time
simulation of quantum interactive
proof system. in Proceedings of
the 32nd Annual ACM Symposium
on Theory of Computing (2000),
608–617.
10. lund, C., Fortnow, l., Karloff, h.,
nisan, n. algebraic methods for
interactive proof systems. J. ACM
39, 4 (1992), 859–868. a preliminary
version appeared in Proceedings of
the 31st Annual IEEE Symposium
on Foundations of Computer Science
(1990), 2–10.
Rahul Jain, department of Computer
Science and Centre for Quantum
technologies, national University of
Singapore, republic of Singapore.
Zhengfeng Ji, perimeter institute for theoretical physics, Waterloo, ontario, Canada.
Sarvagya Upadhyay and John
Watrous, institute for Quantum
Computing and School of Computer
Science, University of Waterloo
Waterloo, ontario, Canada.
