Cryptography Reference
In-Depth Information
or 1); it works with probabilities. The last point above suggested this. It is hard
to imagine in everyday life that something can have several states concurrently,
based on a certain probability distribution.
But there are more inconceivable things: quantum particles can be in super-
position to one another so that they are no longer independent. This is called
quantum entanglement
. If you influence one of these entangled quantum parti-
cles, you also influence all others concurrently rather than with a minimal delay.
It is easier to describe it mathematically (though complicated) than trying to
imagine it.
All of this has been known since about 1920 and can be described by quantum
mechanics. But around 1980, Bennett, Benioff, and Feynman hit upon the idea
that one could build a computer on that basis. This computer would look totally
different from the computers we are used to today, and it would also work in
a totally different way:
•
The bit of our times would be replaced by a
qubit
in such a computer. A
qubit could take states 0 and 1 concurrently, with different probabilities.
•
Operations change the state of all qubits concurrently. Though there are
processes that correspond to the logical AND, OR, and NOT operations,
they would merely change probability distributions in quantum computers.
•
Computations are totally 'blind', i.e., there is no feedback on the system's
state as the computer works. And it wouldn't be possible, since you
can't 'read' quantum particles without influencing them (which is exactly
what quantum cryptography in the previous point is based upon!), and a
measuring process would destroy an entanglement immediately.
•
The art of programming a quantum computer consists in, for example,
changing probability distributions by continued operations such that the
'correct' state (i.e., the solution) has a higher probability than all other
states in the end. Only then is the system of qubits read and destroyed as
it is read. Moreover, quantum computers allow you to directly determine
periods of functions. This is the principle that the Shor algorithm for
factoring, which is explained in detail in [WillClear10], works by.
In sequential work, say, in iterations, quantum computers are not faster than
conventional computers. But they can do things like determining the period of a
function 'directly', which poses enormous problems for our classic sequential
computers. Consider diffraction radiograms of crystals: the images give you
