Transcript Introduction to Quantum Computation

Introduction to Quantum
Computation
Andris Ambainis
University of Latvia
What is quantum
computation?
New model of computing based on
quantum mechanics.
Quantum circuits, quantum Turing
machines
More powerful than conventional models.
Quantum algorithms
Factoring: given N=pq, find p and q.
1/3)
O(n
Best algorithm 2
, n -number of
digits.
Many cryptosystems based on hardness of
factoring.
O(n2) time quantum algorithm [Shor,
1994]
Similar quantum algorithm solves discrete
log.
Quantum algorithms
0 1 0 ... 0
x1 x2 x3
xn
Find if there exists i for which xi=1.
Queries: input i, output xi.
Classically, n queries.
Quantum, O(n) queries [Grover,
1996].
Speeds up exhaustive search.
Quantum cryptography
Key distribution: two parties want to
create a secret shared key by using a
channel that can be eavesdropped.
Classically: secure if discrete log hard.
Quantum: secure if quantum mechanics
valid [Bennett, Brassard, 1984].
No extra assumptions needed.
Quantum communication
Dense coding: 1 quantum bit can encode
2 classical bits.
Teleportation: quantum states can be
transmitted by sending classical
information.
Quantum protocols that send
exponentially less bits than classical.
Experiments
~10 different ideas how to implement QC.
NMR, ion traps, optical, semiconductor,
etc.
7 quantum bit QC [Knill et.al., 2000].
QKD has been implemented.
Outline
Today: basic notions, quantum key
distribution.
Tomorrow: quantum algorithms, factoring.
Friday: current research in quantum
cryptography, coin flipping.
Model
Quantum states
Unitary transformations
Measurements
Quantum bit
|1>
|0>
2-dimensional vector
of length 1.
Basis states |0>, |1>.
Arbitrary state:
|0>+|1>,
,  complex,
||2+ ||2=1.
Physical quantum bits
Nuclear spin = orientation of atom’s
nucleus in magnetic field.
 = |0>,  = |1>.
Photons in a cavity.
No photon = |0>, one photon = |1>
Physical quantum bits (2)
Energy states of an atom
|0>
ground state
|1>
excited state
Polarization of photon
Many others.
General quantum states
k-dimensional quantum system.
Basis |1>, |2>, …, |k>.
General state
1|1>+2|2>+…+k|k>,
|1|^2+…+ |k|^2=1
2k dimensional system can be constructed
as a tensor product of k quantum bits.
Unitary transformations
Linear transformations that preserve
vector norm.
In 2 dimensions, linear transformations
that preserve unit circle (rotations and
reflections).
Examples
Bit flip
| 0 | 1 

| 1 | 0 
Hamamard transform
1

| 0  2 | 0  

1
 | 1 
|0

2
1
2
1
2
|1 
|1 
Linearity
Bit flip
|0>|1>
|1>|0>
By linearity,
|0>+|1> |1>+|0>
Sufficient to specify U|0>, U|1>.
Examples
|1>
1
2
1
|0
2
|1 
|0>
1
2
|0
1
2
|1 
Measurements
Measuring |0>+|1> in basis |0>, |1>
gives:
 0 with probability | |2,
 1 with probability | |2.
Measurement changes the state: it
becomes |0> or |1>.
Repeating measurement gives the same
outcome.
Measurements
|0>
Probability 1/2
1
2
|0
1
|1>
Probability 1/2
2
|1 
General measurements
Let |0>, | 1> be two orthogonal one-qubit
states.
Then,
|> = 0|0> + 1|1>.
Measuring | > gives | i> with probability
|i|2.
This is equivalent to mapping |0>, | 1> to
|0>, |1> and then measuring.
Measurements
1
2
1
2
|0
1
2
|1 
Probability 1
|0
1
2
|1 
Measurements
|1>
1
1
2
|0
1
|1 
2
Probability 1/2
2
|0
Probability 1/2
1
2
|1 
Measurements
Measuring
1|1>+2|2>+…+k|k>
in the basis |1>, |2>, …, |k> gives |i>
with probability |i|2.
Any orthogonal basis can be used.
Partial measurements
Example: two quantum bits, measure
first.
1
1
1
2
00 
2
2
| 00  
2
10
Result 1
Result 0
1
01 
1
2
| 01 
| 10 
Classical vs. Quantum
Classical bits:
can be measured
completely,
are not changed by
measurement,
can be copied,
can be erased.
Quantum bits:
can be measured
partially,
are changed by
measurement,
cannot be copied,
cannot be erased.
Copying
One nuclear spin  Two spins
?
Impossible!
Related to impossiblity of measuring a state perfectly.
No-cloning theorem
Imagine we could copy quantum states.
| 0 | 0 | 0 
| 1 | 1 | 1 
Then, by linearity
1
2
|0
1
2
| 1 
1
2
| 0 | 0  
1
2
| 1 | 1 
Not the same as two copies of |0>+|1>.
Key distribution
Alice and Bob want to create a shared
secret key by communicating over an
insecure channel.
Needed for symmetric encryption (onetime pad, DES etc.).
Key distribution
Can be done classically.
Needs hardness assumptions.
Impossible classically if adversary has
unlimited computational power.
Quantum protocols can be secure against
any adversary.
The only assumption: quantum
mechanics.
BB84 states
|> = |1>
1
2
|  >=
|  >=
|0
1
2
1
2
|0
|1 
|> = |0>
1
2
|1 
BB84 QKD
Alice
...
Bob
...
No
Yes
Yes
...
Yes
...
0
0
1
BB84 QKD
Alice sends n qubits.
Bob chooses the same basis n/2 times.
If there is no eavesdropping/transmission
errors, they share the same n/2 bits.
Eavesdropping
Assume that Eve measures some qubits in
, | basis and resends them.
If the qubit she measures is |> or |>,
Eve resends a different state ( or |
).
If Bob chooses |>, |> basis, he gets
each answer with probability 1/2.
With probability 1/2, Alice and Bob have
different bits.
Eavesdropping
Theorem: Impossible to obtain
information about non-orthogonal states
without disturbing them.
In this protocol:
Check for eavesdropping
Alice randomly chooses a fraction of the
final string and announces it.
Bob counts the number of different bits.
If too many different bits, reject
(eavesdropper found).
If Eve measured many qubits, she gets
caught.
Next step
Alice and Bob share a string most of
which is unknown to Eve.
Eve might know a few bits.
There could be differences due to
transmission errors.
Classical post-processing
Information reconciliation: Alice and Bob
apply error correcting code to correct
transmission errors.
They now have the same string but small
number of bits might be known to Eve.
Privacy amplification: apply a hash
function to the string.
QKD summary
Alice and Bob generate a shared bit string
by sending qubits and measuring them.
Eavesdropping results in different bits.
That allows to detect Eve.
Error correction.
Privacy amplification (hashing).
Eavesdropping models
Simplest: Eve measures individual qubits.
Most general: coherent measurements.
Eve gathers all qubits, performs a joint
measurement, resends.
Security proofs
Mayers, 1998.
Lo, Chau, 1999.
Preskill, Shor, 2000.
Boykin et.al., 2000.
Ben-Or, 2000.
EPR state
1

2
1
| 0 | 0  
2
| |   
1
2
1
| 1 | 1 
2
| |  
• First qubit to Alice, second to Bob.
• If they measure, same answers.
• Same for infinitely many bases.
Bell’s theorem
Alice’s basis:
|1>
cos x 0  sin x 1
 sin x 0  cos x 1
Bob’s basis: y instead of x.
|0>
Bell’s theorem
Pr[b=0]
Pr[b=1]
Pr[a=0]
1
cos 2  x  y 
2
1 2
sin  x  y 
2
Pr[a=1]
1 2
sin  x  y 
2
1
cos 2  x  y 
2
Classical simulation
Alice and Bob share random variables.
Someone gives to them x and y.
Can they produce the right distribution
without communication?
Bell’s theorem
Classical simulation impossible:
  3 
x   ,
,
 4 4
3 

y ,  
4
4
Bell’s inequality: constraint satisfied by
any result produced by classical
randomness.
Ekert’s QKD
Alice generates n states
1
2
| 0 | 0  
1
2
| 1 | 1 
sends 2nd qubits to Bob.
They use half of states for Bell’s test.
If test passed, they error-correct/amplify
the rest and measure.
Equivalence
In BB84 protocol, Alice could prepare the
state
1
1
1
1
0   1   2 
3 
2
2
2
2
keep the first register and send the
second to Bob.
Ekert and BB84 states
UI
BB
E 
1
2
| 0 | 0  
1
| 1 | 1 
2
1
1
1
1
 0   1   2 
3 
2
2
2
2
1
1
1

U | 0  2 0  2 2  2 3

1
1
1
 U | 1 
1  2  3

2
2
2
QKD summary
Key distribution requires hardness
assumptions classically.
QKD based on quantum mechanics.
Higher degree of security.
Showed two protocols for QKD.
QKD implementations
First: Bennett et.al., 1992.
Currently: 67km, 1000 bits/second.
Commercially available: Id Quantique,
2002.
Next lectures
Tomorrow: quantum algorithms for
factoring.
Friday: quantum coin flipping.