an Introduction to Quantum Information...

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 11

CCllaauuddee CCrrééppeeaauu

SScchhooooll ooff CCoommppuutteerr SScciieenncceeMMccGGiillll UUnniivveerrssiittyy

an Introduction toQuantum

Information Processing

an Introduction toQuantum

Information Processing

�1

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 22

((11))QQuuaannttuumm IInnffoorrmmaattiioonn

�2

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 33

Photons

�3

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 44

Photons

�4

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 55

Photons

�5

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 66

q +=

BBiittss && QQuuBBiittss

00::

11::

Cosq Sinq

+= C0 C1|YÒ0000::

0011::

1100::

1111::

+= C00|YÒ+C01+C10

C11

Ci,CijŒCC_

�6

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 77

standard notationsBBaassiiss vveeccttoorrss:: ||00ÒÒ aanndd ||11ÒÒ

�7

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 88

standard notationsBBaassiiss vveeccttoorrss:: ||00ÒÒ aanndd ||11ÒÒ

AArrbbiittrraarryy ssttaatteess:: ||yyÒÒ==aa||00ÒÒ++bb||11ÒÒssuucchh tthhaatt ||aa||22++||bb||22==11

a,b ŒCC_

�8

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 99

standard notationsBBaassiiss vveeccttoorrss:: ||00ÒÒ aanndd ||11ÒÒ

AArrbbiittrraarryy ssttaatteess:: ||yyÒÒ==aa||00ÒÒ++bb||11ÒÒssuucchh tthhaatt ||aa||22++||bb||22==11

AArrbbiittrraarryy mmuullttii--ssttaatteess::||yyÒÒ==aa||0000ÒÒ++bb||0011ÒÒ++dd||1100ÒÒ++gg||1111ÒÒ

ssuucchh tthhaatt ||aa||22++||bb||22++||dd||22++||gg||22==11

a,b,d,gŒCC_

�9

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 1133

((22))QQuuaannttuumm MMeeaassuurreemmeennttss

�10

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 1155

Polarizing Filterand photodetectors

qq ccooss22 qq

ccooss qq

qq ssiinn22 qq

ssiinn qq

Photo-multipliers

�11

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 1144

Polarizing Filteroptical axis

�12

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 1155

Polarizing Filterand photodetectors

qq ccooss22 qq

ccooss qq

qq ssiinn22 qq

ssiinn qq

�13

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 1166

Photons

�14

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 2266

Calcite Crystal

optical axis

optical axis

�15

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 2277

ccooss qq

ssiinn qq

Calcite Crystal

qq

�16

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 2288

Photons

�17

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 1177

+= C00|YÒ +C01 +C10 C11

|YÒ

|C00|2

Projective Measurements

|C01|2

|C10|2

|C11|2S|Cij|2=1

�18

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 2255

((33))QQuuaannttuumm CCoommppuuttaattiioonnss

�19

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 2299

+C0 C1

|YÒ U |Y'Ò

Quantum Evolution:Unitary Operators

U |Y0ÒU |Y1ÒU +C0 C1|Y0Ò |Y1Ò

�20

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 3300

standard notationsUUnniittaarryy OOppeerraattoorrss:: UU††UU==UUUU††==II

�21

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 3311

standard notationsUUnniittaarryy OOppeerraattoorrss:: UU††UU==UUUU††==II

lliinneeaarr:: UU((aa||00ÒÒ++bb||11ÒÒ)) == aaUU||00ÒÒ++bbUU||11ÒÒ

�22

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 3322

standard notationsUUnniittaarryy OOppeerraattoorrss:: UU††UU==UUUU††==II

lliinneeaarr:: UU((aa||00ÒÒ++bb||11ÒÒ)) == aaUU||00ÒÒ++bbUU||11ÒÒ

pprreesseerrvveess ssccaallaarr pprroodduuccttss::

((··yy||UU††))((UU||ffÒÒ))== ··yy||UU††UU||ffÒÒ == ··yy||II||ffÒÒ == ··yy||ffÒÒ

�23

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 3333

example: Hadamard

||00ÒÒ H (( ||00ÒÒ++||11ÒÒ))//√22

||11ÒÒ H (( ||00ÒÒ-- ||11ÒÒ))//√22

H == 11//√22 (( ))11 1111 --11

�24

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 2277

ccooss qq

ssiinn qq

Calcite Crystal

qq|0⟩|1⟩

©©CCllaauuddeeCCrrééppeeaauu22000022--220000882266

CalciteCrystal

opticalaxis

opticalaxis

|0⟩

�25

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 3344

||00ÒÒ

||00ÒÒ

example: Control-NOT||00ÒÒ

||00ÒÒ

||00ÒÒ

||11ÒÒ

||00ÒÒ

||11ÒÒ

||11ÒÒ

||00ÒÒ

||11ÒÒ

||11ÒÒ

||11ÒÒ

||11ÒÒ

||11ÒÒ

||00ÒÒ

==(( ))1 0 0 00 1 0 00 0 0 10 0 1 0

�26

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 3355

((44))GGeenneerraall MMeeaassuurreemmeennttss

�27

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 3366

Calcite Crystaland photodetectors

qq

ssiinn22 qq

ccooss22 qq

ccooss qq

ssiinn qq

�28

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 4400

1/2

Calcite crystal& Photodetection

1/2

�29

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 4411

1/2

Calcite crystal& Photodetection

1/2

�30

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 4422

POSSIBLE!

qq

�31

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 4433

q qq

qq

IMPOSSIBLE!

�32

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 4444

QQuuaannttuumm

CCllaassssiiccaall & Quantum Information0000111100111111000000111100 CCllaassssiiccaall

CCooppyyiinngg:: YYeess NNOO

MMeeaassuurriinngg:: YYeess ppaarrttiiaall

BBrrooaaddccaassttiinngg:: YYeess NNOO

SSuuppeerrppoossiinngg:: NNOO YYeess

IInntteerrffeerriinngg:: NNOO YYeess

�33

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 11�34

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 1188

((33))

QQuuaannttuumm KKeeyy DDiissttrriibbuuttiioonn

�35

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 3322

1/2

Calcite crystal& Photodetection

1/2

�36

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 3333

1/2

Calcite crystal& Photodetection

1/2

�37

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 3344

0 1

+

¥

Ambiguous Coding Scheme

((33..11..11)) KKeeyy ddiissttrriibbuuttiioonn

�38

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 3355

0V

400V

800V

Pockel Cells

�39

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 3366

LED Pinhole

Filter Pockel Cells

0/800V 0/400V

SENDER

�40

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 3377

LED Pinhole

Filter Light source:

~ 1/10 photon per pulse

n = #photons per pulse follows

a Poisson distribution

Pr(n≤x) = 1-e-x/10

Problem:

• may transmit multiple

correlated polarized photons

�41

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 3388

0/400V

Pockel Cell Calcite Crystal

Photo Multipliers

RECEIVER

�42

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 3399

00

00 00 00 111111000000 00 00001100

00 ææææ 00 ææ 11 ææææ 11 ææ 00 ææææææææ 11 11ææææ ææ 00 00 00¥¥ ¥¥ ¥¥¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++

¥¥ ¥¥00 00 11 11 00 11 11 00 00 00

BB:: ++ ++ ¥¥ ++ ++ ++ ¥¥ ++ ++ ¥¥ ¥¥ ¥¥ ++ ¥¥ ¥¥ ¥¥ ++ ++ ¥¥ ++ ¥¥ ++

AA::BB::

¥¥ ¥¥ ¥¥¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥11 11 11 11 11 11 11 11 11 1111

++AA:: 00 00 00 00 00 00 00 00 00 00 00 00 00

++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++

0000 00 11 11 00 11 11 00 00 00BB::11 11 11 11 11AA:: 00 00 00 00 00 00

11 11AA:: 00 00 00

ππ== == == ==BB::00 11 11 11 00 00BB::

11 11 11AA:: 00 00 00

2200%%

Q-distributionof keys

BBeennnneetttt-- BBrraassssaarrdd

»

�43

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4400

¥¥ ¥¥ ¥¥¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥11 11 11 11 11 11 11 11 11 1111

++AA:: 00 00 00 00 00 00 00 00 00 00 00 00 00

++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++

Q-distributionof keys

»

�44

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4411

00 00 00 111111000000 00 00001100¥¥ ¥¥00 00 11 11 00 11 11 00 00 00

BB:: ++ ++ ¥¥ ++ ++ ++ ¥¥ ++ ++ ¥¥ ¥¥ ¥¥ ++ ¥¥ ¥¥ ¥¥ ++ ++ ¥¥ ++ ¥¥ ++¥¥ ¥¥ ¥¥¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥

11 11 11 11 11 11 11 11 11 1111++

AA:: 00 00 00 00 00 00 00 00 00 00 00 00 00++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++

Q-distributionof keys

»

�45

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4422

00 00 00 111111000000 00 00001100¥¥ ¥¥ ¥¥¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++

¥¥ ¥¥00 00 11 11 00 11 11 00 00 00

BB:: ++ ++ ¥¥ ++ ++ ++ ¥¥ ++ ++ ¥¥ ¥¥ ¥¥ ++ ¥¥ ¥¥ ¥¥ ++ ++ ¥¥ ++ ¥¥ ++

AA::

¥¥ ¥¥ ¥¥¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥11 11 11 11 11 11 11 11 11 1111

++AA:: 00 00 00 00 00 00 00 00 00 00 00 00 00

++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++

Q-distributionof keys

»

�46

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4433

00

00 00 00 111111000000 00 00001100

00 ææææ 00 ææ 11 ææææ 11 ææ 00 ææææææææ 11 11ææææ ææ 00 00 00¥¥ ¥¥ ¥¥¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++

¥¥ ¥¥00 00 11 11 00 11 11 00 00 00

BB:: ++ ++ ¥¥ ++ ++ ++ ¥¥ ++ ++ ¥¥ ¥¥ ¥¥ ++ ¥¥ ¥¥ ¥¥ ++ ++ ¥¥ ++ ¥¥ ++

AA::BB::

¥¥ ¥¥ ¥¥¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥ ¥¥11 11 11 11 11 11 11 11 11 1111

++AA:: 00 00 00 00 00 00 00 00 00 00 00 00 00

++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++

0000 00 11 11 00 11 11 00 00 00BB::

Q-distributionof keys

»11 11 11 11 11AA:: 00 00 00 00 00 00

�47

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4444

0000 00 11 11 00 11 11 00 00 00BB::11 11 11 11 11AA:: 00 00 00 00 00 00

Q-distributionof keys

»

�48

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4455

0000 00 11 11 00 11 11 00 00 00BB::11 11 11 11 11AA:: 00 00 00 00 00 00

11 11AA:: 00 00 00

≠≠== == == ==BB:: 2200%%

Q-distributionof keys

»

≠

�49

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4466

00 11 11 11 00 00BB::11 11 11AA:: 00 00 00

2200%%

Q-distributionof keys

»

≠≠== == == ==BB:: ≠

�50

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4477

00 11 11 11 00 00BB::11 11 11AA:: 00 00 00

2200%%

Q-distributionof keys

»

�51

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4488

Q-distributionof keys

•• •• •• •• ••

• Produces raw classical key

• Observed error rate indicates amount

of eavesdropper information

• Error-correction is used to fix errors

• Random hash function is used to distill

a smaller secret classical key

•• •• •• •• ••

»

�52

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 4499

Information <--> Errors

(intercept resend)

¥¥ ¥¥ ++¥¥ ¥¥++ ++ ++ ++ ++

¥¥ ¥¥ ++¥¥ ¥¥++ ++ ++ ++ ++�53

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 5500

Mostly Identical

Partly Secret

String

X X'

E(qq)

�54

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 5511

≥d

(classical) error-

correcting codes

�55

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 5522

Identical

Partly Secret

String

X X'

E:=E(qq)+W

W:=C+X

C

W

C':=W+X'C

C'X:=C+W

�56

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 5533

Identical

Partly Secret

String

X X

E

�57

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 5544

in BB84, Eve’s information at thispoint (before privacy amplification)contains:

• results of eavesdropping

• multi-photon pulses

• error correction

�58

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 5555

Identical Secret Shorter String

through Privacy Amplification

XÆÆh(X)

h

XÆÆh(X)

EÆÆh(E)

�59

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 5566

BBCM

H( G(X) | E=e,G ) > |G(X)| - 2(|G(X)|-R(X|E=e))

k:=g(X)

g

k:=g(X)

???????????k':=g(E)??????????

�60

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 6644

((55))

PPrrooooffss ooff sseeccuurriittyy

�61

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 6655

Biham, Boyer, Boykin, Mayers, Oppenheim - 2000 -

Shor, Preskill - 2000 -

Mayers - 2001 -

Gottesman, Lo - 2003 -

Renner - 2006 -

TTiimmee--lliinnee

�62

©© CCllaauuddee CCrrééppeeaauu 22000022--22000055 6666�63

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 5599

((77))QQuuaannttuumm FFaaccttoorriinngg

�64

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 6600

Quantum Superposition

++

++

+

++

+

++

+

++

+

+

+

�65

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 6611

Quantum Superposition+

++

+

++

+

++

+

+

+

F F( ) F F( )

+

++

+

++

+

++

+

+

+

F( )F( )F( )F( )F( )F( )F( )

F( )F( )F( )F( )

�66

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 6622

QQuuaannttuumm FFaaccttoorriinngg

GGiivveenn nn==ppqq aanndd ff((nn))==((pp--11))((qq--11))iitt iiss eeaassyy ttoo ffiinndd pp aanndd qq bbeeccaauussee

ff((nn))== ((pp--11))((qq--11))==ppqq--pp--qq++11==nn--pp--((nn//pp))++11

pp++((nn//pp))++nn--ff((nn))++11==00

pp22++((nn--ff((nn))++11))pp++nn==00 hhaass ssoolluuttiioonnss::pp== ((--bb±±√√44aacc))//22aa ((aa==11,, bb==nn--ff((nn))++11,, cc==nn))p=−b±√(b2−4ac)/2a (a=1, b=n−φ(n)+1, c=n)�

67

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 6633

QQuuaannttuumm FFaaccttoorriinngg

EEuulleerr’’ss tthheeoorreemm

aaff((nn)) mmoodd nn == 11

--------------------------------------------------------------

FF((aa,,rr,,nn))::==((aarr mmoodd nn,,rr,,nn))FF((aa,,rr,,nn))::==(( ,,rr,,nn))

FF((aa,,kkff((nn)),,nn))::==(( ,,kkff((nn)),,nn))�68

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 6644

QQuuaannttuumm FFaaccttoorriinnggFF((aa,,rr,,nn))::==((aarr mmoodd nn,,rr,,nn))FF((aa11,,rr,,nn))::==(( ,,rr,,nn))FF((aa22,,rr,,nn))::==(( ,,rr,,nn))

......FF((aaii,,rr,,nn))::==(( ,,rr,,nn))

bbuutt ..FF((aa11,,kkff((nn)),,nn))::==(( ,,kkff((nn)),,nn))FF((aa22,,kkff((nn)),,nn))::==(( ,,kkff((nn)),,nn))

......FF((aaii,,kkff((nn)),,nn))::==(( ,,kkff((nn)),,nn))

�69

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 6655

QQuuaannttuumm FFaaccttoorriinnggFF((aa,,rr,,nn))::==((aarr mmoodd nn,,rr,,nn))FF((**,,rr,,nn))::==(( ,,rr,,nn)).. ==(( ,,rr,,nn))

bbuutt ..FF((**,,kkff((nn)),,nn))::==(( ,,kkff((nn)),,nn))FF((**,,kkff((nn)),,nn))::==(( ,,kkff((nn)),,nn))

using Quantum Fourrier Transform

�70

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 6666

QQuuaannttuumm FFaaccttoorriinngg(( ,,11,,nn))(( ,,22,,nn))(( ,,33,,nn))......

(( ,,ff((nn))--11,,nn))(( ,,ff((nn)),,nn))(( ,,ff((nn))++11,,nn))

......(( ,,kkff((nn)),,nn))(( ,,ff((nn))++11,,nn))

......�71

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 6677

QQuuaannttuumm FFaaccttoorriinngg

�72

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 6688

CCoonnssttrruucctt tthhee ssuuppeerrppoossiittiioonnffoorr aallll rr aanndd aallll aa ooff

((aarr mmoodd nn,,rr,,nn))

mmeeaassuurree rr,, aanndd wwiitthh hhiigghhpprroobbaabbiilliittyy rr==kkff((nn))ffoorr ssoommee iinntteeggeerr kk

rreeppeeaatt ttoo oobbttaaiinn rr’’==kk’’ff((nn))ggccdd((rr,,rr’’)) == ff((nn))..

QQuuaannttuumm FFaaccttoorriinngg

�73

©© CCllaauuddee CCrrééppeeaauu 22000022--22000088 11

CCllaauuddee CCrrééppeeaauu

SScchhooooll ooff CCoommppuutteerr SScciieenncceeMMccGGiillll UUnniivveerrssiittyy

an Introduction toQuantum

Information Processing

an Introduction toQuantum

Information Processing

�74