A Semidefinite Programming Formulation of Quantum and

A S

em

ide

fin

ite P

rog

ram

min

g

A S

em

ide

fin

ite P

rog

ram

min

g

Fo

rmu

lati

on

of

Qu

an

tum

an

d

Fo

rmu

lati

on

of

Qu

an

tum

an

d

Cla

ssic

al

Ora

cle

Pro

ble

ms

Cla

ssic

al

Ora

cle

Pro

ble

ms

Mik

e M

ulla

n a

nd E

manuel

Mik

e M

ulla

n a

nd E

manuel K

nill

Knill

Univ

ers

ity o

f C

olo

rado a

t B

ould

er

and the

Univ

ers

ity o

f C

olo

rado a

t B

ould

er

and the

National In

stitu

te o

f S

tandard

s a

nd T

echnolo

gy

National In

stitu

te o

f S

tandard

s a

nd T

echnolo

gy

Ou

tlin

eO

utl

ine

1.

1.

Se

mid

efin

ite

Pro

gra

mm

ing

Fo

rmu

latio

n o

f Q

ua

ntu

m

Se

mid

efin

ite

Pro

gra

mm

ing

Fo

rmu

latio

n o

f Q

ua

ntu

m

Co

mp

uta

tio

n

Co

mp

uta

tio

n [

2,3

][2

,3]

••C

an c

alc

ula

te

Ca

n c

alc

ula

te e

xact

exact

err

or

pro

bab

ilities f

or

a q

ua

ntu

m

err

or

pro

bab

ilities f

or

a q

ua

ntu

m

com

pute

r optim

ally

so

lvin

g a

rbitra

ry q

uantu

m o

racle

com

pute

r optim

ally

so

lvin

g a

rbitra

ry q

uantu

m o

racle

pro

ble

ms

pro

ble

ms

2.

2.

Re

mo

te S

tate

Pre

pa

ratio

n,

an

d a

Ge

ne

raliz

ed

R

em

ote

Sta

te P

rep

ara

tio

n,

an

d a

Ge

ne

raliz

ed

O

bje

ctive

Ob

jective

3.

3.

Re

str

icte

d C

om

pu

tatio

nR

estr

icte

d C

om

pu

tatio

n

••D

ecoh

ere

nce a

nd a

na

lyzin

g a

co

mputa

tion s

ubje

ct

to

Decoh

ere

nce a

nd a

na

lyzin

g a

co

mputa

tion s

ubje

ct

to

no

ise

no

ise

••O

ptim

al alg

orith

ms u

sin

g r

educed

quantu

m r

esourc

es

Optim

al alg

orith

ms u

sin

g r

educed

quantu

m r

esourc

es

(briefly)

(briefly)

4.

4.

Qu

an

tum

Clo

cks

Qu

an

tum

Clo

cks

Qu

an

tum

Alg

ori

thm

s, G

en

eri

cally

Qu

an

tum

Alg

ori

thm

s, G

en

eri

cally

Qu

an

tum

Qu

ery

Alg

ori

thm

:A

rbitra

ry u

nitary

opera

tors

inte

rspers

ed w

ith o

racle

opera

tors

acting o

n s

om

e in

itia

l

sta

te, fo

llow

ed b

y a

measure

men

t

Sem

idefi

nit

e P

rog

ram

min

g:

Lin

ear

pro

gra

mm

ing w

ith

sem

idefin

ite c

onstr

ain

ts

| ψ(t)〉=UtΩUt−1Ω...ΩU0| ψ(0)〉

Go

al: M

inim

ize t

he n

um

ber

of

queri

es o

f a q

ua

ntu

m q

uery

alg

ori

thm

via

a g

en

era

lizatio

n o

f A

mba

inis

’advers

ary

meth

od

[1]

(and r

ecent

pro

gre

ss g

iven

in [

8])

Try

to e

xpre

ss a

quan

tum

query

alg

ori

thm

as a

sem

idefin

ite

pro

gra

m (

SD

P) :

Gro

ver

Gro

ver ’’

s A

lgo

rith

ms A

lgo

rith

m

0000

1100

U=

Invers

ion a

bo

ut

the M

ean

1.

2.

3.

4.

5.|ψ(0)〉=|0〉

U0|ψ(0)〉=1 2(|0〉+

|1〉+

|2〉+

|3〉)

U1ΩU0|ψ(0)〉=|1〉

Ω3

Ω0Ω1Ω2

ΩU0|ψ(0) 〉=1 2( |0〉−

|1〉+

|2〉+

|3〉)

ΩU0|ψ(0) 〉=1 2

( (−1)Ω

0|0〉+

( −1)Ω

1|1〉+

( −1)Ω2|2〉+

( −1)Ω3|3〉)

ai→

−ai+2∗〈a〉

Go

al: S

earc

h –

Fin

d the m

ark

ed e

lem

ent

Ω|ψ(t)〉=∑ i

aiΩ|i〉→∑ i

ai(−1)Ωi|i〉

Oth

er

Ora

cle

s A

re P

ossib

leO

ther

Ora

cle

s A

re P

ossib

le

0000

0011

0000

1100

We c

an a

lso h

ave

: 1100

0000

0011

0000

Assum

e e

ach o

racle

can b

e g

ive

n t

o o

ur

com

pute

r w

ith s

om

e p

roba

bili

ty

New

Go

al: F

ind t

he m

ark

ed e

lem

ent

→

Identify

the a

pplie

d o

racle

Ω(0)

Ω(1)

Ω(2)

Ω(3)

ρO=∑ x,y

√px√py|x〉〈y|

Q: Q

uerier

syste

m

ρQ=∑ i,j

ai,j|i〉〈j|

O: O

racle

syste

m

Pure

sta

te o

ver

possib

le o

racle

s

Th

e C

om

pu

ter

Th

e C

om

pu

ter

A:

Ancill

a

ρO=∑ x,y

√px√py|x〉〈y|

Q: Q

uerier

syste

m

ρQ=∑ i,j

ai,j|i〉〈j|

O: O

racle

syste

m

ΩOQ=∑ x

|x〉〈x|ΩQ(x)

Pure

sta

te o

ver

possib

le o

racle

s

Th

e C

om

pu

ter

Th

e C

om

pu

ter

A:

Ancill

a

ρO=∑ x,y

√px√py|x〉〈y|

Q: Q

uerier

syste

m

ρQ=∑ i,j

ai,j|i〉〈j|

O: O

racle

syste

m

ΩOQ=∑ x

|x〉〈x|ΩQ(x)

Pure

sta

te o

ver

possib

le o

racle

s

Th

e C

om

pu

ter

Th

e C

om

pu

ter

A:

Ancill

a

ΩOQ(|x〉O⊗|ψ〉Q)→(|x〉O⊗ΩQ(x)|ψ〉Q)

Th

e In

itia

l Jo

int

Den

sit

y M

atr

ixT

he In

itia

l Jo

int

Den

sit

y M

atr

ix

ρOQ(0)=∑ x,y

∑ i,j

√px√py|x〉〈y|⊗

ai,j|i〉〈j|

ρOQ(0)=

√p0√p0

(a0,0

a0,1

a1,0

. ..

)√p0√p1

(a0,0

a0,1

a1,0

. ..

)

√p1√p0

(a0,0

a0,1

a1,0

. ..

). ..

ρQ(0)

Th

e In

itia

l Jo

int

Den

sit

y M

atr

ixT

he In

itia

l Jo

int

Den

sit

y M

atr

ix

ρOQ=

√p0√p0Ω(0)†

(a0,0

a0,1

a1,0

. ..

)

Ω(0)

√p0√p1Ω(0)†

(a0,0

a0,1

a1,0

. ..

)

Ω(1)

√p1√p0Ω(1)†

(a0,0

a0,1

a1,0

. ..

)

Ω(0)†

. ..

ρOQ(0)=∑ x,y

∑ i,j

√px√py|x〉〈y|⊗

ai,j|i〉〈j|

ρOQ(0)=

√p0√p0

(a0,0

a0,1

a1,0

. ..

)√p0√p1

(a0,0

a0,1

a1,0

. ..

)

√p1√p0

(a0,0

a0,1

a1,0

. ..

). ..

Ω†ρOQ(0)Ω→∑ x,y

∑ i,j

√px√py| x〉〈y|⊗Ω(x)†ai,j| i〉〈 j| Ω(y)

ρQ(0)

Qu

an

tum

Alg

ori

thm

Q

uan

tum

Alg

ori

thm

→→S

DP

(1)

SD

P (

1)

ρOQ

Ne

ed b

oth

an o

bje

ctive a

nd a

set

of lin

ear

constr

ain

ts o

ver

(Str

aig

htf

orw

ard

) C

on

str

ain

ts

ρOQ(t)≥0,

ρO(t)≥0

ρO(t)=trQ(ρOQ(t))

ρO(0)=ρ0

t∈0...tf

Qu

an

tum

Alg

ori

thm

Q

uan

tum

Alg

ori

thm

→→S

DP

(2)

SD

P (

2)

|ψ(t)〉=UtΩUt−1Ω...ΩU0|ψ(0)〉

ρO(t)=trQA(U

†QA

tΩ†OQρOQA(t−1)ΩOQUQA

t)

Qu

an

tum

Alg

ori

thm

Q

uan

tum

Alg

ori

thm

→→S

DP

(2)

SD

P (

2)

|ψ(t)〉=UtΩUt−1Ω...ΩU0|ψ(0)〉

ρO(t)=trQA(U

QA

tU†QA

tΩ†OQρOQA(t−1)Ω

OQ)

ρO(t)=trQA(U

†QA

tΩ†OQρOQA(t−1)ΩOQUQA

t)

Qu

an

tum

Alg

ori

thm

Q

uan

tum

Alg

ori

thm

→→S

DP

(2)

SD

P (

2)

|ψ(t)〉=UtΩUt−1Ω...ΩU0|ψ(0)〉

ρO(t)=trQ(Ω

†OQρOQ(t−1)ΩOQ)

ρO(t)=trQA(U

QA

tU†QA

tΩ†OQρOQA(t−1)Ω

OQ)

ρO(t)=trQA(U

†QA

tΩ†OQρOQA(t−1)ΩOQUQA

t)

Qu

an

tum

Alg

ori

thm

Q

uan

tum

Alg

ori

thm

→→S

DP

(2)

SD

P (

2)

Lea

ds t

o the S

DP

SE,corr

espond

ing

to the a

pplic

ation o

f

ora

cle

and u

nitary

opera

tors

as a

bove

|ψ(t)〉=UtΩUt−1Ω...ΩU0|ψ(0)〉

SE=

ρOQ(t)≥0,ρO(t)≥0

ρO(t)=trQ(ρOQ(t))

ρO(t)=trQ(Ω

†OQρOQ(t−1)Ω

OQ)

ρO(0)=ρ0

t∈0...tf

ρO(t)=trQ(Ω

†OQρOQ(t−1)ΩOQ)

ρO(t)=trQA(U

QA

tU†QA

tΩ†OQρOQA(t−1)Ω

OQ)

ρO(t)=trQA(U

†QA

tΩ†OQρOQA(t−1)ΩOQUQA

t)

Measu

rem

en

t an

d R

em

ote

Sta

te P

rep

ara

tio

nM

easu

rem

en

t an

d R

em

ote

Sta

te P

rep

ara

tio

n

The f

ollo

win

g p

roto

co

l describes t

he m

easure

ment

pro

cess a

t th

e e

nd o

f th

e c

om

puta

tion a

t tim

e t

f. [6

]

1.

Q m

akes a

measure

ment

with a

ny c

om

ple

te P

OV

MP

QA

i i

Measu

rem

en

t an

d R

em

ote

Sta

te P

rep

ara

tio

nM

easu

rem

en

t an

d R

em

ote

Sta

te P

rep

ara

tio

n

The f

ollo

win

g p

roto

co

l describes t

he m

easure

ment

pro

cess a

t th

e e

nd o

f th

e c

om

puta

tion a

t tim

e t

f. [6

]

1.

Q m

akes a

measure

ment

with a

ny c

om

ple

te P

OV

M

2.

Co

nd

itio

na

l on m

easure

ment

outc

om

e i, th

e o

racle

syste

m s

tate

is (

up t

o n

orm

aliz

ation)

PQA

i i

σi=trQA(P

QA

iρOQA(tf))

Measu

rem

en

t an

d R

em

ote

Sta

te P

rep

ara

tio

nM

easu

rem

en

t an

d R

em

ote

Sta

te P

rep

ara

tio

n

The f

ollo

win

g p

roto

co

l describes t

he m

easure

ment

pro

cess a

t th

e e

nd o

f th

e c

om

puta

tion a

t tim

e t

f. [6

]

1.

Q m

akes a

measure

ment

with a

ny c

om

ple

te P

OV

M

2.

Co

nd

itio

na

l on m

easure

ment

outc

om

e i, th

e o

racle

syste

m s

tate

is (

up t

o n

orm

aliz

ation)

3. W

e m

easure

a c

ost fu

nction A

ion t

his

rem

ote

ly

pre

pare

d s

tate

, w

hic

h ind

icate

s h

ow

successfu

l our

alg

ori

thm

was

PQA

i i

σi=trQA(P

QA

iρOQA(tf))

Measu

rem

en

t an

d R

em

ote

Sta

te P

rep

ara

tio

nM

easu

rem

en

t an

d R

em

ote

Sta

te P

rep

ara

tio

n

The f

ollo

win

g p

roto

co

l describes t

he m

easure

ment

pro

cess a

t th

e e

nd o

f th

e c

om

puta

tion a

t tim

e t

f. [6

]

1.

Q m

akes a

measure

ment

with a

ny c

om

ple

te P

OV

M

2.

Co

nd

itio

na

l on m

easure

ment

outc

om

e i, th

e o

racle

syste

m s

tate

is (

up t

o n

orm

aliz

ation)

3. W

e m

easure

a c

ost fu

nction A

ion t

his

rem

ote

ly

pre

pare

d s

tate

, w

hic

h ind

icate

s h

ow

successfu

l our

alg

ori

thm

was

Q’s

PO

VM

is u

nco

nstr

ain

ed,

but th

e s

et

of sta

tes t

hat can b

e

pre

pare

d o

n O

is r

estr

icte

d b

y:

PQA

i i

σi=trQA(P

QA

iρOQA(tf))

∑iσO i=ρO(tf)

Th

e C

om

ple

te S

DP

Th

e C

om

ple

te S

DP

S=SM∪SE

SE=

ρOQ(t)≥0,ρO(t)≥0

ρO(t)=trQ(ρOQ(t))

ρO(t)=trQ(Ω

†OQρOQ(t−1)Ω

OQ)

ρO(0)=ρ0

t∈0...tf

SM=

Minimize∑ i

tr(σiA

i)subjectto:

∀ iσi≥0

∑ i

σO i=ρO(tf)

Co

nven

tio

nal C

ost

Fu

ncti

on

Co

nven

tio

nal C

ost

Fu

ncti

on

E

ach m

easure

ment

outc

om

e

Each m

easure

ment

outc

om

e ii

corr

espon

ds to t

he

corr

espon

ds to t

he

queri

er

queri

er ’’

ssguess o

f w

hic

h o

racle

was a

pp

lied

guess o

f w

hic

h o

racle

was a

pp

lied

S

earc

h:

Searc

h:

i =

2i =

2––

The m

ark

ed e

lem

ent is

in p

ositio

n

The m

ark

ed e

lem

ent is

in p

ositio

n 22

A

vera

ge P

roba

bili

ty o

f E

rror:

Pro

bab

ility

that you h

ad

Avera

ge P

roba

bili

ty o

f E

rror:

Pro

bab

ility

that you h

ad

ora

cle

ora

cle

xx, m

easure

d o

utc

om

e

, m

easure

d o

utc

om

e ii, and t

hat you s

hou

ldn

, and t

hat you s

hou

ldn

’’ t t

measure

outc

om

e

measure

outc

om

e ii

on o

racle

on o

racle

xx

Searc

h:

Searc

h:

x =

1000, i =

2

x =

1000, i =

2

T

his

err

or

pro

bab

ility

will

be

This

err

or

pro

bab

ility

will

be e

xa

ct

exa

ct .

Q

is fre

e to c

hoose

. Q

is fre

e to c

hoose

the P

OV

M w

hic

h o

ptim

izes t

he c

ost fu

nction

, and t

he

the P

OV

M w

hic

h o

ptim

izes t

he c

ost fu

nction

, and t

he

SD

P w

ill f

ind t

his

optim

um

subje

ct to

its

constr

ain

ts.

SD

P w

ill f

ind t

his

optim

um

subje

ct to

its

constr

ain

ts.

(σi)x,x=P(measuredi∩oracle=x)

ǫ=∑i

∑x:x =i(σi)x,x

〈x|Ai|x〉=

1−δ(i,x)

Restr

icte

d C

om

pu

tati

on

Restr

icte

d C

om

pu

tati

on

A

ll e

xp

eri

me

nta

lly a

va

ilab

le q

ua

ntu

m

All

exp

eri

me

nta

lly a

va

ilab

le q

ua

ntu

m

co

mp

ute

rs a

re s

ub

ject

to n

ois

e

co

mp

ute

rs a

re s

ub

ject

to n

ois

e

D

eco

he

ren

ce

ca

n r

ed

uce

or

elim

ina

te a

ny

De

co

he

ren

ce

ca

n r

ed

uce

or

elim

ina

te a

ny

qu

an

tum

ad

va

nta

ge

.q

ua

ntu

m a

dva

nta

ge

.

A

ll cu

rre

nt,

ge

ne

ral q

ua

ntu

m lo

we

r b

ou

nd

A

ll cu

rre

nt,

ge

ne

ral q

ua

ntu

m lo

we

r b

ou

nd

me

tho

ds a

ssu

me

pe

rfe

ct

qua

ntu

m

me

tho

ds a

ssu

me

pe

rfe

ct

qua

ntu

m

co

mp

uta

tio

n.

co

mp

uta

tio

n.

W

e w

ou

ld lik

e a

wa

y t

o c

ha

racte

rize

ho

w

We

wo

uld

lik

e a

wa

y t

o c

ha

racte

rize

ho

w

““ qu

an

tum

qu

an

tum

””o

ur

de

vic

e is

ou

r d

evic

e is

Deco

here

nce

Deco

here

nce

Aft

er

each q

uery

, th

e e

nvironm

ent

will

inte

ract

with

the c

om

pute

r and w

ill d

eco

here

the q

ueri

er

[11]

Po

st

Un

itary

, P

re-Q

uery

|ψ(0)〉OQE=∑ x,i

ax x,i|x〉O|i〉Q|ǫ 0〉E

1

Deco

here

nce

Deco

here

nce

Aft

er

each q

uery

, th

e e

nvironm

ent

will

inte

ract

with

the c

om

pute

r and w

ill d

eco

here

the q

ueri

er

[11]

Po

st

Un

itary

, P

re-Q

uery

Po

st

Qu

ery

The s

ize o

f th

e e

nviro

nm

ent

gro

ws w

ith e

very

query

,

so a

t tim

e t:

|ψ(0)〉OQE=∑ x,i

ax x,i|x〉O|i〉Q|ǫ 0〉E

1

|ψ(1)〉OQE=∑ x,i

ax i,a|x〉O(−1)Ω(x) i|i〉Q|ǫ i〉E

1|ǫ 0〉E

2

E(t)≡E=E1⊗E2...⊗Et

Ad

din

g t

he E

nvir

on

men

t A

dd

ing

th

e E

nvir

on

men

t

Q: Q

uerier

syste

mA

: A

ncill

a

O:

Ora

cle

Syste

mE

1E

t2

E:

The e

nviro

nm

ent

is p

art

of th

e o

racle

syste

m that th

e q

ueri

er

has n

o a

ccess t

o,

but

acts

on the q

ueri

er

during e

ach q

uery

.

Th

e E

xte

nd

ed

SD

PT

he E

xte

nd

ed

SD

P

Minimizetr(∑

iσiA

i)subjectto:

∀ iσOE

i≥0

ρOQE(t)≥0,ρOE(t)≥0

∑ i

σOE

i=ρOE(T)

ρOE(t)=trQ(ρOQE(t))

ρOE(t)=trQ(D

†QEtΩ†OQρOQE(t−1)⊗|ǫ 0〉E

t

Et〈ǫ0|ΩOQDQEt)

ρOE(0)=ρ0

t∈0...tf

Qu

an

tum

/Cla

ssic

al In

terp

ola

tio

nQ

uan

tum

/Cla

ssic

al In

terp

ola

tio

n

One o

r m

ore

qubits m

ay d

ecohere

independently w

ith p

robabili

ty p

Red:

One q

ub

it

decoh

ere

nce

Gre

en:

Tw

o q

ubit

decoh

ere

nce

|x〉O|i〉Q|ǫ 0〉E→√1−p|x〉O(−1)Ω(x) i|i〉Q|ǫ 0〉E+√p|x〉O(−1)Ω(x) i|i〉Q|ǫ(i)〉E

Co

mm

en

tsC

om

men

ts

T

he s

ize o

f th

e S

DP

gro

ws r

apid

ly, part

icula

rly w

he

n

The s

ize o

f th

e S

DP

gro

ws r

apid

ly, part

icula

rly w

he

n

mode

ling

mode

ling d

ecoh

ere

nce

decoh

ere

nce

. (

< 1

0 q

ub

its )

. (

< 1

0 q

ub

its )

S

ince t

he S

DP

outp

uts

the o

ptim

al density m

atr

ix a

t S

ince t

he S

DP

outp

uts

the o

ptim

al density m

atr

ix a

t every

tim

e s

tep,

we c

an r

econstr

uct th

e inte

revery

tim

e s

tep,

we c

an r

econstr

uct th

e inte

r --query

query

un

itaries

un

itaries,

and h

ence the o

ptim

al alg

ori

thm

, and h

ence the o

ptim

al alg

ori

thm

W

e h

ave r

ecently e

xp

lore

d t

hese issu

es f

rom

an

We h

ave r

ecently e

xp

lore

d t

hese issu

es f

rom

an

altern

ate

ang

le b

y a

skin

g:

altern

ate

ang

le b

y a

skin

g:

Is there

an e

qu

ally

optim

al

Is there

an e

qu

ally

optim

al

alg

ori

thm

that

uses f

ew

er

qua

ntu

m r

eso

urc

es?

alg

ori

thm

that

uses f

ew

er

qua

ntu

m r

eso

urc

es?

U

se a

n a

ltern

ate

SD

P w

hic

h tries to s

plit

the o

ptim

al alg

orith

m

Use a

n a

ltern

ate

SD

P w

hic

h tries to s

plit

the o

ptim

al alg

orith

m

into

tw

o o

r m

ore

part

s that can b

e c

lassic

ally

com

bin

ed

into

tw

o o

r m

ore

part

s that can b

e c

lassic

ally

com

bin

ed

U

se the V

on N

eum

ann e

ntr

opy to q

uantify

the q

uantu

m

Use the V

on N

eum

ann e

ntr

opy to q

uantify

the q

uantu

m

resourc

es n

eeded in e

ach b

ranch

resourc

es n

eeded in e

ach b

ranch

S

ee s

lides a

t end o

f ta

lk f

or

deta

ilsS

ee s

lides a

t end o

f ta

lk f

or

deta

ils

Clo

cks

Clo

cks

O

ur

SD

P f

orm

ula

tio

n is h

igh

ly g

en

era

l, a

nd

ca

n

Ou

r S

DP

fo

rmu

latio

n is h

igh

ly g

en

era

l, a

nd

ca

n

de

scri

be

qu

an

tum

d

escri

be

qu

an

tum

pro

ce

ss

es

pro

ce

ss

es

as w

ell

as q

ua

ntu

m

as w

ell

as q

ua

ntu

m

qu

ery

alg

ori

thm

sq

ue

ry a

lgo

rith

ms

S

pe

cific

ally

, if a

n e

lem

en

t d

raw

n f

rom

a c

on

tin

uo

us

Sp

ecific

ally

, if a

n e

lem

en

t d

raw

n f

rom

a c

on

tin

uo

us

se

t o

f u

nita

ry o

pe

rato

rs,

ind

exe

d b

y s

om

e

se

t o

f u

nita

ry o

pe

rato

rs,

ind

exe

d b

y s

om

e

pa

ram

ete

r, a

cts

on a

sta

te, o

ur

form

ula

tio

n c

an

be

p

ara

me

ter,

acts

on a

sta

te, o

ur

form

ula

tio

n c

an

be

u

se

d t

o o

ptim

ally

estim

ate

the

va

lue

of

this

u

se

d t

o o

ptim

ally

estim

ate

the

va

lue

of

this

p

ara

me

ter

pa

ram

ete

r

W

e w

ill u

se

th

is ide

a t

o o

ptim

ize

th

e a

ccu

racy o

f W

e w

ill u

se

th

is ide

a t

o o

ptim

ize

th

e a

ccu

racy o

f q

ua

ntu

m c

locks

qu

an

tum

clo

cks

G

oa

lG

oa

l : E

xp

ress t

he o

pe

ratio

n o

f th

e a

qu

an

tum

:

Exp

ress t

he o

pe

ratio

n o

f th

e a

qu

an

tum

clo

ck a

s a

bla

ck b

ox o

racle

pro

ble

m.

clo

ck a

s a

bla

ck b

ox o

racle

pro

ble

m.

Ato

mic

Clo

ck B

asic

sA

tom

ic C

lock B

asic

s

C

ount

the tic

ks o

f som

e

Co

unt

the tic

ks o

f som

e

peri

od

ic s

yste

m a

nd inte

rpre

t peri

od

ic s

yste

m a

nd inte

rpre

t as t

ime.

as t

ime.

A

tom

s h

ave a

dis

cre

te s

et

of

Ato

ms h

ave a

dis

cre

te s

et

of

energ

y levels

an

d c

an

energ

y levels

an

d c

an

transitio

n b

etw

ee

n t

hem

by

transitio

n b

etw

ee

n t

hem

by

absorb

ing o

r em

itting p

hoto

ns.

absorb

ing o

r em

itting p

hoto

ns.

(

E =

(

E =

hf

hf

))

A

tom

ic c

locks c

ount th

e

Ato

mic

clo

cks c

ount th

e

oscill

ations o

f a laser

wh

ose

oscill

ations o

f a laser

wh

ose

frequency is s

tabili

ze

d to s

om

e

frequency is s

tabili

ze

d to s

om

e

ato

mic

tra

nsitio

nato

mic

tra

nsitio

n

1 s

econd

1 s

econd ªª

9,1

92,6

31,7

70

9,1

92,6

31,7

70

cycle

s o

f th

e r

adia

tion

cycle

s o

f th

e r

adia

tion

corr

espo

nd

ing t

o a

hyperf

ine

corr

espo

nd

ing t

o a

hyperf

ine

transitio

n in C

esiu

mtr

ansitio

n in C

esiu

mN

IST

F1

Sp

ectr

osco

py

Sp

ectr

osco

py

•T

his

acts

as o

ur

bla

ck b

ox/o

racle

opera

tion

.

Go

al:

Phase E

stim

atio

n

•C

onsid

er

a s

et

of N

ions a

nd t

he s

et

of sta

tes labe

led

by

wh

ich h

ave

kio

ns in t

he e

xcited s

tate

and N

-k

ions in t

he

gro

un

d s

tate

. (

Dic

ke

sta

tes)

•O

ver

tim

e, our

laser/

cla

ssic

al o

scill

ato

r w

ill d

rift fro

m the

ato

mic

resona

nce.

We n

eed t

o m

easure

and c

orr

ect th

is

detu

nin

g.

•A

fter

an in

terr

ogation p

eri

od o

f le

ngth

T w

ith a

laser

tuned n

ear

resona

nce [

7]

| k〉

|k〉→

e−ik(f−f0)T|k〉

Fre

qu

en

cy P

rio

rs a

nd

th

e C

lock O

racle

Fre

qu

en

cy P

rio

rs a

nd

th

e C

lock O

racle

Giv

en f

-f 0

we k

now

that:

We d

on’t k

no

w f -

f 0, but

we c

an c

onstr

uct

a p

rior

pro

ba

bili

ty

dis

trib

utio

n o

ver

f -

f 0. Lik

ew

ise,

befo

re,

we d

idn’t k

no

w w

hic

h

ora

cle

our

alg

ori

thm

wo

uld

be g

iven,

so w

e a

ssig

ned

each a

pro

bab

ility

.

|k〉→

e−ik(f−f0)T|k〉

T. R

osenband, N

IST

Clo

ck S

DP

Clo

ck S

DP

Aft

er

on

e q

ue

ry

Ω=∑ x

|x〉〈x|e−

i∆fxσzT/2

ρO=∑ x,y

√px√py|x〉〈y|

Ω†ρOQΩ→∑ x,y

∑ k,l

ax,y,k,l|x〉〈y|⊗

ei∆fxkT|k〉〈l|e

−i∆fylT

ρQ=∑ k,l

ak|k〉〈l |

Go

als

:

1.

Dete

rmin

e o

ptim

al

initia

l sta

te o

f Q

2.

Dete

rmin

e

optim

al m

easure

me

nt

Clo

ck C

ost

Fu

ncti

on

Clo

ck C

ost

Fu

ncti

on

M

easure

with a

dis

cre

te,

com

ple

te P

OV

M

Measure

with a

dis

cre

te,

com

ple

te P

OV

M

whose e

lem

ents

each c

orr

espond t

o a

fre

que

ncy g

uess,

whose e

lem

ents

each c

orr

espond t

o a

fre

que

ncy g

uess,

∆∆ff ii

R

em

ote

Sta

te P

repara

tion:

Rem

ote

Sta

te P

repara

tion:

P

en

aliz

e g

uesses f

ar

from

the tru

e f

requency

Pen

aliz

e g

uesses f

ar

from

the tru

e f

requency

F

rom

the fin

al density m

atr

ix a

nd t

he r

em

ote

ly p

repare

d

Fro

m the fin

al density m

atr

ix a

nd t

he r

em

ote

ly p

repare

d

mix

ed s

tate

s, w

e c

an r

econstr

uct th

is o

ptim

al P

OV

M

mix

ed s

tate

s, w

e c

an r

econstr

uct th

is o

ptim

al P

OV

M

σi=trQ(P

Q iρOQ)

(σi)x,x=P(measured∆fi∩frequency

=∆fx)

PQ i i.

〈 ∆fx| Ai| ∆fx〉 =

(∆fi−∆fx)2

Dis

cu

ssio

nD

iscu

ssio

n

P

rio

r w

ork

ha

s a

ssu

me

d a

un

ifo

rm p

rob

ab

ility

P

rio

r w

ork

ha

s a

ssu

me

d a

un

ifo

rm p

rob

ab

ility

dis

trib

utio

n o

ve

r clo

ck o

racle

s.

dis

trib

utio

n o

ve

r clo

ck o

racle

s.

[4]

[4]

T

his

te

ch

niq

ue

is s

ub

ject

to

Th

is t

ech

niq

ue

is s

ub

ject

to d

iscre

tizatio

nd

iscre

tizatio

ne

rro

re

rro

r

W

ork

ing

on

bo

un

ds

Wo

rkin

g o

n b

ou

nd

s ––

err

or

ap

pe

ars

sm

all

err

or

ap

pe

ars

sm

all

A

lA

l++C

lock a

t N

IST

is a

na

tura

l a

pp

lica

tio

n o

f th

is

Clo

ck a

t N

IST

is a

na

tura

l a

pp

lica

tio

n o

f th

is

tech

niq

ue

. U

se

s o

nly

1te

ch

niq

ue

. U

se

s o

nly

1-- 2

io

ns a

nd

is th

e m

ost

2 io

ns a

nd

is th

e m

ost

accu

rate

clo

ck in

th

e w

orl

d (

8.6

x 1

0a

ccu

rate

clo

ck in

th

e w

orl

d (

8.6

x 1

0-- 1

818

) ) [5

,9]

[5,9

]

Resu

lts

Resu

lts

•O

ptim

al in

itia

l sta

tes h

ave e

qua

l am

plit

ud

es for

kio

ns in t

he

excited s

tate

and N

–k

in t

he g

round s

tate

. e

.g. fo

r N

= 3

:

•O

ne q

uery

on 2

ions is e

quiv

ale

nt to

2 q

ueri

es o

n o

ne ion.

Not

necessari

ly t

rue w

ith m

ore

ion

s a

nd m

ore

querie

s.

|ψ0〉=

a0(|0〉+

|3〉)+a1(|1〉+

|2〉)

A n

arr

ow

er

poste

rior

corr

espo

nd

s to a

n incre

ase

in k

no

wle

dge.

Gre

en:

Priors

Re

d:

Poste

riors

P(∆f|∆fi=0)

Co

nclu

sio

ns

Co

nclu

sio

ns

T

his

SD

P f

orm

ula

tio

n is a

po

we

rfu

l a

nd

hig

hly

T

his

SD

P f

orm

ula

tio

n is a

po

we

rfu

l a

nd

hig

hly

ge

ne

ral w

ay o

f d

escri

bin

g q

ua

ntu

m a

lgo

rith

ms a

nd

g

en

era

l w

ay o

f d

escri

bin

g q

ua

ntu

m a

lgo

rith

ms a

nd

qu

an

tum

pro

ce

sse

sq

ua

ntu

m p

roce

sse

s

T

he

siz

e o

f th

e S

DP

gro

ws q

uic

kly

, bu

t th

is

Th

e s

ize

of

the

SD

P g

row

s q

uic

kly

, bu

t th

is

tech

niq

ue

re

ma

ins a

pp

lica

ble

to

ma

ny in

tere

stin

g

tech

niq

ue

re

ma

ins a

pp

lica

ble

to

ma

ny in

tere

stin

g

pro

ble

ms.

pro

ble

ms.

H

ere

we

an

aly

ze

d q

ua

ntu

m c

om

pu

ters

su

bje

ct to

H

ere

we

an

aly

ze

d q

ua

ntu

m c

om

pu

ters

su

bje

ct to

de

co

he

ren

ce

de

co

he

ren

ce

, a

nd

de

ve

lop

ed

a t

ech

niq

ue

to

,

an

d d

eve

lop

ed

a t

ech

niq

ue

to

exa

min

e t

he

e

xa

min

e t

he

““q

ua

ntu

mn

ess

qu

an

tum

ne

ss””

of

a d

evic

e.

of

a d

evic

e.

T

he

ap

plic

atio

n o

f o

ur

SD

P t

o q

ua

ntu

m c

locks

Th

e a

pp

lica

tio

n o

f o

ur

SD

P t

o q

ua

ntu

m c

locks

ind

ica

tes th

at

it lik

ely

ha

s m

an

y o

the

r a

pp

lica

tio

ns

ind

ica

tes th

at

it lik

ely

ha

s m

an

y o

the

r a

pp

lica

tio

ns

Refe

ren

ces

Refe

ren

ces

1.

1.

A.

A.

Am

bain

isA

mbain

is, , Q

uantu

m low

er

bounds b

y q

uantu

m a

rgum

ents

Quantu

m low

er

bounds b

y q

uantu

m a

rgum

ents

2.

2.

H. B

arn

um

, M

. S

aks, and M

. H

. B

arn

um

, M

. S

aks, and M

. S

zegedy

Szegedy, , Q

uantu

m q

uery

com

ple

xity

Quantu

m q

uery

com

ple

xity

and s

em

idefinite p

rogra

mm

ing

and s

em

idefinite p

rogra

mm

ing

3.

3.

H. B

arn

um

, H

. B

arn

um

, S

em

idefinite p

rogra

mm

ing c

hara

cte

rization a

nd s

pectr

al

Sem

idefinite p

rogra

mm

ing c

hara

cte

rization a

nd s

pectr

al

advers

ary

meth

od for

quantu

m c

om

ple

xity w

ith

advers

ary

meth

od for

quantu

m c

om

ple

xity w

ith n

oncom

muting

noncom

muting

unitary

queries

unitary

queries

4.

4.

V.

V.

Buzek

Buzek, R

. , R

. D

erk

aD

erk

a, and S

. , and S

. M

assar

Massar ,

, O

ptim

al quantu

m c

locks

Op

tim

al quantu

m c

locks

5.

5.

C.W

. C

hou, et. a

l.,

C.W

. C

hou, et. a

l.,

Fre

quency c

om

parison o

f tw

o h

igh

Fre

quency c

om

parison o

f tw

o h

igh

-- accura

cy A

laccura

cy A

l++

optical clo

cks

optical clo

cks

6.

6.

L.

L.

Hughsto

nH

ughsto

n, R

. , R

. Jozsa

Jozsa

, and W

. , and W

. W

oote

rsW

oote

rs, , A

com

ple

te c

lassific

ation o

f A

com

ple

te c

lassific

ation o

f quantu

m e

nsem

ble

s h

avin

g a

giv

en d

ensity m

atr

ixquantu

m e

nsem

ble

s h

avin

g a

giv

en d

ensity m

atr

ix

7.

7.

N.F

. R

am

sey,

N.F

. R

am

sey,

Mole

cula

r B

eam

sM

ole

cula

r B

eam

s

8.

8.

B.

B.

Reic

hard

tR

eic

hard

t , R

eflections for

quantu

m q

uery

com

ple

xity:

, R

eflections for

quantu

m q

uery

com

ple

xity:

The g

enera

l T

he g

enera

l advers

ary

bound is tig

ht fo

r every

advers

ary

bound is tig

ht fo

r every

boole

an

boole

an

function

function

9.

9.

P.O

. S

chm

idt, e

t. a

l.,

P.O

. S

chm

idt, e

t. a

l.,

Spectr

oscopy u

sin

g q

uantu

m logic

Spectr

oscopy u

sin

g q

uantu

m logic

10

.1

0.

B. S

chum

acher,

B

. S

chum

acher,

Quantu

m c

odin

gQ

uantu

m c

odin

g

11

.1

1.

W.

W.

Zure

kZ

ure

k, , D

ecohere

nce,

Decohere

nce,

ein

sele

ction

ein

sele

ction

and the q

uantu

m o

rigin

s o

f th

e

and the q

uantu

m o

rigin

s o

f th

e

cla

ssic

al

cla

ssic

al

Alg

ori

thm

Reco

nstr

ucti

on

Alg

ori

thm

Reco

nstr

ucti

on

•S

DP

outp

uts

a d

ensity m

atr

ix c

orr

espon

din

g t

o the s

tate

of

the c

om

pute

r at every

tim

este

p

•P

urify

the follo

win

g p

airs o

f sta

tes into

A, w

here

|A

| =

|O

||Q

|E|

•S

ince w

e k

no

w t

hat

we c

an s

olv

e f

or

the inte

r-query

un

itaries.

Sin

ce t

he S

DP

yie

lds t

he s

olu

tio

n w

ith

the o

ptim

al pro

ba

bili

ty o

f success, th

is

reconstr

ucts

an o

ptim

al a

lgorith

m. (q

uantu

m o

r cla

ssic

al)

D†QEtΩ†QOρOQE(t)Ω

QODQEt→ρ′OQEA(t)

ρOQE(t+1)→ρOQEA(t+1)

ρOQEA(t+1)=U(t)†QAρ′ OQEA(t)U(t)QA

Measu

rin

g Q

uan

tum

Reso

urc

es

Measu

rin

g Q

uan

tum

Reso

urc

es

O

ur

SD

P f

orm

ula

tio

n w

ill y

ield

th

e a

lgo

rith

m w

ith

O

ur

SD

P f

orm

ula

tio

n w

ill y

ield

th

e a

lgo

rith

m w

ith

the

op

tim

al p

rob

ab

ility

of succe

ss.

the

op

tim

al p

rob

ab

ility

of succe

ss.

B

ut

ca

n w

e f

ind

an

B

ut

ca

n w

e f

ind

an

““a

lte

rna

tea

lte

rna

te””

alg

ori

thm

with

th

e

alg

ori

thm

with

th

e

sa

me

pro

ba

bili

ty o

f su

cce

ss th

at

use

s fe

we

r sa

me

pro

ba

bili

ty o

f su

cce

ss th

at

use

s fe

we

r

qu

an

tum

re

so

urc

es?

qu

an

tum

re

so

urc

es?

Q

ua

ntify

qu

an

tum

re

so

urc

es v

ia V

on N

eu

ma

nn

Q

ua

ntify

qu

an

tum

re

so

urc

es v

ia V

on N

eu

ma

nn

en

tro

py

en

tro

py

B

y S

ch

um

ach

er

By S

ch

um

ach

er ’’

s q

ua

ntu

m c

od

ing

, w

e k

no

w t

his

s q

ua

ntu

m c

od

ing

, w

e k

no

w t

his

is t

he

min

imu

m n

um

be

r o

f q

ub

its n

ee

de

d t

o

is t

he

min

imu

m n

um

be

r o

f q

ub

its n

ee

de

d t

o

rep

rese

nt

a q

ua

ntu

m s

tate

re

pre

se

nt

a q

ua

ntu

m s

tate

[10]

[10]

S(ρ)≡tr(ρlg(ρ))

Sep

ara

te C

om

pu

tati

on

al P

ath

sS

ep

ara

te C

om

pu

tati

on

al P

ath

s

L

et

the

op

tim

al a

lgo

rith

m r

un

no

rma

lly u

ntil tim

e

Le

t th

e o

ptim

al a

lgo

rith

m r

un

no

rma

lly u

ntil tim

e

tt ss, th

en

me

asu

re, th

en

me

asu

re

Q

ua

ntify

th

e q

ua

ntu

m r

eso

urc

es n

ee

de

d t

o r

ea

ch

Q

ua

ntify

th

e q

ua

ntu

m r

eso

urc

es n

ee

de

d t

o r

ea

ch

tim

este

ptim

este

ptt ss

+ 1

+ 1

T

ry to e

xpre

ss a

s the inco

here

nt

sum

of

Try

to e

xpre

ss a

s the inco

here

nt

sum

of

T

hese ind

epen

de

nt

com

puta

tion

al path

s c

an b

e

These ind

epen

de

nt

com

puta

tion

al path

s c

an b

e

cla

ssic

ally

com

bin

ed.

cla

ssic

ally

com

bin

ed.

C

alc

ula

te e

ntr

opy a

s:

Ca

lcu

late

entr

opy a

s:

S

ince t

he full

de

nsity m

atr

ix is p

ure

:S

ince t

he full

de

nsity m

atr

ix is p

ure

:

ρO(ts)

ρO 1(ts),ρO 2(ts)...ρO n(ts)

ST=tr(ρO 1)S

(ρO 1

tr(ρO 1)

)+tr(ρO 2)S

(ρO 2

tr(ρO 2)

)+...

S(ρO)=S(ρQA)

Sp

litt

ing

SD

PS

plitt

ing

SD

P

A

dd t

he f

ollo

win

g c

onstr

ain

ts to a

ne

w S

DP

Add t

he f

ollo

win

g c

onstr

ain

ts to a

ne

w S

DP

A

dd a

n o

bje

ctive w

hic

h m

axim

ize

s the d

ista

nce b

etw

ee

n

Add a

n o

bje

ctive w

hic

h m

axim

ize

s the d

ista

nce b

etw

ee

n

the t

wo s

ubpart

s o

f th

e o

racle

de

nsity m

atr

ix.

the t

wo s

ubpart

s o

f th

e o

racle

de

nsity m

atr

ix.

T

his

will

be

a n

onlin

ea

r obje

ctive s

o w

e u

se a

n ite

rative

T

his

will

be

a n

onlin

ea

r obje

ctive s

o w

e u

se a

n ite

rative

str

ate

gy

str

ate

gy

with t

he u

sua

l sets

of constr

ain

ts o

n t

hese n

ew

de

nsity

with t

he u

sua

l sets

of constr

ain

ts o

n t

hese n

ew

de

nsity

matr

ices. H

ere

, th

e o

racle

de

nsity m

atr

ix is t

he o

ptim

al

matr

ices. H

ere

, th

e o

racle

de

nsity m

atr

ix is t

he o

ptim

al

solu

tio

n t

o o

ur

orig

ina

l S

DP

.solu

tio

n t

o o

ur

orig

ina

l S

DP

.

trQ(ρOQ

1(t))=ρO 1(t)

trQ(ρOQ

2(t))=ρO 2(t)

ρO opt(t)=ρO 1(t)+ρO 2(t)

t≥t s

Sp

litt

ing

Resu

lts

Sp

litt

ing

Resu

lts

R

ecu

rsiv

ely

pe

rfo

rm t

his

sp

littin

g,

ca

lcu

latin

g th

e

Re

cu

rsiv

ely

pe

rfo

rm t

his

sp

littin

g,

ca

lcu

latin

g th

e

en

tro

py a

t e

ach

ite

ratio

n.

en

tro

py a

t e

ach

ite

ratio

n.

P

ari

ty lo

oks c

lassic

al in

th

e

Pa

rity

lo

oks c

lassic

al in

th

e H

ad

am

ard

Ha

da

ma

rdb

asis

.

ba

sis

.

E

ntr

op

y is a

ba

sis

in

de

pe

nd

en

t q

ua

ntity

.E

ntr

op

y is a

ba

sis

in

de

pe

nd

en

t q

ua

ntity

.

8 E

lem

en

t S

earc

h/O

R:

0. 2

.056

2. 2

.0096

4. 2

.0093

8. 2

.0093

4 E

lem

en

t P

AR

ITY

0. 2

2. 1

4. 0

8. 0