Introduction to Quantum Computation

Document technical information

Format ppt
Size 190.0 kB
First found May 22, 2018

Document content analysis

Category Also themed
Language
English
Type
not defined
Concepts
no text concepts found

Persons

Organizations

Places

Transcript

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
sin 2  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.
×

Report this document