QM in computing
Levin
mathematicians and physicists. Recently a specific model, BQP, has
been under much discussion. It allows polynomial time computations
employing quantum effects with some idealizations: arbitrary
hamiltonian, zero dissipation, perfect isolation, etc.
It was, however, hard to demonstrate that it can or cannot be
implemented without any resource (e.g. energy) becoming exponential.
A significant hint was recently given by Peter Shor. He proved that
implementing BQP must be at least as hard as doing factoring and
discrete log. These two problems are the most famous examples of
computational tasks believed to be intractable. Much of modern
cryptography is based on the assumption of their intractability.
Impressive as it is, Shor's theorem does not prove, however, that
implementing BQP requires exponential resources, nor even hints WHICH
resource (energy, entropy, or what?) would be non-polynomial. After
all, factoring MAY turned out to be easy. It would be much more
enlightening to prove directly that implementing BQP does (or does
not) require exponential resources.
It is clear what would constitute the optimistic answer: just build
the damn machine or give a plan with only those obstacles which are
pure engineering. It is harder to state what would be a pessimistic
answer: we do not know much of physics (quantum gravity, exotic
particles, etc.). How can one prove that the unknown physics offers
no tools to implement BQP with polynomial resources?
I think, however, unknown physics can be just ignored in answering the
question. Consider a system of non-relativistic point-like electrons
and nuclei with only electro-magnetic quantum interaction. (All other
interactions are anyway illegal in Cambridge Massachusetts under its
anti-nuclear ordinance.) Without fancier physics and cosmology we
cannot provide a stable source of light or a heat sink, but these can
be taken as a boundary condition. Proving that a BQP built of such
elements can be overpowered by a probabilistic polynomial time Turing
Machine would remove all curiosity I have in the matter.
On the other hand, one could try the opposite: to show that BQP is
implementable. One would have to demonstrate that interaction with a
thermal environment does not cause drastic decoherence or other
disasters; that an arbitrary (or the one actually used) hamiltonian
can be approximated sufficiently close by Coulomb force, and things
like that. (Not everything can be approximated by everything: e.g.,
polynomials cannot approximate the conjugation of complex numbers.)
So, does somebody have some answers or insights? With many thanks,
-Leonid Levin.
PS. I have similar questions about the possibility to perform
reversible computations while dissipating << kT of energy per bit
operation. But BQP is more dramatic, so more chances that somebody
would bother to answer.