Present Remotely
Send the link below via email or IM
CopyPresent to your audience
Start remote presentation Invited audience members will follow you as you navigate and present
 People invited to a presentation do not need a Prezi account
 This link expires 10 minutes after you close the presentation
 A maximum of 30 users can follow your presentation
 Learn more about this feature in our knowledge base article
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.
An introduction to Quantum computing
No description
by
Tweetcedric cod
on 7 November 2013Transcript of An introduction to Quantum computing
An introduction to Quantum computing
Quantum computer hardware
Got bits ? need gates
Applied computer science
Integer factorization (Peter Shor)
Quantum bits
Meet a Qubit
Theoretical computer science
Database search (Lov Grover)
Hmm.. What the hell?
quick definition
origins
hopes
presentation scope
why bother ?
Telecommunication security
How to harness its power
What I could
compute
What I can
compute
What's next ?
Quantum mechanics
Tiny weird objects
A new security
paradigm
Fresh new bites !!!
Turing and complexity theory
010 101
references
cedric codet  07/11/2013  Jeudi Trialog
A quantum computer is a machine that performs calculations based on the laws of quantum mechanics, which is the behavior of particles at the subatomic level.
1982  Feynman proposed the idea of creating machines based on the laws of quantum mechanics instead of the laws of classical physics.
1985  David Deutsch developed the quantum turing machine, showing that quantum circuits are universal.
1994  Peter Shor came up with a quantum algorithm to factor very large numbers in polynomial time.
1997  Lov Grover develops a quantum search algorithm with O(√N) complexity
different kinds of Qubits
Due to the nature of quantum physics, the destruction of information in a gate will cause heat to be evolved which can destroy the superposition of qubits.
This type of gate cannot be used. We must use Quantum Gates.
Quantum Gates are similar to classical gates, but do not have a degenerate output. i.e. their original input state can be derived from their output state, uniquely. They must be reversible.
This means that a deterministic computation can be performed on a quantum computer only if it is reversible. Luckily, it has been shown that any deterministic computation can be made reversible.(Charles Bennet, 1973)
Simplest gate involves one qubit and is called a Hadamard Gate (also known as a squareroot of NOT gate.) Used to put qubits into superposition.
more stuff... And
The CCN gate has been shown to be a universal reversible logic gate as it can be used as a NAND gate.
Application: cracking RSA !
if you can factorize (quick enough) the public key, you can decipher the message
existing computers
IBM quantum molecule computer
DWave
 Key technical challenge: prevent decoherence, or unwanted interaction with environment
 Several Qubits approaches: NMR, ion trap, quantum dot, Josephson junction, optical…
implementation
 Larger computations will require quantum error correcting codes
Expected
applications
 Quantum computing can provide insight on the physical nature of the world
 On the other hand, physical processes may enable to solve computing problems (like optimizations)
 Secured commmunications from eavesdropper
 Crypto analysis
 Faster search algorithms
 Quantum systems simulation
Need for increase in processing power strong (big data processing has become a necessity for businesses)
Moore’s Law: We hit
the quantum level
by 2010~2020.
“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
The Photon case
A simple experiment with polarization
"Explanation"
What's a Photon ?
Polarization ?
The experiment
Vibration of photon
phi> = a↑> + b→>
probability that the photon polarized is horizontally (switch to state →>) after measure: b²
a²+b² = 1
Duality body wave:
 To explain some aspects of light behavior, such as interference and diffraction, you treat it as a wave
 To explain other aspects you treat light as being made up of particles
probability that the photon is polarized vertically (switch to state ↑>) after measure: a²
a and b are complex numbers
the basis is arbitrary
Key notions
entanglement
no cloning
destructive measure
probabilistic behaviour
super cool
sucks
superposition (= coherence)
decoherence
Super computer
The photon as a Qubit
phi> = a↑> + b→>
can be written
phi> = a1> + b0>
quantum object used to store information: that's a Qubit !
Quantum Key Distribution
Multiple Qubits
Safe communication channel

Classical bits : independent
0 1
those two bits have no interaction between them
Qubits: entangled
2 parameters are sufficient to describe the state of the register
=> 2 classical bits carry 2 unity of information
bit1
bit2
bit1
bit2
Decoherence
a1> + b0>
a'1> + b'0>
NO!
Experience proves qubits can't be described independently. there is a strong correlation between states.
you need a new basis to describe the two bits
EPR pair and entanglement
bit1 & bit2> = w00> + x10> + y01> + z11>
What can you do ? => you code all integers up to 2^n1 on n bits AT THE SAME TIME
If you have a 2 qubits computer => you can store the following integers:
 0 coded by the physical state 00>
 1 coded by 01>
 2 coded by 10>
 3 coded by 11>
and compute all of them at the same time
00>
01>
10>
11>
bit1
bit2
No cloning principle
middle man attack hard because no cloning principle

4 parameters are need to describe the state of the register
=> 2 qubits carry 4 unity of information
exponential growth of the state space
Massive code parallelization ?
No : Destructive measure + probabilitic output => you got only one result!
Maths say so! The proof relies on Quantum mechanism axioms and particularly linearity.
Any function modifying a state phi> must be linear. You can't find such a function that copies the state of a qubit to another.
You could copy all the results before measuring ? No: No cloning theorem
You have to invent another way to code => Software challenge !
Computation:
 add bit1 and bit2
 write the result in bit3
So we compute f(n) in bit3 with n coded by bit1 and bit2 (hence n ranges from 0 to 3)
Measure all registers
w² = probability to measure state 00>
x² = probability to measure state 10>
y² = probability to measure state 01>
z² = probability to measure state 11>
bit1 & bit2> = w000> + x100> + y010> + z110>
000>
010>
100>
110>
w² = probability to measure state 000> = 0.25
x² = probability to measure state 100> = 0.25
y² = probability to measure state 010> = 0.25
z² = probability to measure state 110> = 0.25
bit1
bit2
bit3
normally we should add states 001>, 011>, 101> and 111> but we know here those are null
input register
output register
bit1 & bit2> = w000> + x101> + y011> + z110>
000>
011>
101>
110>
w² = probability to measure state 000> = 0.25
x² = probability to measure state 101> = 0.25
y² = probability to measure state 011> = 0.25
z² = probability to measure state 110> = 0.25
bit1
bit2
bit3
input register
output register
bit1
bit2
bit3
input register
output register
we only have 1 left in input register
and f(1) = 1 n output register
We can measure the couple {1, f(1)} with probability 0.25
Another problem:
Entanglement collapses at one point (Decoherence) => Hardware challenge !
"Decoherence, in brief, describes the constant, tenuous interactions between a system or object and its environment, a set of interactions that allows concrete behaviors to emerge from the multitude of simultaneous possibilities that quantum theory allows".
Schrodinger's cat is not in a superposition of states. The number of interacting particles "stabilizes" it all.
EPR pair distribution
Teleportation
Dense coding
Two dual operations:
"transmit" one qubit with two classical bits
"transmit" two classical bits on a qubit
"Spooky action at a distance"
Einstein
Thought experiment intended to reveal what they (EPR authors) believed to be inadequacies of quantum mechanics (1935).
"Deux cœurs qui ont interagi dans le passé ne peuvent plus être considérés de la même manière que s'ils ne s'étaient jamais rencontrés. Marqués à jamais par leur rencontre, ils forment un tout inséparable".Etienne Klein
two entangled photons are produced with opposed polarization
Schrodinger thought experiment
(1935)
To be done !
Gate example
http://imgur.com/gallery/a4yU9
http://en.wikipedia.org/wiki/Timeline_of_quantum_computing
 The process has to be repeated several times because the QFT may yield false results
 Most quantum algorithms : they are probabilistic and give the right answer with high probability
How to find the period of a function f on a quantum computer ?
Input register
Output register
Entangled Qubits
Initialize registers
superposition of integers from 0 to Log2(N).
All Qubits set to 0
Apply f to input register
N Qubits
superposition of integers from 0 to Log2(N).
superposition of f(n) with n integer from 0 to Log2(N).
n and f(n) are entangled
When measuring f(x), the input register collapses to the superposition of states y such that f(y) = f(x)
Measure f(x)
superposition of states x and y such that f(y) = f(x)
f(x)
f(x)
x
0
1
2
3
00>
01>
10>
11>
input register
output register
0
1
1>
0>
if we measure 1:
f(x)
x
1
3
01>
11>
input register
output register
0
1
1>
0>
Apply QFT on input register
Biggest difficulty: decoherence
Need for very low temperature, magnetic fields...
superposition of states x and y such that f(y) = f(x)
The period of f !
 Performed factorization of 15 with shor's algorithm
Classical computing poses no serious threat to the RSA system
 approximately 428 millenia to factorise a 200digit number (assuming GHz computing speed).
 Shor’s quantum algorithm would be able to factor the same number in a matter of days
Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(log N) storage space. Lov Grover formulated it in 1996.
In models of classical computation, searching an unsorted database cannot be done in less than linear time (so merely searching through every item is optimal). Grover's algorithm illustrates that in the quantum model searching can be done faster than this; in fact its time complexity O(N1/2) is asymptotically the fastest possible for searching an unsorted database in the linear quantum model.
Can find a solution in polynomial time (bounded by N^x)
N is the size of the input
difficulty of a problem
Can verify a solution in polynomial time (bounded by N^x)
Requires a space on a computer bounded by N^x
BoundedError Probabilistic PolynomialTime with error probability under 1/3
Bounded error Quantum Polynomial time with error probability under 1/3
BoundedError Probabilistic PolynomialTime with error probability under 1/2
Prospects
 Bought by Lockhead Martin, Google and Nasa
 Big controversy: is it a quantum computer ?
 In parallel, new programming techniques are required
 Link between computability and physics
Hectic, hard to follow =>
 Compute hard problems
 Harness quantum mechanics properties for security purposes
 Deepen our understanding of Physics
Beware !
> More a mathematical theory than a physical one
Polarization in photography
A basis for Qubits
Computation example
Outline of the algorithm
Quantum part
Remarks
Full transcriptQuantum computer hardware
Got bits ? need gates
Applied computer science
Integer factorization (Peter Shor)
Quantum bits
Meet a Qubit
Theoretical computer science
Database search (Lov Grover)
Hmm.. What the hell?
quick definition
origins
hopes
presentation scope
why bother ?
Telecommunication security
How to harness its power
What I could
compute
What I can
compute
What's next ?
Quantum mechanics
Tiny weird objects
A new security
paradigm
Fresh new bites !!!
Turing and complexity theory
010 101
references
cedric codet  07/11/2013  Jeudi Trialog
A quantum computer is a machine that performs calculations based on the laws of quantum mechanics, which is the behavior of particles at the subatomic level.
1982  Feynman proposed the idea of creating machines based on the laws of quantum mechanics instead of the laws of classical physics.
1985  David Deutsch developed the quantum turing machine, showing that quantum circuits are universal.
1994  Peter Shor came up with a quantum algorithm to factor very large numbers in polynomial time.
1997  Lov Grover develops a quantum search algorithm with O(√N) complexity
different kinds of Qubits
Due to the nature of quantum physics, the destruction of information in a gate will cause heat to be evolved which can destroy the superposition of qubits.
This type of gate cannot be used. We must use Quantum Gates.
Quantum Gates are similar to classical gates, but do not have a degenerate output. i.e. their original input state can be derived from their output state, uniquely. They must be reversible.
This means that a deterministic computation can be performed on a quantum computer only if it is reversible. Luckily, it has been shown that any deterministic computation can be made reversible.(Charles Bennet, 1973)
Simplest gate involves one qubit and is called a Hadamard Gate (also known as a squareroot of NOT gate.) Used to put qubits into superposition.
more stuff... And
The CCN gate has been shown to be a universal reversible logic gate as it can be used as a NAND gate.
Application: cracking RSA !
if you can factorize (quick enough) the public key, you can decipher the message
existing computers
IBM quantum molecule computer
DWave
 Key technical challenge: prevent decoherence, or unwanted interaction with environment
 Several Qubits approaches: NMR, ion trap, quantum dot, Josephson junction, optical…
implementation
 Larger computations will require quantum error correcting codes
Expected
applications
 Quantum computing can provide insight on the physical nature of the world
 On the other hand, physical processes may enable to solve computing problems (like optimizations)
 Secured commmunications from eavesdropper
 Crypto analysis
 Faster search algorithms
 Quantum systems simulation
Need for increase in processing power strong (big data processing has become a necessity for businesses)
Moore’s Law: We hit
the quantum level
by 2010~2020.
“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
The Photon case
A simple experiment with polarization
"Explanation"
What's a Photon ?
Polarization ?
The experiment
Vibration of photon
phi> = a↑> + b→>
probability that the photon polarized is horizontally (switch to state →>) after measure: b²
a²+b² = 1
Duality body wave:
 To explain some aspects of light behavior, such as interference and diffraction, you treat it as a wave
 To explain other aspects you treat light as being made up of particles
probability that the photon is polarized vertically (switch to state ↑>) after measure: a²
a and b are complex numbers
the basis is arbitrary
Key notions
entanglement
no cloning
destructive measure
probabilistic behaviour
super cool
sucks
superposition (= coherence)
decoherence
Super computer
The photon as a Qubit
phi> = a↑> + b→>
can be written
phi> = a1> + b0>
quantum object used to store information: that's a Qubit !
Quantum Key Distribution
Multiple Qubits
Safe communication channel

Classical bits : independent
0 1
those two bits have no interaction between them
Qubits: entangled
2 parameters are sufficient to describe the state of the register
=> 2 classical bits carry 2 unity of information
bit1
bit2
bit1
bit2
Decoherence
a1> + b0>
a'1> + b'0>
NO!
Experience proves qubits can't be described independently. there is a strong correlation between states.
you need a new basis to describe the two bits
EPR pair and entanglement
bit1 & bit2> = w00> + x10> + y01> + z11>
What can you do ? => you code all integers up to 2^n1 on n bits AT THE SAME TIME
If you have a 2 qubits computer => you can store the following integers:
 0 coded by the physical state 00>
 1 coded by 01>
 2 coded by 10>
 3 coded by 11>
and compute all of them at the same time
00>
01>
10>
11>
bit1
bit2
No cloning principle
middle man attack hard because no cloning principle

4 parameters are need to describe the state of the register
=> 2 qubits carry 4 unity of information
exponential growth of the state space
Massive code parallelization ?
No : Destructive measure + probabilitic output => you got only one result!
Maths say so! The proof relies on Quantum mechanism axioms and particularly linearity.
Any function modifying a state phi> must be linear. You can't find such a function that copies the state of a qubit to another.
You could copy all the results before measuring ? No: No cloning theorem
You have to invent another way to code => Software challenge !
Computation:
 add bit1 and bit2
 write the result in bit3
So we compute f(n) in bit3 with n coded by bit1 and bit2 (hence n ranges from 0 to 3)
Measure all registers
w² = probability to measure state 00>
x² = probability to measure state 10>
y² = probability to measure state 01>
z² = probability to measure state 11>
bit1 & bit2> = w000> + x100> + y010> + z110>
000>
010>
100>
110>
w² = probability to measure state 000> = 0.25
x² = probability to measure state 100> = 0.25
y² = probability to measure state 010> = 0.25
z² = probability to measure state 110> = 0.25
bit1
bit2
bit3
normally we should add states 001>, 011>, 101> and 111> but we know here those are null
input register
output register
bit1 & bit2> = w000> + x101> + y011> + z110>
000>
011>
101>
110>
w² = probability to measure state 000> = 0.25
x² = probability to measure state 101> = 0.25
y² = probability to measure state 011> = 0.25
z² = probability to measure state 110> = 0.25
bit1
bit2
bit3
input register
output register
bit1
bit2
bit3
input register
output register
we only have 1 left in input register
and f(1) = 1 n output register
We can measure the couple {1, f(1)} with probability 0.25
Another problem:
Entanglement collapses at one point (Decoherence) => Hardware challenge !
"Decoherence, in brief, describes the constant, tenuous interactions between a system or object and its environment, a set of interactions that allows concrete behaviors to emerge from the multitude of simultaneous possibilities that quantum theory allows".
Schrodinger's cat is not in a superposition of states. The number of interacting particles "stabilizes" it all.
EPR pair distribution
Teleportation
Dense coding
Two dual operations:
"transmit" one qubit with two classical bits
"transmit" two classical bits on a qubit
"Spooky action at a distance"
Einstein
Thought experiment intended to reveal what they (EPR authors) believed to be inadequacies of quantum mechanics (1935).
"Deux cœurs qui ont interagi dans le passé ne peuvent plus être considérés de la même manière que s'ils ne s'étaient jamais rencontrés. Marqués à jamais par leur rencontre, ils forment un tout inséparable".Etienne Klein
two entangled photons are produced with opposed polarization
Schrodinger thought experiment
(1935)
To be done !
Gate example
http://imgur.com/gallery/a4yU9
http://en.wikipedia.org/wiki/Timeline_of_quantum_computing
 The process has to be repeated several times because the QFT may yield false results
 Most quantum algorithms : they are probabilistic and give the right answer with high probability
How to find the period of a function f on a quantum computer ?
Input register
Output register
Entangled Qubits
Initialize registers
superposition of integers from 0 to Log2(N).
All Qubits set to 0
Apply f to input register
N Qubits
superposition of integers from 0 to Log2(N).
superposition of f(n) with n integer from 0 to Log2(N).
n and f(n) are entangled
When measuring f(x), the input register collapses to the superposition of states y such that f(y) = f(x)
Measure f(x)
superposition of states x and y such that f(y) = f(x)
f(x)
f(x)
x
0
1
2
3
00>
01>
10>
11>
input register
output register
0
1
1>
0>
if we measure 1:
f(x)
x
1
3
01>
11>
input register
output register
0
1
1>
0>
Apply QFT on input register
Biggest difficulty: decoherence
Need for very low temperature, magnetic fields...
superposition of states x and y such that f(y) = f(x)
The period of f !
 Performed factorization of 15 with shor's algorithm
Classical computing poses no serious threat to the RSA system
 approximately 428 millenia to factorise a 200digit number (assuming GHz computing speed).
 Shor’s quantum algorithm would be able to factor the same number in a matter of days
Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(log N) storage space. Lov Grover formulated it in 1996.
In models of classical computation, searching an unsorted database cannot be done in less than linear time (so merely searching through every item is optimal). Grover's algorithm illustrates that in the quantum model searching can be done faster than this; in fact its time complexity O(N1/2) is asymptotically the fastest possible for searching an unsorted database in the linear quantum model.
Can find a solution in polynomial time (bounded by N^x)
N is the size of the input
difficulty of a problem
Can verify a solution in polynomial time (bounded by N^x)
Requires a space on a computer bounded by N^x
BoundedError Probabilistic PolynomialTime with error probability under 1/3
Bounded error Quantum Polynomial time with error probability under 1/3
BoundedError Probabilistic PolynomialTime with error probability under 1/2
Prospects
 Bought by Lockhead Martin, Google and Nasa
 Big controversy: is it a quantum computer ?
 In parallel, new programming techniques are required
 Link between computability and physics
Hectic, hard to follow =>
 Compute hard problems
 Harness quantum mechanics properties for security purposes
 Deepen our understanding of Physics
Beware !
> More a mathematical theory than a physical one
Polarization in photography
A basis for Qubits
Computation example
Outline of the algorithm
Quantum part
Remarks