Transcript Quantum

Quantum Computing and
Quantum Programming Language
Choon Oh Lee
ISILab, KAIST
Motivation
• Moore’s Law
– Number of transistors per square inch
doubles every two years.
– Expected be broken down in 2020
• Atomic scales are reached
• Incoherent by any particle
– Solutions
• Fatalists: Noise-based Computing
• Optimists: Quantum Computing
Bit
Value
vs.
Qubit
or 1
0
5V
Realization
or
various candidates
0V
Computation
0
(Ion trap, NMR, etc.)
0
1
0
1
0
1
0
0
1
S
S
S
S
S
Q. Circuit
ADDER
S
S
S
S
S
Measuring
0
1
1
1
0
0
Universal
component
NAND and NOR gate
1
1
1
0
Controlled Not gate
How’s qubit possible?
• The legendary experiment
– By David Wineland and Christopher Monroe
– Steps
1. Pin Barium ion in vacuum room
2. Optical freezing on ion to deactivate it
3. Expose ion on laser pulse for certain time
–
Barium ion had superposition
4. Slightly push ion using laser beam
–
One ion existed on two different spots
– Remarks
• Superposition is collapsed in 25~50 microsecond
• NIST scientists succeed to make first controlled
not gate based on this experiment
Conceptual Models
Computational
Model
• Quantum Circuit
A
B
M
D
C
Algorithmic
Model
M
• Matrix Mechanics
4 by 4
2 by 2
2 by 2
2 by 2
2 by 2
2 by 1
2 by 1
Quantum Gates
• Pauli Gates
– Identity (I)
– Not Gate (X)
– Y Gate
– Z Gate
Quantum Gates
• Hadamard Gate (H)
– Make a qubit superpositioned.
Quantum Gates
• Controlled Not Gate (cNot)
– Apply NOT gate on second bit when first bit
is 1.
Quantum Gates
• Measurement (M)
– Technically, it’s not a gate
– It measures a qubit to determine its value
– Output of measurement would be 0 or 1
• Probability to be 0:
• Probability to be 1:
– After it measures qubit, qubit becomes
just bit
Algorithms
• Quantum Teleportation
– Qubits cannot be copied or moved
– How to teleport a qubit
1. Prepare two entangled qubits,
2. Alice and Bob take each qubit initially
3. Alice wants to send an another qubit to Bob
Algorithms
• Quantum Teleportation
Original
qubit
Alice’s qubit
Bob’s qubit
H
M
M
Z
Same
qubit
Algorithms
• Quantum Teleportation
Original
qubit
Alice’s qubit
Bob’s qubit
– Initial state
H
M
M
Z
Same
qubit
Algorithms
• Quantum Teleportation
Original
qubit
H
Alice’s qubit
Bob’s qubit
– Previous state
– Current state
M
M
Z
Same
qubit
Algorithms
• Quantum Teleportation
Original
qubit
H
Alice’s qubit
Bob’s qubit
– Previous state
– Current state
M
M
Z
Same
qubit
Algorithms
• Quantum Teleportation
Original
qubit
Alice’s qubit
H
M
M
Bob’s qubit
– Rearrange current state
Z
Same
qubit
Algorithms
• Quantum Teleportation
Original
qubit
Alice’s qubit
H
M
M
Bob’s qubit
– Measure first two qubits
Z
Same
qubit
Algorithms
• Grover’s Search Algorithm
– Searching desired items from database
– Instead of checking every items in database,
algorithm increases probabilities that
desired items can be found decreasing
others’
– Idea is simple,
but point is quantum parallelism!
Algorithms
• Grover’s Search Algorithm
Probability
(amplitude)2
0
1
2
3
4
5
6
7
1. Apply Hadamard gates to make superposition
Probability
(amplitude)2
0
1
2
3
4
5
6
7
Algorithms
• Grover’s Search Algorithm
Probability
(amplitude)2
0
1
2
3
4
5
6
7
2. Apply function f
Probability
(amplitude)2
0
1
2
3
4
5
6
7
Algorithms
• Grover’s Search Algorithm
Probability
(amplitude)2
Average line
0
1
2
3
4
5
6
7
3. Flip probability based on average point
Probability
(amplitude)2
Average line
0
1
2
3
4
5
6
7
Algorithms
• Shor’s Factoring Algorithm
– Great algorithm that attracted the world’s
attention to quantum computing
– Proposed shortcut to break RSA system
• The source of RSA’s power is hardness of
factorization of a big number which is product of
two prime numbers
– Best known way to factor a number, N
1.
2.
3.
4.
Find a and b where N divides (a2 – b2)
If N doesn’t divide (a + b) and (a – b),
Then, gcd(N, (a + b)) is one of factors of N
Another factor is then N / gcd(N, (a + b))
Algorithms
• Shor’s Factoring Algorithm
– Algorithm
input: an odd integer n
1. Choose g in [2…n-1] randomly
2. Calculate d = gcd(g, n)
3. If d ≠ 1, return d
4. Calculate r where gr = 1 (mod n)
5. If r is even,
and n doesn’t divide gr/2+1 or gr/2-1,
then return gcd(n, gr/2+1)
6. Re-find r or g
– Shor used superpositioned qubits to
represent g and QFT to calculate r