Embed Size (px)
Citation preview
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
