Applications and the Future - Codes: The Guide to Secrecy from Ancient to Modern Times - page 370

Quantum Computing
The conventional digital computers, with which we are familiar, use bits,
0 and 1, to represent information. Moreover, after each execution, the digital
computer has a definite, precisely measurable state; all the bits are either 0
or 1 but not both. A (as yet still hypothetical) quantum computer is a quan-
tum analogue of a digital computer, that operates with quantum bits involving
quantum states. A quantum bit is also called a qubit , which may be represented
as a (unit) vector in a sphere, where

↑ represents 1, and ↓ represents 0. Any

orientations in between such as represents the angle with the vertical

axis as a measure of the “0-to-1”-ness of the qubit. Thus, unlike classical bits,
a qubit may posses several states at once. The input and output qubits can
be linear combinations of basic states, so that the quantum computer functions
on all basic states in the linear combinations simultaneously. Hence, a quan-
tum computer is essentially a massively parallel computer. This means that (if
one were ever built), it would outperform all classical computers, and would
make classical cryptography obsolete. For example RSA could be broken. Even
though a quantum computer, per se, does not yet exist, factoring methods for
one have been developed. In [252], Shor 9.36 presented a polynomial time quan-
tum algorithm for factoring large integers. He used the quantum property called
interference , which is the feature of quantum mechanics that dictates that the
outcome of a general quantum process is dependent upon all possible histories of
that process. Interference makes quantum computers qualitatively more power-
ful than classical ones, because quantum interference can occur whenever there
exists more than one method for obtaininga specific result.
In 1993, the authors of [21] showed how to teleport the quantum state of
an object, meaningthat they presented a scheme for transportingfrom one lo-
cation to another without passingthrouh the distance between them. They
used the notion of entangled states (or entanglement ), which refers to the quan-
tum fact that the properties of a composite system, even when the components
are distant and noninteracting, cannot be fully expressed by descriptions of the
properties of all the component systems. Entanglement is the feature of quan-
tum mechanics that makes quantum cryptography possible. Hence, with this
scenario, quantum cryptography employing quantum computers would involve
encipheringqubits usingquantum states and teleportingthose quantum states
from one quantum computer to another without havingto pass through an unse-
cured channel. Although prototypes exist, the construction of a general-purpose
quantum computer seems infeasible at this time. Yet, it might be possible to
construct a special-purpose quantum factoringmachine. After all, Shor has
shown us how to use quantum computers to break classical cryptosystems, such
as RSA, based on factoring, since his technique reduces the factoring of very
large composite numbers to the comparable triviality of multiplying.

and

9.36 Peter Shor was born August 14, 1959. He obtained his Ph.D. at MIT, and after a brief
stint at the Mathematics Research Center in Berkeley, California, as a postdoctoral fellow, he
joined AT&T in 1986. He is currently a mathematician at the AT&T Research Laboratories in
Florham Park, New Jersey. His work on quantum factoring earned him the 1998 Nevanlinna
Prize at the International Congress of Mathematicians in Berlin.