Parallel algorithms for 3D Reconstruction of Asymmetric Objects
Download
Report
Transcript Parallel algorithms for 3D Reconstruction of Asymmetric Objects
Introduction to
Quantum Computing and
Quantum Information Theory
Dan C. Marinescu and Gabriela M. Marinescu
Computer Science Department
University of Central Florida
Orlando, Florida 32816, USA
Acknowledgments
The material presented is from the book
Lectures on Quantum Computing
by Dan C. Marinescu and Gabriela M. Marinescu
Prentice Hall, 2004
Work supported by National Science Foundation grants
MCB9527131, DBI0296107,ACI0296035, and EIA0296179.
ISCIS Antalya November 5, 2003
2
Contents
I. Computing and the Laws of Physics
II. A Happy Marriage; Quantum Mechanics &
Computers
III. Qubits and Quantum Gates
IV. Quantum Parallelism
V. Deutsch’s Algorithm
VI. Bell States, Teleportation, and Dense Coding
VII. Summary
ISCIS Antalya November 5, 2003
3
Technological limits
For the past two decades we have enjoyed Gordon
Moore’s law. But all good things may come to an end…
We are limited in our ability to increase
the density and
the speed of a computing engine.
Reliability will also be affected
to increase the speed we need increasingly smaller circuits
(light needs 1 ns to travel 30 cm in vacuum)
smaller circuits systems consisting only of a few particles
subject to Heissenberg uncertainty
ISCIS Antalya November 5, 2003
4
Energy/operation
If there is a minimum amount of energy dissipated to
perform an elementary operation, then to increase the
speed, thus the number of operations performed each
second, we require a liner increase of the amount of
energy dissipated by the device.
The computer technology vintage year 2000 requires
some 3 x 10-18 Joules per elementary operation.
Even if this limit is reduced say 100-fold we shall see a
10 (ten) times increase in the amount of power needed
by devices operating at a speed 103 times larger than
the sped of today's devices.
ISCIS Antalya November 5, 2003
5
Power dissipation, circuit density, and speed
In 1992 Ralph Merkle from Xerox PARC calculated that
a 1 GHz computer operating at room temperature, with
1018 gates packed in a volume of about 1 cm3 would
dissipate 3 MW of power.
A small city with 1,000 homes each using 3 KW would require
the same amount of power;
A 500 MW nuclear reactor could only power some 166 such
circuits.
ISCIS Antalya November 5, 2003
6
Talking about the heat…
The heat produced by a super dense computing engine is
proportional with the number of elementary computing
circuits, thus, with the volume of the engine. The heat
dissipated grows as the cube of the radius of the device.
To prevent the destruction of the engine we have to remove
the heat through a surface surrounding the device.
Henceforth, our ability to remove heat increases as the
square of the radius while the amount of heat increases
with the cube of the size of the computing engine.
ISCIS Antalya November 5, 2003
7
Energy consumption of a logic circuit
E
S
Speed of individual logic gates
Heat removal for a circuit with densely packed
logic gates poses tremendous challenges.
(b)
(a)
ISCIS Antalya November 5, 2003
8
Contents
I. Computing and the Laws of Physics
II. A Happy Marriage; Quantum Mechanics &
Computers
III. Qubits and Quantum Gates
IV. Quantum Parallelism
V. Deutsch’s Algorithm
VI. Bell States, Teleportation, and Dense Coding
VII. Summary
ISCIS Antalya November 5, 2003
9
A happy marriage…
The two greatest discoveries of the 20-th century
quantum mechanics
stored program computers
produced quantum computing and quantum
information theory
ISCIS Antalya November 5, 2003
10
Quantum; Quantum mechanics
Quantum is a Latin word meaning some quantity. In
physics it is used with the same meaning as the word
discrete in mathematics, i.e., some quantity or variable
that can take only sharply defined values as opposed to a
continuously varying quantity. The concepts continuum
and continuous are known from geometry and calculus.
For example, on a segment of a line there are infinitely
many points, the segment consists of a continuum of
points. This means that we can cut the segment in half,
and then cut each half in half, and continue the process
indefinitely.
Quantum mechanics is a mathematical model of the
physical world
ISCIS Antalya November 5, 2003
11
Heissenberg uncertainty principle
Heisenberg uncertainty principle says we cannot determine
both the position and the momentum of a quantum
particle with arbitrary precision.
In his Nobel prize lecture on December 11, 1954 Max Born
says about this fundamental principle of Quantum
Mechanics : ``... It shows that not only the determinism
of classical physics must be abandoned, but also the naive
concept of reality which looked upon atomic particles as if
they were very small grains of sand. At every instant a
grain of sand has a definite position and velocity. This is
not the case with an electron. If the position is determined
with increasing accuracy, the possibility of ascertaining its
velocity becomes less and vice versa.''
ISCIS Antalya November 5, 2003
12
A revolutionary approach to computing and
communication
We need to consider a revolutionary rather than an
evolutionary approach to computing.
Quantum theory does not play only a supporting role
by prescribing the limitations of physical systems used
for computing and communication.
Quantum properties such as
uncertainty,
interference, and
entanglement
form the foundation of a new brand of theory, the
quantum information theory where computational and
communication processes rest upon fundamental
physics.
ISCIS Antalya November 5, 2003
13
Milestones in quantum physics
1900 - Max Plank presents the black body radiation theory;
the quantum theory is born.
1905 - Albert Einstein develops the theory of the
photoelectric effect.
1911 - Ernest Rutherford develops the planetary model of
the atom.
1913 - Niels Bohr develops the quantum model of the
hydrogen atom.
1923 - Louis de Broglie relates the momentum of a particle
with the wavelength
1925 - Werner Heisenberg formulates the matrix quantum
mechanics.
1926 - Erwin Schrodinger proposes the equation for the
dynamics of the wave function.
ISCIS Antalya November 5, 2003
14
Milestones in quantum physics (cont’d)
1926 - Erwin Schrodinger and Paul Dirac show the
equivalence of Heisenberg's matrix formulation and Dirac's
algebraic one with Schrodinger's wave function.
1926 - Paul Dirac and, independently, Max Born, Werner
Heisenberg, and Pasqual Jordan obtain a complete
formulation of quantum dynamics.
1926 - John von Newmann introduces Hilbert spaces to
quantum mechanics.
1927 - Werner Heisenberg formulates the uncertainty
principle.
ISCIS Antalya November 5, 2003
15
Milestones in computing and information theory
1936 - Alan Turing dreams up the Universal Turing
Machine, UTM.
1936 - Alonzo Church publishes a paper asserting that
``every function which can be regarded as computable
can be computed by an universal computing machine''.
1945 - ENIAC, the world's first general purpose computer,
the brainchild of J. Presper Eckert and John Macauly
becomes operational.
1946 - A report co-authored by John von Neumann
outlines the von Neumann architecture.
1948 - Claude Shannon publishes ``A Mathematical
Theory of Communication’’.
1953 - The first commercial computer, UNIVAC I.
ISCIS Antalya November 5, 2003
16
Milestones in quantum computing
1961 - Rolf Landauer decrees that computation is physical and
studies heat generation.
1973 - Charles Bennet studies the logical reversibility of
computations.
1981 - Richard Feynman suggests that physical systems including
quantum systems can be simulated exactly with quantum computers.
1982 - Peter Beniof develops quantum mechanical models of Turing
machines.
1984 - Charles Bennet and Gilles Brassard introduce quantum
cryptography.
1985 - David Deutsch reinterprets the Church-Turing conjecture.
1993 - Bennet, Brassard, Crepeau, Josza, Peres, Wooters discover
quantum teleportation.
1994 - Peter Shor develops a clever algorithm for factoring large
numbers.
ISCIS Antalya November 5, 2003
17
Deterministic versus probabilistic photon
behavior
D1
D3
Incident beam of light
D5
Detector D1
D7
Reflected beam
Beam splitter
Transmitted beam
Detector D2
D2
(a)
ISCIS Antalya November 5, 2003
(b)
18
The puzzling nature of light
If we start decreasing the intensity of the incident light
we observe the granular nature of light. Imagine that
we send a single photon. Then either detector D1 or
detector D2 will record the arrival of a photon.
If we repeat the experiment involving a single photon
over and over again we observe that each one of the
two detectors records a number of events.
Could there be hidden information, which controls the
behavior of a photon? Does a photon carry a gene and
one with a ``transmit'' gene continues and reaches
detector D2 and another with a ``reflect'' gene ends
up at D1?
ISCIS Antalya November 5, 2003
19
The puzzling nature of light (cont’d)
Consider now a cascade of beam splitters. As before,
we send a single photon and repeat the experiment
many times and count the number of events
registered by each detector.
According to our theory we expect the first beam
splitter to decide the fate of an incoming photon; the
photon is either reflected by the first beam splitter or
transmitted by all of them. Thus, only the first and last
detectors in the chain are expected to register an equal
number of events.
Amazingly enough, the experiment shows that all the
detectors have a chance to register an event.
ISCIS Antalya November 5, 2003
20
State description
0
0
V
q0 = q
1
45o
O
q1 = q
q0
1
1
O
(a)
V
30o
1
q1
(b)
ISCIS Antalya November 5, 2003
21
A mathematical model to describe the state of a
quantum system
0 0 1 1
| 0 , 1 |
are complex numbers
| 0 | | 1 | 1
2
2
ISCIS Antalya November 5, 2003
22
Superposition and uncertainty
In this model a state 0 0 1 1
is a superposition of two basis states, “0” and “1”
This state is unknown before we make a measurement.
After we perform a measurement the system is no longer in
an uncertain state but it is in one of the two basis states.
2
| 0 | is the probability of observing the outcome “1”
2
is the probability of observing the outcome “0”
| 1 |
| 0 | | 1 | 1
2
2
ISCIS Antalya November 5, 2003
23
Multiple measurements
black
hard
white
soft
(a)
black
(b)
hard
white
black
soft
white
(c)
ISCIS Antalya November 5, 2003
24
Measurements in multiple bases
|
>
|
|
>
|
>
1
1
1
0
0
0
ISCIS Antalya November 5, 2003
|
>
25
Measurements of superposition states
The polarization of a photon is described by a unit vector on
a two-dimensional space with basis | 0 > and | 1>.
Measuring the polarization is equivalent to projecting the
random vector onto one of the two basis vectors.
Source S sends randomly polarized light to the screen; the
measured intensity is I.
The filter A with vertical polarization is inserted between the
source and the screen an the intensity of the light measured
at E is about I/2.
Filter B with horizontal polarization is inserted between A and
E. The intensity of the light measured at E is now 0.
Filter C with a 45 deg. polarization is inserted between A and
B. The intensity of the light measured at E is about 1 / 8.
ISCIS Antalya November 5, 2003
26
|
0
|
1
(a)
E
S
S
(b)
(c)
intensity = I
A
B
S
E
intensity = I/2
A
C
B
E
S
intensity = 0
(d)
E
A
intensity = I/8
(e)
ISCIS Antalya November 5, 2003
27
The superposition probability rule
If an event may occur in two or more
indistinguishable ways then the probability
amplitude of the event is the sum of the
probability amplitudes of each case considered
separately (sometimes known as Feynmann rule).
ISCIS Antalya November 5, 2003
28
Reflecting mirror U
Source S1
Detector D1
direction1
Beam splitter BS1
Beam splitter BS2
direction2
Detector D2
Source S2
Reflecting mirror L
(a)
| 0 > (| t >)
| 0 > (| t >)
V
V
+q
O
(b)
1
1
+q
direction1
|1>
(| r >)
+q
|1>
(| r >)
-q
(c)
ISCIS Antalya November 5, 2003
direction2
29
The experiment illustrating the
superposition probability rule
In certain conditions, we observe experimentally that a
photon emitted by S1 is always detected by D1 and
never by D2 and one emitted by S2 is always detected
by D2 and never by D1.
A photon emitted by one of the sources S1 or S2 may
take one of four different paths shown on the next
slide, depending whether it is transmitted, or reflected
by each of the two beam splitters.
ISCIS Antalya November 5, 2003
30
direction1
direction2
S1
S1
D1
BS1
T
BS2
T
+q
D1
U
+q
BS1
BS2
R
+q
R
+q
(b) The RR case: the probability
amplitude is (+q)(+q).
L
(a) - The TT case: the probability
amplitude is (+q)(+q).
S1
S1
R
BS1
T
U
-q
T
BS2
BS1
R
+q
+q
BS2
+q
D2
(d) The RT case: the probability
amplitude is (+q)(+q).
L
D2
(c) - The TR case: the
probability amplitude is (+q)(-q).
ISCIS Antalya November 5, 2003
31
A photon coincidence experiment
Detector D1
Reflecting mirror U
Beam splitter
Source
Reflecting mirror L
Detector D2
ISCIS Antalya November 5, 2003
32
A glimpse into the world of quantum computing
and quantum information theory
Quantum key distribution
Exact simulation of systems with a very large
state space
Quantum parallelism
ISCIS Antalya November 5, 2003
33
Quantum key distribution
To ensure confidentiality, data is often encrypted. The
most reliable encryption techniques are based upon
one time pads whereby the encryption key is used for
one session only and then discarded.
Thus, there exists the need for reliable and effective
methods for the distribution of the encryption keys.
The problem rests on the physical difficulty to detect
the presence of an intruder when communicating
through a classical communication channel.
To date, secure and reliable methods for cryptographic
key distribution have largely eluded the cryptographic
community in spite of considerable research effort and
ingeniousness.
ISCIS Antalya November 5, 2003
34
Quantum key distribution setup
Alice and Bob are connected via two communication channels, a
quantum and a classical one. Eve eavesdrops on both.
The photons prepared by Alice may have vertical/horizontal (VH) or
diagonal polarization (DG).
The photons with vertical/horizontal (VH) polarization may be used to
transmit binary information as follows: a photon with vertical
polarization may transmit a 1 while one with a horizontal polarization
may transmit a 0.
Similarly, those with diagonal (DG) polarization may transmit binary
information, 1 encoded as a photon with 45 deg. polarization, and 0
encoded as a photon with a 135 deg. polarization.
Bob uses a calcite crystal to separate photons with different
polarization. Shown is the case when the crystal is set up to separate
vertically polarized photons from the horizontally polarized ones. To
perform a measurement in the DG basis the crystal is oriented
accordingly.
ISCIS Antalya November 5, 2003
35
Vertical
Horizontal
45 deg
Vertical/Horizontal (VH)
135 deg
Diagonal (DG)
(a)
(b)
Quantum communication channel
Source of
polarized
photons
Quantum wiretap
Photon
separation
system
Eve
Classical wiretap
Alice
Classical communication channel
Bob
(c)
ISCIS Antalya November 5, 2003
36
The quantum key distribution algorithm of
Bennett and Brassard (BB84)
Alice selects n, the approximate length of the encryption
key. Alice generates two random strings a and b, each of
length (4+ )n. By choosing sufficiently large Alice and
Bob can ensure that the number of bits kept is close to 2n
with a very high probability.
A subset of length n of the bits in string a will be used as
the encryption key and the bits in string $b$ will be used
by Alice to select the basis (VH) or (DG) for each photon
sent to Bob.
ISCIS Antalya November 5, 2003
37
BB84 (cont’d)
Alice encodes the binary information in string a based
upon the corresponding values of the bits in string b.
For example, if the i-th bit of string b is
1 then Alice selects Vertical-Horizontal (VH) polarization. If VH is
selected, then
0 then Alice selects Diagonal (DG) polarization. If DG is selected,
then
a 1 in the i-th position of string a is sent as a photon with vertical
polarization (V), and
a $0$ as a photon with horizontal (H) polarization;
a 1 in the i-th position of string a is sent as a photon with a 45 deg.
polarization, and
a $0$ as a photon with 135 deg. polarization.
Both Alice and Bob use the same encoding convention for
each of the bases.
ISCIS Antalya November 5, 2003
38
BB84 (cont’d)
In turn, Bob picks up randomly (4+ )n bits to form a
string b’. He uses one of the two basis for the
measurement of each incoming photon in string a
based upon the corresponding value of the bit in string
b’.
For example, a 1 in the i-th position of b’ implies that
the i-th photon is measured in the DG basis, while a 0
requires that the photon is measured in the VH basis.
As a result of this measurement Bob constructs the
string a’.
ISCIS Antalya November 5, 2003
39
BB84 (cont’d)
Bob uses the classical communication channel to
request the string b and Alice responds on the
same channel with b. Then Bob sends Alice string
b’ on the classical channel.
Alice and Bob keep only those bits in the set {a,
a’} for which the corresponding bits in the set {b,
b’} are equal. Let us assume that Alice and Bob
keep only 2n bits.
ISCIS Antalya November 5, 2003
40
BB84 (cont’d)
Alice and Bob perform several tests to determine the
level of noise and eavesdropping on the channel. The
set of 2n bits is split into two sub-sets of n bits each.
One sub-set will be the check bits used to estimate the level
of noise and eavesdropping, and
The other consists of the {\it data} bits used for the quantum
key.
Alice selects n check bits at random and sends the
positions and values of the selected bits over the
classical channel to Bob. Then Alice and Bob compare
the values of the check bits. If more than say t bits
disagree then they abort and re-try the protocol.
ISCIS Antalya November 5, 2003
41
State space dimension of classical and quantum
systems
Individual state spaces of n particles combine quantum
mechanically through the tensor product. If X and Y are
vectors, then
their tensor product X
Y is also a vector, but its dimension is:
dim(X) x dim(Y)
while the vector product X x Y has dimension
dim(X)+dim(Y).
For example, if dim(X)= dim(Y)=10, then the tensor
product of the two vectors has dimension 100 while the
vector product has dimension 20.
ISCIS Antalya November 5, 2003
42
Quantum computers
In quantum systems the amount of parallelism
increases exponentially with the size of the system,
thus with the number of qubits. This means that the
price to pay for an exponential increase in the power of
a quantum computer is a linear increase in the amount
of matter and space needed to build the larger
quantum computing engine.
A quantum computer will enable us to solve problems
with a very large state space.
ISCIS Antalya November 5, 2003
43
Contents
I. Computing and the Laws of Physics
II. A Happy Marriage; Quantum Mechanics &
Computers
III. Qubits and Quantum Gates
IV. Quantum Parallelism
V. Deutsch’s Algorithm
VI. Bell States, Teleportation, and Dense Coding
VII. Summary
ISCIS Antalya November 5, 2003
44
One qubit
Mathematical abstraction
Vector in a two dimensional complex vector space
(Hilbert space)
Dirac’s notation
ket
bra
|
column vector
row vector
bra dual vector (transpose and complex conjugate)
ISCIS Antalya November 5, 2003
45
Ortonormal basis
| 1
| 0
0 1
2
0 1
2
ISCIS Antalya November 5, 2003
46
One qubit
0 0 1 1
| 0 , 1 |
are complex numbers
| 0 | | 1 | 1
2
2
ISCIS Antalya November 5, 2003
47
A bit versus a qubit
A bit
Can be in two distinct states, 0 and 1
A measurement does not affect the state
A qubit
0 0 1 1
can be in state | 0 or in state | 1 or in any other state
that is a linear combination of the basis state
When we measure the qubit we find it
in state | 0
in state | 1
with probability
with probability
| 0 |2
| 1 | 2
ISCIS Antalya November 5, 2003
48
0
0
Superposition states
1
(a) One bit
1
Basis (logical) state 0
Basis (logical) state 1
(b) One qubit
ISCIS Antalya November 5, 2003
49
Other states of a qubit
1
1
0
1
2
2
1
3
0
1
2
2
ISCIS Antalya November 5, 2003
50
A different basis for one qubit
0 1
0
0 1
2
2
2
1
2
0 1
0 1
2
2
ISCIS Antalya November 5, 2003
51
Qubit measurement
0
p0
p1
1
Possible states of one qubit before
the measurement
The state of the qubit after
the measurement
ISCIS Antalya November 5, 2003
52
The Boch sphere representation of one qubit
A qubit in a superposition state is represented
as a vector connecting the center of the Bloch
sphere with a point on its periphery.
The two probability amplitudes can be
expressed using Euler angles.
ISCIS Antalya November 5, 2003
53
|0>
z
|ψ
r
x
y
b
|1>
ISCIS Antalya November 5, 2003
54
z
x
b
ISCIS Antalya November 5, 2003
y
55
Two qubits
Represented as vectors in a 2-dimensional Hilbert
space with four basis vectors
00 , 01 , 10 , 11
When we measure a pair of qubits we decide that the
system it is in one of four states
00 , 01 , 10 , 11
with probabilities
| 00 | , | 01 | , | 10 | , | 11 |
2
2
ISCIS Antalya November 5, 2003
2
2
56
Two qubits
00 00 01 01 10 10 11 11
| 00 | | 01 | | 10 | | 11 | 1
2
2
2
ISCIS Antalya November 5, 2003
2
57
Measuring two qubits
Before a measurement the state of the system
consisting of two qubits is uncertain (it is given by the
previous equation and the corresponding probabilities).
After the measurement the state is certain, it is
00, 01, 10, or 11 like in the case of a classical two bit
system.
ISCIS Antalya November 5, 2003
58
Measuring two qubits (cont’d)
What if we observe only the first qubit, what
conclusions can we draw?
We expect that the system to be left in an uncertain
sate, because we did not measure the second qubit
that can still be in a continuum of states. The first qubit
can be
0 with probability
1 with probability
| 00 |2 | 01 |2
| 10 |2 | 11 |2
ISCIS Antalya November 5, 2003
59
Measuring two qubits (cont’d)
0I
Call
measure
I
Call 1
measure
I
0
the post-measurement state when we
the first qubit and find it to be 0.
the post-measurement state when we
the first qubit and find it to be 1.
00 00 01 01
| 00 | | 01 |
2
2
I
1
ISCIS Antalya November 5, 2003
10 10 11 11
| 10 | | 11 |
2
2
60
Measuring two qubits (cont’d)
II
0
0II
Call
measure
II
Call 1
measure
the post-measurement state when we
the second qubit and find it to be 0.
the post-measurement state when we
the second qubit and find it to be 1.
00 00 10 10
| 00 | | 10 |
2
2
II
1
ISCIS Antalya November 5, 2003
01 01 11 11
| 01 | | 11 |
2
2
61
Bell states - a special state of a pair of qubits
If
1
00 11
2
and
01 10 0
When we measure the first qubit we get the post
measurement state
I
I
1 | 11
0 | 00
When we measure the second qubit we get the post
mesutrement state II | 00 1II | 11
0
ISCIS Antalya November 5, 2003
62
This is an amazing result!
The two measurements are correlated, once we
measure the first qubit we get exactly the same result
as when we measure the second one.
The two qubits need not be physically constrained to
be at the same location and yet, because of the strong
coupling between them, measurements performed on
the second one allow us to determine the state of the
first.
ISCIS Antalya November 5, 2003
63
Entanglement
Entanglement is an elegant, almost exact translation of
the German term Verschrankung used by Schrodinger
who was the first to recognize this quantum effect.
An entangled pair is a single quantum system in a
superposition of equally possible states. The entangled
state contains no information about the individual
particles, only that they are in opposite states.
The important property of an entangled pair is that the
measurement of one particle influences the state of the
other particle. Einstein called that “Spooky
action at a distance".
ISCIS Antalya November 5, 2003
64
The spin
In quantum mechanics the intrinsic angular moment,
the spin, is quantized and the values it may take are
multiples of the rationalized Planck constant.
The spin of an atom or of a particle is characterized by
the spin quantum number s , which may assume
integer and half-integer values. For a given value of s
the projection of the spin on any axis may assume 2s
+ 1 values ranging from - s to $ + s by unit steps, in
other words the spin is quantized.
ISCIS Antalya November 5, 2003
65
More about the spin
There are two classes of quantum particles
fermions - spin one-half particles such as the electrons. The
spin quantum numbers of fermions can be
s=+1/2 and
s=-1/2
bosons - spin one particles. The spin quantum numbers of
bosons can be
s=+1,
s=0, and
s=-1
ISCIS Antalya November 5, 2003
66
The Stern-Gerlach experiment with
hydrogen atoms
Screen
N
Source of
hydrogen
atoms
S
Magnet
ISCIS Antalya November 5, 2003
67
Physical embodiment of a qubit
The electron with tow independent spin values,
+1/2 and -1/2
The photon, with tow independent polarizations,
horizonatla and vertical
ISCIS Antalya November 5, 2003
68
The spin of the electron
The electron has spin s = 1 /2 and the spin
projection can assume the values $ + ½
referred to as spin up, and -1/2 referred to as
spin down.
ISCIS Antalya November 5, 2003
69
Sz
Rn(0)
1
h
2
-
1
h
2
Rn(180)
(a)
(b)
ISCIS Antalya November 5, 2003
70
Light and photons
Light is a form of electromagnetic radiation; the
wavelength of the radiation in the visible
spectrum varies from red to violet.
Light can be filtered by selectively absorbing
some color ranges and passing through others.
A polarization filter is a partially transparent
material that transmits light of a particular
polarization.
ISCIS Antalya November 5, 2003
71
Photons
Photons differ from the spin 1/2 electrons in two ways:
A photon is characterized by its
(1) they are massless and
(2) have spin $1$.
vector momentum (the vector momentum determines the
frequency) and
polarization.
In the classical theory light is described as having an
electric field which oscillates either vertically, the light is
x-polarized, or horizontally, the light is y-polarized in a
plane perpendicular to the direction of propagation, the
z-axis.
The two basis vectors are |h> and |v>
ISCIS Antalya November 5, 2003
72
Vertically and horizontally polarized photons
x
v
z
y
(a)
x
z
h
y
(b)
ISCIS Antalya November 5, 2003
73
Polarization filters
A polarization filter is a partially transparent material that
transmits light of a particular polarization.
If we set the axis of a polarization filter to let pass ypolarized light, then all photons in the state |v> will be
absorbed in the filter and only the photons in state |h> will
pass through. If the axis of the polarization filter is set to
let pass x-polarized light, then all photons in state |h> will
be absorbed and only photons in state | v > will pass
through.
When the polarization filter is set at angle with respect to
the coordinate system of the incoming beam of light the
emerging photons are in a superposition state
ISCIS Antalya November 5, 2003
74
The effect of a polarization filter
x'
x
y'
| h' >
y
|h>
(a)
y
Incident
beam of light
y
x
| h' >
x
PF1
|h>
| h' >
PF2
z
(b)
ISCIS Antalya November 5, 2003
75
Communication with entangles particles
Even when separated two entangled particles
continue to interact with one another.
Particle 2 and particle 3 in an anti-correlated
state (spin up and spin down).
Then if we measure particle 1 and particle 2 and
set them in an anti-correlated state, then
particle 1 ends up in the same state particle 3
was initially.
ISCIS Antalya November 5, 2003
76
Initial state
particle1
particle2
particle3
Entangle particle2 and particle3
Particle2 and particle3 in an anti-symmetric entangled state
particle1
particle2
particle3
Separate the entangled particles
New York
particle1
London
particle2
particle3
Entangle particle1 and particle2
Measure the entangled system
(particle1, particle2)
New York
particle1
London
particle2
particle3
ISCIS Antalya November 5, 2003
77
Classical gates
Implement Boolean functions.
Are not reversible (invertible). We cannot recover the
input knowing the output.
This means that there is an iretriviable loss of
information
ISCIS Antalya November 5, 2003
78
NOT gate
x
x
0
1
y
1
0
z = (x) AND (y)
x
0
0
1
1
y
0
1
0
1
z
0
0
0
1
z = (x) NAND (y)
x
0
0
1
1
y
0
1
0
1
z
1
1
z = (x) OR (y)
x
0
0
1
1
y
0
1
0
1
z
0
1
1
1
z = (x) NOR (y)
x
0
0
1
1
y
0
1
0
1
z
1
0
0
0
z = (x) XOR (y)
x
0
0
1
1
y
0
1
0
1
z
0
1
1
0
y = NOT(x)
x
AND gate
y
x
NAND gate
y
x
OR gate
y
x
NOR gate
y
x
XOR gate
y
ISCIS Antalya November 5, 2003
1
0
79
One qubit gates
Transform an input qubit into an output qubit
Characterized by a 2 x 2 matrix with complex
coefficients
ISCIS Antalya November 5, 2003
80
0 1
0 0 1 1
'
0
'
1
One-qubit gate
g11 g12
G
g 21 g 22
G
0 g11
1 g 21
ISCIS Antalya November 5, 2003
g12 0
g 22 1
81
One qubit gates
I identity gate; leaves a qubit unchanged.
X or NOT gate transposes the components
of an input qubit.
Y gate.
Z gate flips the sign of a qubit.
H the Hadamard gate.
ISCIS Antalya November 5, 2003
82
One qubit gates
g11
G
g 21
g12
g 22
g11
T
G
g12
*
*
g11g11 g 21g 21
G G *
*
g
g
g
22 g 21
12 11
g 21
g 22
*
g11
G *
g12
g
g
*
21
*
22
g g g g
I
g g g g
*
11 12
*
12 12
ISCIS Antalya November 5, 2003
*
21 22
*
22 22
83
Identity transformation, Pauli matrices, Hadamard
1 0
0 I
0 1
0 0 1 1
0 1
1 X
1 0
1 0 0 1
0 i
2 Y
i 0
1 0
3 Z
0 1
1 1 1
H
2 1 1
i1 0 i 0 1
0 0 1 1
0
ISCIS Antalya November 5, 2003
0 1
2
1
0 1
2
84
Tensor products and ``outer’’ products
1
1 1 0
00 | 0 | 0
0 0 0
0
1
1
0
0
00 00 1 0 0 0
0
0
0
0
ISCIS Antalya November 5, 2003
0 0 0
0 0 0
0 0 0
0 0 0
85
CNOT a two qubit gate
Control input
Target input
Two inputs
Control
Target
+
O
+
O
addition modulo 2
The control qubit is transferred to the output as is.
The target qubit
Unaltered if the control qubit is 0
Flipped if the control qubit is 1.
ISCIS Antalya November 5, 2003
86
VCNOT
WCNOT GCNOT VCNOT
CNOT
GCNOT
1
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
ISCIS Antalya November 5, 2003
87
The two input qubits of a two qubit gates
0 0 1 1
0 0 1 1
VCNOT
0 0
0 0 0 1
1 1 1 0
1 1
ISCIS Antalya November 5, 2003
88
Two qubit gates
GCNOT 00 00 01 01 10 11 11 10
GCNOT
1
0
0
0
0
1
0
0
0
0
0
1
ISCIS Antalya November 5, 2003
0
0
1
0
89
Two qubit gates
WCNOT GCNOT VCNOT
WCNOT
1
0
0
0
0 0 0 0 0 0 0
1 0 0 0 1 0 1
11
0 0 1 1 0
0 1 0 11 1 0
WCNOT 0 0 00 0 1 01 11 10 10 11
WCNOT 0 0 (0 0 1 1 ) 1 1 (1 0 0 1 )
ISCIS Antalya November 5, 2003
90
Final comments on the CNOT gate
CNOT preserves the control qubit (the first and the
second component of the input vector are replicated
in the output vector) and flips the target qubit (the
third and fourth component of the input vector
become the fourth and respectively the third
component of the output vector).
WCNOT 0 0 (0 0 1 01 ) 1 1 (1 0 0 1 )
The CNOT gate is reversible. The control qubit is
replicated at the output and knowing it we can
reconstruct the target input qubit.
ISCIS Antalya November 5, 2003
91
Fredkin gate
Three input and three output qubits
One control
Two target
When the control qubit is
0 the target qubits are replicated to the output
1 the target qubits are swapped
ISCIS Antalya November 5, 2003
92
Three
qubit
gate
a
a
a
b
a
a'
b
b
b
a
b
b'
0
0
1
1
c
c'
a
Input
b
c
a'
Output
b' c'
a
Input
b
c
a'
Output
b' c'
a
Input
b
c
a'
Output
b' c'
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
00
0
1
1
1
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
0
1
0
1
1
1
0
0
1
0
0
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
0
0
1
1
0
1
0
0
1
0
1
1
1
0
1
1
0
1
0
1
1
1
1
1
1
1
1
(a)
(b)
(c)
0
bc
1
c
b
bc
0
c
c
c'
c
c'
a=0
a’= bc & b’ = bc
a=1
& b=0
ISCIS
Antalya November 5, 2003
(d)
(e)
a’= c
& b’ = c
93
Toffoli gate
Three input and three output qubits
Two control
One target
When both control qubit
are 1 the target qubit is flipped
otherwise the target qubit is not changed.
ISCIS Antalya November 5, 2003
94
Toffoli gate is universal. It may emulate an
AND and a NOT gate
a
a
a
a
1
1
b
b
b
b
b
b
+ ab
c O
1
0
b
c
(a)
NAND(ab)
(b)
ISCIS Antalya November 5, 2003
(c)
95
Controlled H gate
H
H
(a)
(b)
ISCIS Antalya November 5, 2003
96
Generic one qubit controlled gate
|c>
|t>
|c>
U
|t>
A
(a)
B
C
(b)
ISCIS Antalya November 5, 2003
97
|c0>
|c0>
|c1>
|c1>
|c2>
|c2>
|c3>
|c3>
|c4>
|c4>
|c5>
|c5>
| w0>=| 0 >
| 0>
| w1>=| 0 >
| 0>
| w2>=| 0 >
| 0>
| w3>=| 0 >
| 0>
| w4>=| 0 >
| 0>
C
o
n
t
r
o
l
Target
|t>
U
ISCIS Antalya November 5, 2003
98
Contents
I. Computing and the Laws of Physics
II. A Happy Marriage; Quantum Mechanics &
Computers
III. Qubits and Quantum Gates
IV. Quantum Parallelism
V. Deutsch’s Algorithm
VI. Bell States, Teleportation, and Dense Coding
VII. Summary
ISCIS Antalya November 5, 2003
99
A quantum circuit
Given a function f(x) we can construct a reversible
quantum circuit consisting of Fredking gates only,
capable of transforming two qubits as follows
|x>
|x>
Uf
|y>
| y o+ f(x )>
The function f(x) is hardwired in the circuit
ISCIS Antalya November 5, 2003
100
A quantum circuit (cont’d)
If the second input is zero then the transformation
done by the circuit is
|x>
|x>
Uf
| f(x )>
|0>
ISCIS Antalya November 5, 2003
101
A quantum circuit (cont’d)
Now apply the first qubit through a Hadamad gate.
0 1
|0>
H
2
|0>
Uf
|0>
0
f (0) 1 f (1)
2
The resulting sate of the circuit is
0 1
0 f(
)
2
The output state contains information about f(0) and f(1).
ISCIS Antalya November 5, 2003
102
|x>
|x>
|x>
Uf
|y>
Uf
| y O+ f(x) >
|0>
(a)
|0>
|x>
| f(x) >
(b)
H
Uf
|0>
(c)
ISCIS Antalya November 5, 2003
103
Quantum parallelism
The output of the quantum circuit contains information
about both f(0) and f(1). This property of quantum circuits
is called quantum parallelism.
Quantum parallelism allows us to construct the entire truth
table of a quantum gate array having 2n entries at once. In
a classical system we can compute the truth table in one
time step with 2n gate arrays running in parallel, or we
need 2n time steps with a single gate array.
We start with n qubits, each in state |0> and we apply a
Welsh-Hadamard transformation.
ISCIS Antalya November 5, 2003
104
|x>
(m-dimensional)
|x>
Uf
|y>
(k-dimensional)
|yO
+ f(x) >
(n=m+k)-dimensional)
ISCIS Antalya November 5, 2003
105
H0
0 1
2
( H H H ) 000
Uf(
1
2n
2 n 1
x ,0 )
x 0
1
2n
1
2
1
n
2
n
[( 0 1 ) ( 0 1 ) ( 0 1 )]
2 n 1
x
x 0
2 n 1
U
x 0
f
( x,0 )
ISCIS Antalya November 5, 2003
1
2 n 1
2n
x 0
x, f ( x ) )
106
Contents
I. Computing and the Laws of Physics
II. A Happy Marriage; Quantum Mechanics &
Computers
III. Qubits and Quantum Gates
IV. Quantum Parallelism
V. Deutsch’s Algorithm
VI. Bell States, Teleportation, and Dense Coding
VII. Summary
ISCIS Antalya November 5, 2003
107
Deutsch’s problem
Consider a black box characterized by a transfer
function that maps a single input bit x into an output,
f(x). It takes the same amount of time, T, to carry out
each of the four possible mappings performed by the
transfer function f(x) of the black box:
f(0) = 0
f(0) = 1
f(1) = 0
f(1) = 1
The problem posed is to distinguish if
f ( 0) f (1)
f ( 0) f (1)
ISCIS Antalya November 5, 2003
108
0
f(0)
1
0
f(0)
1
f(1)
f(1)
2T
(a)
T
(b)
|x>
|x>
Uf
|y>
| y > O+ f(x) >
T
(c)
ISCIS Antalya November 5, 2003
109
A quantum circuit to solve Deutsch’s problem
|0>
H
|x>
|x>
H
Uf
|1>
H
0
|y>
1
| y > +O f(x)
2
ISCIS Antalya November 5, 2003
3
110
0
1 0 1
0 0 1
0 1 0
0
1 1 1 1
1 1 1
1 1 1 1 1 1 1 1
G1 H H
2 1 1
2 1 1 2 1 1 1 1
1 1 1 1
1 1 1 1 0
1
1 1 1 1 1 1 1 1
1 G1 0
2 1 1 1 1 0
2 1
1 1 1 1 0
1
0 1 0 1
1
1 ( 00 01 10 11 )
2
2
2
x
0 1
2
y
0 1
2
ISCIS Antalya November 5, 2003
111
y f ( x)
0 1
2
f ( x)
0 f ( x) 1 f ( x)
y f ( x) (1)
2
f ( x)
f ( x) 1 f ( x)
2
0 1
2
0 1
2
y f ( x)
0 1
2
if
f ( x) 0
if
f ( x) 1
ISCIS Antalya November 5, 2003
112
x
y
0 1
1
0
1
0
1
1 1
2
2 2 1
2
1
2 x ( y f ( x))
1
0 1 0 1
1 1
1
2
2
2
1
1
0 1 0 1 1 1
2
2 2 1
1
2 x ( y f ( x))
1
0 1 0 1
1 1
1
2
2
2
1
ISCIS Antalya November 5, 2003
2
0 1
if
f (0) f (1) 0
if
f (0) f (1) 1
if
f (0) 0, f (1) 1
if
f (0) 1, f (1) 0
113
2
1
1 1 if
2 1
1
x ( y f ( x))
1
1 1
if
2 1
1
ISCIS Antalya November 5, 2003
f (0) f (1)
f (0) f (1)
114
1
1 1 1 1 0 1 0
G3 H I
2 1 1 0 1
2 1
0
3 G3 2
1
1 0
2 1
0
1
1 0
2 1
0
0
1
0
1
0
1
0
1
0 1
0 1 1 1
1 0 2 1
0 1 1
1 0 1
0 1 1 1
1 0 2 1
0 1 1
1
0 1
1 0
0 1
1
0
1
0
1
0
1
0 1
1 1
0
2 0
2
0
0
0 1
1 0
1
2 1
2
1
ISCIS Antalya November 5, 2003
if
f (0) f (1)
if
f (0) f (1)
115
Evrika!!
By measuring the first output qubit qubit we are able to
determine
f (0) f (1) performing a single evaluation.
3 f (0) f (1)
0 if
f (0) f (1)
1 if
0 1
2
f (0) f (1)
f (0) f (1)
ISCIS Antalya November 5, 2003
116
Contents
I. Computing and the Laws of Physics
II. A Happy Marriage; Quantum Mechanics &
Computers
III. Qubits and Quantum Gates
IV. Quantum Parallelism
V. Deutsch’s Algorithm
VI. Bell States, Teleportation, and Dense Coding
VII. Summary
ISCIS Antalya November 5, 2003
117
Quantum circuit to create Bell states
stage 1
|a>
|a>
H
H
stage 2
|a’>
|V>
|b>
|b>
I
|W>
|b’>
(a)
(b)
ISCIS Antalya November 5, 2003
118
Pair of entangled qubits
particle
1
particle
2
particle
3
Caroll
Bob
Alice
particle
1
particle
2
particle
3
Quantum
Channel
CNOT
particle 1 - target qubit
particle 3 - control qubit
The measurement on
the pair (1&3) changes
the state of particle 2 to
one of four states: S1,
S2, S3, S4
iY
Receive from Alice
results of measurements
00 01
10
11
Measurement
particle 3 - measured
particle 1 - unchanged
I
Send to Bob results of
measurement
00 01
10
11
X
Z
Z
Classical
Channel
Particle 2 is in the same
state as particle 3
ISCIS Antalya November 5, 2003
119
Pair of entangled qubits
Alice’s
qubit
Bob’s
qubit
Caroll
Bob’s
qubit
Alice’s
qubit
I
Z
X
00
01
10
iY
11
Alice’s modified
but still entangled qubit
Quantum
channel
Qubit from
Alice
Alice
CNOT
First
qubit
Second
qubit
0
H
0
1
1
Bob
ISCIS Antalya November 5, 2003
120
Contents
I. Computing and the Laws of Physics
II. A Happy Marriage; Quantum Mechanics &
Computers
III. Qubits and Quantum Gates
IV. Quantum Parallelism
V. Deutsch’s Algorithm
VI. Bell States, Teleportation, and Dense Coding
VII. Summary
ISCIS Antalya November 5, 2003
121
Final remarks
A tremendous progress has been made in the area of
quantum computing and quantum information theory
during the past decade. Thousands of research papers,
a few solid reference books, and many popular-science
books have been published in recent years in this area.
The growing interest in quantum computing and
quantum information theory is motivated by the
incredible impact this discipline could have on how we
store, process, and transmit data and knowledge in
this information age.
ISCIS Antalya November 5, 2003
122
Final remarks (cont’d)
Computer and communication systems using quantum
effects have remarkable properties.
Quantum computers enable efficient simulation of the most
complex physical systems we can envision.
Quantum algorithms allow efficient factoring of large integers with
applications to cryptography.
Quantum search algorithms speedup considerably the process of
identifying patterns in apparently random data.
We can guarantee the security of our quantum communication
systems because eavesdropping on a quantum communication
channel can always be detected.
ISCIS Antalya November 5, 2003
123
Final remarks (cont’d)
It is true that we are years, possibly decades away
from actually building a quantum computer
requiring little if any power at all,
filling up the space of a grain of sand, and
computing at speeds that are unattainable today even
by covering tens of acres of floor space with clusters
made from tens of thousands of the fastest processors
built with current state of the art solid state technology.
ISCIS Antalya November 5, 2003
124
Final remarks (cont’d)
All we have at the time of this writing is a seven qubit
quantum computer able to compute the prime factors
of a small integer, 15. Building a quantum computer
faces tremendous technological and theoretical
challenges.
At the same time, we witness a faster rate of progress
in quantum information theory where applications of
quantum cryptography seem ready for
commercialization. Recently, a successful quantum key
distribution experiment over a distance of some 100
km has been announced.
ISCIS Antalya November 5, 2003
125
Summary
Quantum computing and quantum information theory
is truly an exciting field.
It is too important to be left to the physicists alone….
ISCIS Antalya November 5, 2003
126