Evidence supporting quantum information processing in animals

              Evidence supporting quantum

           information processing in animals


                   James A. Donald

                   1068 Fulton Av
                   Sunnyvale, CA 94089-1505
                   USA


I show that quantum systems can rapidly solve some
problems for which finite state machines require a non-
polynomially large time. This class of problems is
closely related to the class of problems that animals
can solve rapidly and effortlessly, but are intractable
for computers by all known algorithms.



1. Introduction
     Animals, including very simple animals, can
rapidly and effortlessly perceive objects, whereas
computers take nonpolynomial time to do this by all
known algorithms [1, 2, 3, 4, 5, 6]. Our persistent
inability to emulate perception gives reason to doubt
the current paradigm and to look for an alternative
paradigm.
     Penrose[7] and many others [8, 9, 10] argue from
practical considerations, Godel's theorem, and on
philosophical grounds, that consciousness or awareness
is non-algorithmic and so cannot be generated by a
system that can be described by classical physics, such
as a conventional computer, but could perhaps be
generated by a system requiring a quantum (Hilbert
space) description. Penrose suspects that aspects of
quantum physics not yet understood might be needed to
explain consciousness. In this paper we shall see that
only known quantum physics is needed to explain
perception.
     Bialek[11, 12] and Frolich[13] suggested on very
different grounds that cells process information using
quantum mechanical processes. Frolich suggested a class
of mechanisms that might enable them to do this despite
the high temperature and large size of biological
membranes and macromolecules. Deutch[14] showed that
quantum systems can solve some problems that computers
cannot solve in polynomial time, but he did not show
that quantum systems could solve perception problems.
Penrose[7] conjectured that some areas where animals
are superior to computers are of this class, but did
not find any examples. Bialek[15] argued that
perception is inherently non-polynomial if done
algorithmically, and therefore neurons must be doing
something remarkable, but he did not show that quantum
mechanics would enable them to do this.
     This paper will show that quantum systems can also
rapidly solve perception problems, closing the gap
between Bialek's argument and Deutch's result, and
demonstrating Penrose's conjecture. This result
supports the idea that animals perceive by processing
sensory information quantum mechanically in hilbert
spaces corresponding to many strongly coupled degrees
of freedom.

2. The Perception Problem
     Perception is the problem of inferring the
external world from immediate sensory data by finding
instances of known categories such that they would
generate the immediate sensory data. Animals do this
very well, and, for perception problems that only
require recognizing objects as instances of innate
categories rather than learnt categories, animals with
very simple nervous systems sometimes perceive almost
as well as animals with complex nervous systems such as
ourselves, and perhaps better in some cases and some
circumstances. Indeed animals do this so well and so
effortlessly that people only began to recognize that
there was a problem to be solved when we attempted to
program computers to perceive.
     The fact that animals perceive effortlessly has
lead to a widespread belief that some polynomial time
algorithm must exist, yet no significant progress has
been made in the search for an efficient perception
algorithm.
     A number of perception problems have been studied
very thoroughly, in particular the target acquisition
problem in radar and sonar, and the visual problem of
inferring objects from two dimensional data.
     An algorithm that could perceive in polynomial
time is called direct perception (DP), or bottom up
perception. Such algorithms unsuccessfully attempt to
construct object descriptions (top level) from
immediate data (bottom level). The algorithms that do
work are called indirect perception (IP), or top down
perception. Such algorithms start at the top level
(objects) and search for a match with the immediate
data. Such algorithms take non-polynomial time [2, 3],
for they must try an non-polynomial number of object
hypotheses.
     Many top down algorithms are not strictly top down -
they start from both top and bottom and look for a
match in the middle, but this does not change the
character of the algorithm.
     Bottom up algorithms do not work. Ullman[16] gives
examples of situations where perception must be purely
top down because all local or explicit information is
suppressed, scrambled or misleading, so that bottom up
processing has nothing to start from. Gregory[17], made
the same argument long before these acronyms were
coined, using the example of a dalmatian against a
background of spots. In Gregory's lucid terminology we
perceive by forming object hypotheses that fit the
data.
     Kanade[5] showed that when we attempt to
generalize the polyhedral labeling problem it no longer
has a unique solution. (The polyhedral labeling problem
is a special case of the problem of forming a 2 1/2 D
image, which is the problem of identifying contours in
an image and labeling them as silhouette, convex,
concave, groove, or mere change in surface albedo.) His
result means that even when there is local and explicit
data in an image, this is not sufficient to form a
visual perception. You also need knowledge of what
objects are likely. This led him to perform the
negative chair experiment: He constructed an unlikely
unfamiliar object and had people look at it. They
misperceived it even though it was right in front of
them. This experiment showed that not only is light and
shade insufficient in itself to construct 3D or 2 1/2 D
descriptions of the image, but even with small angle
stereoscopic and small angle apparent motion data, it
is still insufficient. Object perception is primary. We
do not see three dimensionally and infer objects from
the three dimensional information. We do not see what
we think we see - we perceive it by forming hypotheses.
Gregory[17] made the same argument using the example of
reversed masks, but many people argued that this was a
special case. Kanade[5] showed the same phenomenon
occurs with any complex object. This shows that it is
pointless to do anything elaborate to the immediate
data without an object hypothesis.
     The results for the target acquisition problem are
similar to the visual perception problem: If the target
and background signals are comparable then the only way
to extract the target signal is to find the correct
object hypothesis. You cannot find the correct object
hypothesis by extracting the target signal first. This
is a tractable problem if you are only interested in a
single class of objects with a single orientation, for
example a specific type of interceptor on an intercept
course at full speed, but it is an intractable problem
if you are interested in many different possible
targets that can be travelling in many different
possible directions at many different speeds, with
several similar moving objects present at once, and
several similar interfering radars, yet bats solve this
problem with the effortless rapidity that animals
always show when using their most important senses for
normal survival purposes.

3. Quantum Solution
     All computer programs that successfully solve non-
trivial perception problems have as their hard step a
search for the global minimum of a function. This works
for an artificially simple microworld [4], and it also
works when the categories consist of a short list of
rigid objects with only two degrees of freedom in their
position and one degree of freedom in their orientation
[18], but if we allow irregular and elastic categories
with many internal variables, such as occur in the real
world, then the dimension of the space becomes much too
large for exhaustive search (the combinatorial
explosion, [6]).
     In some areas of AI, such as chess, search is an
acceptable algorithm because we merely want a good
sequence, not the best sequence, and this can be
achieved in polynomial time, but in perception we want
the right object hypothesis, not merely a good object
hypothesis.
     Thus the problem of perceiving efficiently is
equivalent to the problem of efficiently minimizing a
class of many variable functions. Almost everyone who
has confronted this problem has argued, from the fact
that animals perceive rapidly, that it must be
sufficient to find a good minimum, not the global
minimum, but it all cases tried so far, algorithms that
stop before finding the global minimum have been
unsuccessful, as one would expect from the nature of
the problem.
     Any classical system performing such a
minimization can only sample the system locally in
phase space, thus if the function is irregular and
general the system must find a non-polynomially large
number of local minima before it finds the global
minimum. This the reason why a chess playing computer
must explicitly generate an enormous number of
sequences and evaluate each one, and a perceiving
computer must explicitly generate a non-polynomially
large number of object hypotheses and evaluate each
one, but this is not how we play chess and this is not
how we perceive.
     If the function to be minimized is completely
general then the problem is non-polynomial (NP)
complete. It is likely that animals and computers are
both equally incapable of solving large NP complete
problems. This leads us to expect that the class of
functions corresponding to the class of perception
problems is not general, but has some special property
that enables animals to get a handle on it.
     We shall see that the perception problem
corresponds to the problem of finding the global
minimum of a function of many variables, where the
global minimum is much deeper than any other minimum.
     One may easily show that a quantum system with a
potential corresponding to such a function may be
rapidly brought to the ground state by cooling where
the ground state is not localized, followed by
adiabatic cooling so that the ground state becomes
substantially localized in the well containing the
global minimum, whereas a classical system with the
corresponding hamiltonian requires nonpolynomially
large time to reach the corresponding ground state by
cooling; for a classical system the ground state is
always localized in the well so the system will rattle
randomly from one local minimum to another, until it
finally hits the well containing the global minimum;
the number of local minima will be exponential in the
number of degrees of freedom.
     For this to work in polynomial time the momentum
terms in the initial hamiltonian must be large enough
relative to the potential terms to prevent substantial
localization, which requires that the significant
degrees of freedom of the system be initially far in
the quantum domain. The change in state will remain
adiabatic during the change in hamiltonian if the local
minima are sufficiently shallow relative to the global
minimum that the ground state is not significantly
localized in local minima during the change.
     We can deduce that the global minimum is much
deeper than any local minimum from the way in which
these functions are constructed.
     The function to be minimized is a measure of the
discrepancy between the perception and the immediate
sensory data. We wish to minimize the function with
respect to a set of variables that constitute a parse
tree describing the external world assumed to be
generating the immediate data (the object hypothesis).
The grammar of the parse tree is a model of the world
and the way in which the world interacts with the
senses. There will be a single deep well because the
immediate data has much higher apparent entropy than
the parse tree data. In other words the immediate data
is not noise, it has internal consistency in that it is
capable of being generated from a much smaller parse
tree. Conversely, if the immediate data was
indistinguishable from noise, there would be no
dominant global well. The probability that a second
dissimilar parse tree will have a comparably good fit
to the data varies exponentially with the difference
between the apparent entropies of the parse tree and
the immediate data.
     This result is also supported by the fact that
programs that truncate their search produce flagrant
errors, suggesting that almost right interpretations
are rare, and by the fact that genuinely ambiguous
images (images with two distinct interpretations)
seldom occur in nature but only occur when contrived by
artists, indicating that cases where the two deepest
wells are of comparable depth are very rare in nature.
(We can ignore the very common case - fitting a
stimulus of small apparent entropy, for example a
Rorschach blot, with a complex perception.)

4. Objections
     Many people have vigorously argued that the brain
is too warm and wet, macromolecules too large, heavy,
and slow, for living things to process information
quantum mechanically.
     The mechanism I have described (adiabatically
cooling the ground state) is an equilibrium mechanism
that can only work for very small systems or at very
low temperatures. There are however a few small
loopholes in this argument:
_ Although deviations from classical trajectories
usually decline rapidly with the size of the system, in
systems far from equilibrium deviations from the
probabilities that one would expect from classical
local causality decline much more slowly, for example
the quantum scar effect [19]. (These deviations are
what is needed to process information quantum
mechanically in ways that have no classical equivalent,
rather than deviations from the classical
trajectories.)
_ Finding a short unstable closed cycle in a many
variable chaotic system is (like finding the minimum
energy) also an NP problem, but in phase space rather
than coordinate space. Such trajectories are
distinguished quantum mechanically [19], but they are
not distinguished classically.
_ Quantum effects tend to increase with the number
of coupled degrees of freedom. Also systems with more
coupled degrees of freedom tend to contradict classical
causality in a stronger and more direct fashion.
Frolich proposes a very large number of redundant
degrees of freedom, moderately driven from equilibrium.
Bialek proposes a moderate number of degrees of
freedom, very strongly driven.
_ Although macromolecules are too large and
heavy, their electrons are not. In macromolecules
containing many highly polarizable groups the groups
will have energy eigenstates where the relative
polarizations have substantial non-local correlations.
The relative polarization state will effect the way in
which such molecules cleave - one method by which cells
process information is by cleaving and joining RNA
chains. Another possibility is that unstable
macromolecules with highly conjugated electron
structures are synthesized on cell membranes by the
oxidative polymerization of serotonin, although no such
molecules have been found in biological systems.

5. Predictions
     The theoretical results of this paper lead me to
make an experimental prediction: I predict that
perception neurons proceed in one large indivisible
step directly from low level inputs to high level
outputs; for example the inputs for a "face of social
superior"[20, 21] neuron would be pixel neurons, edge
detection neurons, and similarly low level feature
detectors. This prediction is hard to test directly
because neurons with high level outputs have vast
numbers of diverse inputs and it is difficult to
determine what most of these inputs signify. But from
this prediction flow some predictions that are easier
to test:
_ Neurons that generate high level perceptions will
be located in regions well supplied with low level
data. The neural net model would lead us to expect some
physical separation between low level inputs and high
level outputs, contrary to observation [20, 21].
_ Plausible intermediate level outputs will be rare
or nonexistent. For example Kendrick[20, 21] found many
neurons that respond only to faces, but none that
respond only to frontal or only to profile views of
faces, and none that respond to specific distinguishing
features of faces, neurons that respond to heads with
horns but none that respond to horns in isolation from
a head.
_ Neurons that originate high level outputs will
have star rather than tree topology because each low
level input is only significant in the context provided
by most of the other distinct and separate low level
inputs
_ The delay between low level inputs stabilizing and
high level output starting will often be very short,
making it implausible that there is any neural net
generating essential intermediate level inputs.
_ Many of the inputs will be low level. Observation
of some low level inputs would not disprove all
possible neural net models, since such an observation
would not prove that intermediate level inputs were
inessential, but it would disprove all simple standard
neural net models which assume that a neurons output
frequency is a simple function of its inputs, e.g. a
weighted sum of inputs or a weighted sum of low order
products of inputs.

References
[1] S. Conner, New Scientist 121 No. 1648 (1989) 68
[2] J.K. Tsotsos, in: IEEE First International
    Conference on Computer Vision, IEEE Computer society
    press, Washington DC 1987) p. 346
[3] L.M. Kirousis & C.H. Papadimitriou, in: 26th
    Annual Symposium on Foundations of computer Science,
    Portland Oregon, 1985) p.175
[4] T. Kanade, Artificial Intelligence, 13 (1980) 279
[5] T. Kanade, Artificial Intelligence, 17 (1981) 409
[6] M.J. Lighthill in: Artificial Intelligence, a
    paper symposium, SRC report, Science research
    council, London (1973) p1
[7] R. Penrose, The Emperors New Mind, (Oxford
    University press, 1989)
[8] M. Lockwood, Mind Brain and the Quantum, (Basil
    Blackwell Inc, Oxford, 1989) p.240
[9] I.N. Marshall, New Ideas in Psychology, 7 (1989) 73
[10] C.I.J.M. Stuart, Y. Takahashi, H. Umezawa,
    Foundations of Physics, 9 (1979) 301
[11] W. Bialek and A. Sweitzer, Phys. Rev. Lett. 54
    (1986) 725
[12] W. Bialek, Phys. Rev. Lett., 56 (1986) 996
[13] H. Frolich, Physics Letters, 110A (1985) 480
[14] D. Deutch, Proc. Roy. Soc. (Lond.), A400, (1985) 97
[15] W. Bialek, Phys. Rev. Lett., 58 (1987) 741
[16] S. Ullman, Behavioral & brain Sciences, 3 (1980) 373
[17] R.L. Gregory, The Intelligent Eye (McGraw Hill,
    San Francisco 1970) p. 57
[18] W.E.L Grimson, Object Recognition by Computer,
    (MIT Press 1990)
[19] R.V. Jensen & M.M. Sanders, Phys. Rev. Lett., 63
    (1989) 2771
[20] K.M. Kendrick, Science, 236 no 4800 (1987) 448
[21] K.M. Kendrick, New Scientist, 126 No. 1716 (1990) 62