Quantum information and computation theory has become a
fast-growing, if
not all-too-hot field of research, linking quantum optics,
foundations of
quantum physics with recursive function theory, computational
complexity
theory and algorithmic information theory. It utilizes the
"bizarre,
mindboggling" features encountered in the quantum domain. One of
the attempts is directed towards a speedup of computation due to
quantum
parallelism. Another application is quantum cryptography, making use
of
complementarity.
The following features are important, but not sufficient qualities of
quantum computers.
- Input, output, program and memory are qbits.
- Any
computation (step) can be represented by a unitary transformation of
the computer as a whole.
- Any computation is reversible. Because
of the unitarity of the quantum
evolution operator, a deterministic computation can be
performed by a quantum computer if and only if it is reversible,
i.e., if
the program does not involve "deletion" of information or
"many-to-one" operations. Only one-to-one operations are
allowed. Compared
to classical irreversible computation, this may result in a space
and time overheads. Furthermore, no "one-to-many"
operations are allowed.
Thus, unless classical, qbits cannot be copied.
- Unless
classical,qbits are context-dependent. That is, their value may
depend on the method by which they have
been inferred, and on the
co-measured
qbits.
- Measurements may be carried out on any qbit at any stage
of the
computation. But, unless classical, a qbit cannot be measured by a
single
experiment with arbitrary accuracy. The computation process and the
measurement have to be repeated in order to obtain sufficient
statistics. Any such single measurement will yield merely a
"click" on
some counter, from which information about the qbit state must be
inferred. Thereby, any single measurement is indeterminate and
coherence
is destroyed. Therefore, it seems more proper to realize that there
is no
such operational concept of "a single qbit." Because of
complementarity,
single qbits cannot be determined precisely. What is henceforth
called
"determination" or "measurement" of a qbit is, in
effect,
the observation of a successive number of such qbits, one after the
other,
from "similar" computation processes (same preparation,
same evolution).
By performing these measurements on "similar" qbits, one
can "determine"
this qbit within an epsilon-neighborhood only. The parameter epsilon
depends on
the number of successive measurements made.
- Quantum parallelism:
during a computation (step), a quantum computer
proceeds down all coherent paths at once. If managed properly, this
may
give rise to speedups.
- Any subroutine must not leave around any
qbits beyond it's computed
answer, because the computational paths with different residual
information can no longer interfere.
In order to appreciate quantum computation, one should make proper
use of
the above features--quantum parallelism, unerasability of
information, non-copying, context-dependence and impossibility to
directly measure the atoms of quantum information, the qbits, related
to
quantum indeterminism.
Smolin's
collection of manuscripts
Shor's paper
Svozil's
review paper