May Edition
After we
saw
several randomized algorithms for primality we needed a way to
classify and analyze the power of probabilistic computation. The power
of computational complexity comes from not just studying old models of
computation but taking new ones and finding ways to analyze their
computational power as well.
Computational Complexity of Probabilistic Turing Machines, John Gill, STOC 1974,
SICOMP 1977.
A Complexity
Theoretic Approach to Randomness, Michael Sipser, STOC 1983.
Gill gave a formal definition of a probabilistic Turing machine and
defined the basic classes,
PP,
BPP,
RP
(which Gill called VPP) and
ZPP and
showed the basic relationships between them.
Sipser's main result showed the BPP is contained in the
fourth level of the polynomial-time hierarchy and the paper also
includes Gács improvement putting BPP in
Σ
2∩Π
2. More importantly Sipser
introduced new techniques into the complexity theorists' toolbox including
- A new resource-bounded Kolmogorov
distinguishing complexity, and
- Using Carter-Wegman hash functions to focus randomness. Perhaps
the first extractor.
Sipser's tools go on to play an important role in the complexity of
Arthur-Merlin games, graph isomorphism, statistical zero-knowledge and
other areas of complexity. But perhaps most importantly Sipser
showed you can apply the tools of complexity to really understand the power a
new model of computation, the probabilistic machine.
How about that newer model of a quantum computer? Bernstein and
Vazirani's
paper plays
the Gill role, in formalizing efficient quantum computation and
definining the basic classes like
BQP. But
while we have had some limited success in understanding the computational
complexity of BQP, not only do we not know whether BQP is contained in
the polynomial-hierarchy we have not yet developed great tools for
understanding "quantumness" the way Sipser has shown we can
do for randomness.
Quantum computing seems to be rich in new algorithmic ideas, but it also seems somewhat 'orthogonal' to much of existing complexity theory, e.g. is difficult to relate to the polynomial hierarchy.
ReplyDeleteSo, could QC inspire other models that don't share its physical plausibility but that have more use to classical complexity theory? This by way of analogy with PP, which isn't what one 'had in mind' for randomized algs but is nevertheless an upstanding complexity class.
As one example of what I'm thinking of, Scott Aaronson (quant-ph/0402095) shows you can solve NP-hard problems in BQP if you throw in some nonlinearity into QM. And there are others; I'm just wondering if this envelope could still be pushed.