Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present 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.

DeleteCancel

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.

No, thanks

An introduction to Quantum computing

No description
by

cedric cod

on 7 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript 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 sub-atomic 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 square-root 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
D-Wave
- 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> = a|1> + b|0>
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
a|1> + b|0>
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> = w|00> + x|10> + y|01> + z|11>
What can you do ? => you code all integers up to 2^n-1 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> = w|000> + x|100> + y|010> + z|110>
|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> = w|000> + x|101> + y|011> + z|110>
|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 200-digit 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
Bounded-Error Probabilistic Polynomial-Time with error probability under 1/3
Bounded error Quantum Polynomial time with error probability under 1/3
Bounded-Error Probabilistic Polynomial-Time 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 transcript