Transcript 投影片 1

Quantum Computer
電機四 鄭仲鈞
Outline
•
•
•
•
Quantum Computer
Quantum Computing
Implement of Quantum Computer
Nowadays research of Quantum
computer
Traditional Computer
• bit: 0 or 1
• 4 bits data: 0000 0001 0010 0011…
represent 0~15 by
the combination of 0 and 1
one combination  one value
0000  0, 0001  1, 0010  2…
Quantum Computer
• Qubit( Quantum bit ): 0 and 1
bit
bit
and
0
4qubits:
=
1
qubit
?
I’m 0 and 1
 ????(weird thing)
In fact, it can represent 0~15 simultaneously
Qubit( Quantum bit)
• Any thing that has quantum property
can be a qubit.
What quantum property?
 Uncertainty of States
Uncertainty of State
• Electrons
2 Bits
1
2 Qubits
0
0/1
0/1
Material wave
State superposition
Superposition
• Superposition state:
1 x1    2 x2   ....   n xn 
1   2  ....   n  1,  i
2
2
2
{ x1 , x2 ,...., xn }
• Ex: Sup State:
Amplitude (possibility)
Orthogonal Basis
(Specific State)
1
1
0 
1
2
2
Possible States: { 0, 1}
A property of qubit
Any observation will force qubit into
a certain state.
Before observation:
superposition of 0 and 1,
but not pure 0 or 1
After observation:
must be 0 or 1.
Outline
•
•
•
•
Quantum Computer
Quantum Computing
Implement of Quantum Computer
Nowadays research of Quantum
computer
Now that we have qubit…
• A random number generator??
1/16
1/16
1/16
13/16
Must have a method to get the
answer we want.
Interference as calculation
• Wave property:
Two Qubit(electron)
can interfere each
other.
Constructive: % up
Destructive : % down
We can use wave
interference as a
calculation method.
Factoring a big number
• RSA, public-key cryptography method
Public key N which is the product of two large prime numbers.
One way to crack RSA encryption is by factoring N
Factor a number in 400 bits
– Super computer
take 1000000000 years
– Quantum computer(1000qubits)
only take few hours
But how can it do that?
Quantum Parallelism
• Traditional: N Choices.
We have to calculate:
0, 1, 2, …N time to get correct answer.
Quantum computer: N Choices into 1 value.
N calculation completed at one time
T: 63÷1, 63÷2… 63÷8 ,calculate 8times
Q: 63÷
, parallel 8 values
calculate only 1 time
qubits
Shor's algorithm
• use conventional algorithm
factor a number N in O ( e N )
• use Quantum Parallelism
factor a number N in O ( (log N )3 )
Note that
(log N )3 < N (efficient!!)
Constructive Interference:
Find peak value (perhaps the solution)
1
3
http://en.wikipedia.org/wiki/Shor's_algorithm
Shor's algorithm(con’t)
• An example:
We already have a
method to break RSA…
• Why do we still use RSA as a popular
public-key cryptography method?
Because the implement of quantum
computer (qubit) is really hard…
Outline
•
•
•
•
Quantum Computer
Quantum Computing
Implement of Quantum Computer
Nowadays research of Quantum
computer
Implement of qubits
• 1. Nuclear magnetic resonance (NMR)
• 2. Quantum dot
• 3. Ion trap
A Bloch sphere as
a schema of a qubit
NMR
Nucleus’ magnetic moment as qubit
Controlled by
EM wave
Measured by
Nuclear magnetic
resonance
2C +5F = 7 qubits
Not enough qubits
Quantum dot
Lithography and etching:
Build 2D InGaAs surface.
And then Etching the edge out.
What is quantum dot?
A small dot structure including 1-100 electrons in it.
The quantum dot’s scale must
small than Fermi wavelength.
Fermi wavelength
In GaAs (Semiconductor)
λf = 40nm
In Al (metal)
λf = 0.36nm
Where is the qubit?
• (a). Add an extract electron as
• (b). Electron spin up as
spin down as
Recently find a new way:
excited electron as
Electron density of a parabolic quantum
dot with 6 electrons in a magnetic field.
Ion trap
4 rod electrodes
AC 1kv MHz
trap the ions
Ions (cold trapped)
End-rings Charged to
prevent escaping
No AC electric field, spin direction as qubit
The problem is…
• Environment influences the states of
qubits.
• It will make the result incorrect.
By experiments,
Ion trap is the most potential one.
Outline
•
•
•
•
Quantum Computer
Quantum Computing
Implement of Quantum Computer
Nowadays research of Quantum
computer
Nowadays research
• European :
– Information Society Technologies
• United Kingdom:
– CQC( Centre for Quantum Computation)
– Oxford, Cambridge
• Australian:
Centre for Quantum Computer Technology
• Japan:
ERATO (Exploratory Research for Advanced
Technology)
Stanford and IBM
• First demonstration (in 2001)
Shor's factoring algorithm
• 7 qubits system
to find the factor of 15
• System tube including
molecule that has
7 nuclear spins
Conclusion
• Quantum computer is really powerful.
• Although Quantum computer is hard
to implement, it is still realizable.
• Quantum computer will be an
important research issue in the
future.
• It is fun to know more about such
an interesting knowledge.
A good experience
Thank you!!