Home > Quantum Computing Osama Awwad Department of Computer Science Western Michigan University Overview Introduction Data
Quantum Computing
Osama Awwad
Department of Computer Science
Western Michigan
University
Overview
Introduction to quantum mechanics
Introduction to quantum mechanics
What
is a quantum computer?
Why bother with quantum computation?
Computer technology is making devices
smaller and smaller��
��reaching a point where classical physics is no longer a suitable model for the laws of physics.
Physics and Computation
The design of devices on such a small
scale will require engineers to control quantum mechanical effects.
Allowing computers to take advantage
of quantum mechanical behaviour allows us to do more than cram
increasingly many microscopic components onto a silicon chip��
�� it gives us a whole new framework
in which information can be processed in fundamentally new ways.
The nineteenth century was known as the machine age, the twentieth century will go down in history as the information age. I believe the twenty-first century will be the quantum age. Paul Davies, Professor Natural Philosophy – Australian Centre for Astrobiology
��No, you��re not going to be able to understand
it. . . . You see, my physics students don��t understand it either. That is
because I don��t understand it. Nobody does. ...
The theory of quantum electrodynamics describes Nature as absurd from
the point of view of common sense. And it agrees fully with an
experiment. So I hope that you can accept Nature as She is -- absurd.
Richard Feynman
Nobody understands quantum mechanics
��consider a setup involving
a photon source,
a
half-silvered mirror (beamsplitter),
and a pair of photon detectors.
photon source
beamsplitter
detectors
A simple experiment in optics
50%
50%
Simplest explanation:
beam-splitter acts as a classical coin-flip, randomly sending each photon
one way or the other.
Now consider what happens when we fire a single photon into the device��
�� consider a modification of the experiment��
100%
The
simplest explanation is wrong!
The simplest explanation for the modified
setup would still predict a 50-50 distribution��
full mirror
The ��weirdness�� of quantum mechanics��
Classical probabilities��
Consider a computation tree for a simple
two-step (classical) probabilistic algorithm, which makes a coin-flip
at each step, and whose output is 0 or 1:
0
1
0
1
The probability of
the computation following a given path is obtained by multiplying the
probabilities along all branches of that path�� in the example the
probability the computation follows the red path is
The probability of the computation giving
the answer 0 is obtained by adding the probabilities of all paths resulting
in 0:
|0
|1
|0
|1
��vs quantum probabilities
��
In quantum physics, we have probability
amplitudes, which can have complex phase factors associated with
them.
The probability amplitude associated
with a path in the computation tree is obtained by multiplying the probability
amplitudes on that path. In the example, the red path has
amplitude 1/2, and the green path has amplitude –1/2.
The probability amplitude for getting the answer |0 is obtained by adding the probability amplitudes�� notice that the phase factors can lead to cancellations! The probability of obtaining |0 is obtained by squaring the total probability amplitude. In the example the probability of getting |0 is
�� consider a modification of the experiment��
The simplest explanation for the modified
setup would still predict a 50-50 distribution��
full mirror
Explanation of experiment
100%
Representation of Data
A bit of data is represented by a single atom that is in one of two states denoted by |0> and |1>. A single bit of this form is known as a qubit
Representation of Data -
Qubits
A physical implementation of a qubit
could use the two energy levels of an atom. An excited state representing
|1> and a ground state representing |0>.
Excited State
Ground State
Nucleus
Light pulse of frequency
for time interval t
Electron
State |0>
State |1>
Representation of Data - Superposition
A single qubit can be forced into a
superposition of the two states denoted by the addition of the
state vectors:
|>
=
|0> + |1>
Where and
are complex numbers and | | + |
| = 1
1
2
1
2
1
2
2
2
A qubit in superposition is in both of the states |1> and |0 at the same time
Representation of Data - Superposition
Light pulse of frequency
for time interval t/2
State |0>
State |0> + |1>
|> =
|000> + |001> + . . . +
|111>
1
��8
1
��8
1
��8
Data Retrieval
Sound too good to be true?��It is!
In our equation: |> = 1 |0> + 2 |1> , represents the probability of the superposition
collapsing to |0>. The ��s are called
probability amplitudes. In a balanced superposition, = 1/��2n
where n is the number of qubits.
1
2
1
n
Relationships among data - Entanglement
Measuring multi-qubit systems
If we measure both bits of
we get with probability
Measurement
0.316|00› + 0.447|01› + 0.548|10› + 0.632|11›
Quantum mechanics and information
How does this affect communication complexity?
How does this affect information security?
How does this affect computational complexity?
Any physical medium capable of representing 0 and 1 is in principle capable of storing any linear combination
A ��Probabilistic Turing Machine��
(PTM) is an abstract model of the modern (classical) computer.
Strong Church-Turing Thesis:
A PTM can efficiently simulate any realistic
model of computing.
Widespread belief in the Strong Church-Turing
thesis has been one of the underpinnings of theoretical computer science.
The Classical Computing Model
What do we mean by ��efficient��?
The complexity of
an algorithm measures how much of some resource (e.g. time, space, energy)
the algorithm uses as a function of the input size.
e.g. the best known algorithms for factoring
an n bit number uses time in
(number field sieve algorithm)
Factoring is believed to be hard on a Turing machine (or any equivalent model), but how do we know that there isn��t some novel architecture on which it is easy?
The Strong Church Turing thesis
tells us that all reasonable models can be efficiently simulated by
a PTM, which implies that if it��s hard for a PTM it must be hard for
any other reasonable computer.
i.e. we believe computational problems, like factoring, have an intrinsic difficulty, independent of how hard we try to find an efficient algorithm.
In the early 1980s, Richard Feynman observed
that it seems implausible for a PTM to efficiently simulate quantum
mechanical systems��
��quantum computers
are
quantum mechanical systems��
�� so quantum computing is a model which seems to violate the Strong Church-Turing thesis!
Are quantum computers realistic?
Are quantum computers realistic?
The answer seems to be YES!
If the quantum computers are a reasonable
model of computation, and classical devices cannot efficiently simulate
them, then the Strong Church-Turing thesis needs to be modified to state:
A quantum computer can efficiently simulate any realistic model of computation.
Applications
Quantum Algorithms
a,b G ,
ak = b , find k
Integer Factorization (basis of RSA cryptography):
Discrete logarithms (basis of DH crypto,
including ECC):
Given N=pq, find p and q.
Computational Complexity Comparison
Elliptic Curve Discrete Logarithms
Factoring
Quantum
Classical
(in terms of number of group multiplications for n-bit inputs)
The following cryptosystems are insecure
against such quantum attacks:
Which cryptosystems are
threatened by Quantum Computers??
Information security protocols must be
studied in the context of quantum information processing.
http://arxiv.org/abs/quant-ph/0301141
We need to worry NOW about information that needs to remain private for long periods of time.
It takes a long time to change an infrastructure.
Quantum Information Security
We can exploit the eavesdropper detection that is intrinsic to quantum systems in order to derive new ��unconditionally secure�� information security protocols. The security depends only on the laws of physics, and not on computational assumptions.
Quantum computing in computational
complexity theory
Quantum computing in computational
complexity theory
Quantum computing in computational complexity theory
Implementation requirements
Implementation
Optical photon computer
NMR
Ion Traps
Solid-state device
There are two well-known qubits of this type.
Quantum Computer Languages
Even
though no quantum computer has been built that hasn��t stopped the proliferation of papers
on various aspects of the subject. Many such papers have been written
defining language specifications.
http://web.comlab.ox.ac.uk/oucl/work/paolo.zuliani/
References
Q
& A
Thank You
All Rights Reserved Powered by Free Document Search and Download
Copyright © 2011