"Non UBC"@en . "DSpace"@en . "University of British Columbia. Department of Physics and Astronomy"@en . "Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics"@en . "Pacific Institute for the Mathematical Sciences"@en . "Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.)"@en . "Mullan, Michael"@en . "2016-11-22T14:49:13"@en . "2010-07-25"@en . "The Quantum Adversary Method has proven to be a successful technique for deriving lower bounds on a wide variety of problems. However, it assumes perfect quantum computation, which in most modern devices, is unrealistic. Here, we develop a generalization of this technique without this assumption, which can be applied to arbitrary small problems automatically. To do this, we start by reformulating the objective value of the semidefinite program of the spectral adversary method. By relating the final measurement stage of a quantum computation to remote state preparation, we prove that the optimal value of the new objective corresponds to the probability that the quantum computer will output the correct value after a specified number of queries. Once in this framework, the addition of decoherence is natural. In particular, the optimum probability of success can be determined for any probability of phase error. In the limit of complete phase decoherence, we recover the optimal p! robability of success for a classical computation. Our semidefinite programming formulation is suitably general, and so has application outside that of algorithms. In particular, we apply it to the optimization of quantum clocks."@en . "https://circle.library.ubc.ca/rest/handle/2429/30937?expand=metadata"@en . "A S e m id e fi n it e P ro g ra m m in g A S e m id e fi n it e P ro g ra m m in g F o rm u la ti o n o f Q u a n tu m a n d F o rm u la ti o n o f Q u a n tu m a n d C la s s ic a l O ra c le P ro b le m s C la s s ic a l O ra c le P ro b le m s M ik e M u lla n a n d E m a n u e l M ik e M u lla n a n d E m a n u e l K n ill K n ill U n iv e rs it y o f C o lo ra d o a t B o u ld e r a n d t h e U n iv e rs it y o f C o lo ra d o a t B o u ld e r a n d t h e N a ti o n a l In s ti tu te o f S ta n d a rd s a n d T e c h n o lo g y N a ti o n a l In s ti tu te o f S ta n d a rd s a n d T e c h n o lo g y O u tl in e O u tl in e 1 . 1 . S e m id e fi n it e P ro g ra m m in g F o rm u la ti o n o f Q u a n tu m S e m id e fi n it e P ro g ra m m in g F o rm u la ti o n o f Q u a n tu m C o m p u ta ti o n C o m p u ta ti o n [ 2 ,3 ] [2 ,3 ] \u00E2\u0080\u00A2\u00E2\u0080\u00A2 C a n c a lc u la te C a n c a lc u la te e x a c t e x a c t e rr o r p ro b a b ili ti e s f o r a q u a n tu m e rr o r p ro b a b ili ti e s f o r a q u a n tu m c o m p u te r o p ti m a lly s o lv in g a rb it ra ry q u a n tu m o ra c le c o m p u te r o p ti m a lly s o lv in g a rb it ra ry q u a n tu m o ra c le p ro b le m s p ro b le m s 2 . 2 . R e m o te S ta te P re p a ra ti o n , a n d a G e n e ra liz e d R e m o te S ta te P re p a ra ti o n , a n d a G e n e ra liz e d O b je c ti v e O b je c ti v e 3 . 3 . R e s tr ic te d C o m p u ta ti o n R e s tr ic te d C o m p u ta ti o n \u00E2\u0080\u00A2\u00E2\u0080\u00A2 D e c o h e re n c e a n d a n a ly z in g a c o m p u ta ti o n s u b je c t to D e c o h e re n c e a n d a n a ly z in g a c o m p u ta ti o n s u b je c t to n o is e n o is e \u00E2\u0080\u00A2\u00E2\u0080\u00A2 O p ti m a l a lg o ri th m s u s in g r e d u c e d q u a n tu m r e s o u rc e s O p ti m a l a lg o ri th m s u s in g r e d u c e d q u a n tu m r e s o u rc e s (b ri e fl y ) (b ri e fl y ) 4 . 4 . Q u a n tu m C lo c k s Q u a n tu m C lo c k s Q u a n tu m A lg o ri th m s , G e n e ri c a ll y Q u a n tu m A lg o ri th m s , G e n e ri c a ll y Q u a n tu m Q u e ry A lg o ri th m : A rb it ra ry u n it a ry o p e ra to rs in te rs p e rs e d w it h o ra c le o p e ra to rs a c ti n g o n s o m e i n it ia l s ta te , fo llo w e d b y a m e a s u re m e n t S e m id e fi n it e P ro g ra m m in g : L in e a r p ro g ra m m in g w it h s e m id e fi n it e c o n s tr a in ts | \u00CF\u0088 (t )\u00E3\u0080\u0089 = U t \u00E2\u0084\u00A6 U t\u00E2\u0088\u0092 1 \u00E2\u0084\u00A6 .. .\u00E2\u0084\u00A6 U 0 | \u00CF\u0088 (0 )\u00E3\u0080\u0089 G o a l: M in im iz e t h e n u m b e r o f q u e ri e s o f a q u a n tu m q u e ry a lg o ri th m v ia a g e n e ra liz a ti o n o f A m b a in is \u00E2\u0080\u0099 a d v e rs a ry m e th o d [1 ] (a n d r e c e n t p ro g re s s g iv e n i n [ 8 ]) T ry t o e x p re s s a q u a n tu m q u e ry a lg o ri th m a s a s e m id e fi n it e p ro g ra m ( S D P ) : G ro v e r G ro v e r \u00E2\u0080\u0099\u00E2\u0080\u0099 s A lg o ri th m s A lg o ri th m 00 00 11 00 U = I n v e rs io n a b o u t th e M e a n 1 . 2 . 3 . 4 . 5 .|\u00CF\u0088 (0 )\u00E3\u0080\u0089 = |0\u00E3\u0080\u0089 U 0 |\u00CF\u0088 (0 )\u00E3\u0080\u0089 = 1 2 (|0 \u00E3\u0080\u0089+ |1\u00E3\u0080\u0089 + |2\u00E3\u0080\u0089 + |3\u00E3\u0080\u0089 ) U 1 \u00E2\u0084\u00A6 U 0 |\u00CF\u0088 (0 )\u00E3\u0080\u0089 = |1\u00E3\u0080\u0089 \u00E2\u0084\u00A6 3 \u00E2\u0084\u00A6 0 \u00E2\u0084\u00A6 1 \u00E2\u0084\u00A6 2 \u00E2\u0084\u00A6 U 0 |\u00CF\u0088 (0 ) \u00E3\u0080\u0089 = 1 2 ( |0 \u00E3\u0080\u0089\u00E2\u0088\u0092 |1 \u00E3\u0080\u0089 + |2 \u00E3\u0080\u0089 + |3 \u00E3\u0080\u0089 ) \u00E2\u0084\u00A6 U 0 |\u00CF\u0088 (0 ) \u00E3\u0080\u0089 = 1 2 ( ( \u00E2\u0088\u00921 )\u00E2\u0084\u00A6 0 |0 \u00E3\u0080\u0089 + ( \u00E2\u0088\u0092 1 )\u00E2\u0084\u00A6 1 |1 \u00E3\u0080\u0089 + ( \u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 2 |2 \u00E3\u0080\u0089 + ( \u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 3 |3 \u00E3\u0080\u0089 ) a i \u00E2\u0086\u0092 \u00E2\u0088\u0092 a i + 2 \u00E2\u0088\u0097\u00E3\u0080\u0088 a \u00E3\u0080\u0089 G o a l: S e a rc h \u00E2\u0080\u0093 F in d t h e m a rk e d e le m e n t \u00E2\u0084\u00A6 |\u00CF\u0088 (t )\u00E3\u0080\u0089 = \u00E2\u0088\u0091 ia i\u00E2\u0084\u00A6 |i\u00E3\u0080\u0089 \u00E2\u0086\u0092 \u00E2\u0088\u0091 ia i( \u00E2\u0088\u00921 )\u00E2\u0084\u00A6 i |i\u00E3\u0080\u0089 O th e r O ra c le s A re P o s s ib le O th e r O ra c le s A re P o s s ib le 00 00 00 11 00 00 11 00 W e c a n a ls o h a v e : 11 00 00 00 00 11 00 00 A s s u m e e a c h o ra c le c a n b e g iv e n t o o u r c o m p u te r w it h s o m e p ro b a b ili ty N e w G o a l: F in d t h e m a rk e d e le m e n t \u00E2\u0086\u0092 Id e n ti fy t h e a p p lie d o ra c le \u00E2\u0084\u00A6 (0 ) \u00E2\u0084\u00A6 (1 ) \u00E2\u0084\u00A6 (2 ) \u00E2\u0084\u00A6 (3 ) \u00CF\u0081 O = \u00E2\u0088\u0091 x,y\u00E2\u0088\u009A p x \u00E2\u0088\u009A p y |x\u00E3\u0080\u0089 \u00E3\u0080\u0088y | Q : Q u e ri e r s y s te m \u00CF\u0081 Q = \u00E2\u0088\u0091 i,ja i, j |i\u00E3\u0080\u0089 \u00E3\u0080\u0088j| O : O ra c le s y s te m P u re s ta te o v e r p o s s ib le o ra c le s T h e C o m p u te r T h e C o m p u te r A : A n c ill a \u00CF\u0081 O = \u00E2\u0088\u0091 x,y\u00E2\u0088\u009A p x \u00E2\u0088\u009A p y |x\u00E3\u0080\u0089 \u00E3\u0080\u0088y | Q : Q u e ri e r s y s te m \u00CF\u0081 Q = \u00E2\u0088\u0091 i,ja i, j |i\u00E3\u0080\u0089 \u00E3\u0080\u0088j| O : O ra c le s y s te m \u00E2\u0084\u00A6 O Q = \u00E2\u0088\u0091 x| x \u00E3\u0080\u0089\u00E3\u0080\u0088x |\u00E2\u0084\u00A6 Q (x ) P u re s ta te o v e r p o s s ib le o ra c le s T h e C o m p u te r T h e C o m p u te r A : A n c ill a \u00CF\u0081 O = \u00E2\u0088\u0091 x,y\u00E2\u0088\u009A p x \u00E2\u0088\u009A p y |x\u00E3\u0080\u0089 \u00E3\u0080\u0088y | Q : Q u e ri e r s y s te m \u00CF\u0081 Q = \u00E2\u0088\u0091 i,ja i, j |i\u00E3\u0080\u0089 \u00E3\u0080\u0088j| O : O ra c le s y s te m \u00E2\u0084\u00A6 O Q = \u00E2\u0088\u0091 x| x \u00E3\u0080\u0089\u00E3\u0080\u0088x |\u00E2\u0084\u00A6 Q (x ) P u re s ta te o v e r p o s s ib le o ra c le s T h e C o m p u te r T h e C o m p u te r A : A n c ill a \u00E2\u0084\u00A6 O Q (|x \u00E3\u0080\u0089O \u00E2\u008A\u0097 |\u00CF\u0088 \u00E3\u0080\u0089Q ) \u00E2\u0086\u0092 (|x \u00E3\u0080\u0089O \u00E2\u008A\u0097 \u00E2\u0084\u00A6 Q (x )|\u00CF\u0088 \u00E3\u0080\u0089Q ) T h e I n it ia l J o in t D e n s it y M a tr ix T h e I n it ia l J o in t D e n s it y M a tr ix \u00CF\u0081 O Q (0 ) = \u00E2\u0088\u0091 x,y\u00E2\u0088\u0091 i, j \u00E2\u0088\u009A p x \u00E2\u0088\u009A p y |x\u00E3\u0080\u0089 \u00E3\u0080\u0088y |\u00E2\u008A\u0097 a i, j |i\u00E3\u0080\u0089 \u00E3\u0080\u0088j | \u00CF\u0081 O Q (0 ) = \u00EF\u00A3\u00AB \u00EF\u00A3\u00AC \u00EF\u00A3\u00AC \u00EF\u00A3\u00AC \u00EF\u00A3\u00AC \u00EF\u00A3\u00AD\u00E2\u0088\u009A p 0 \u00E2\u0088\u009A p 0 ( a 0 ,0 a 0 ,1 a 1 ,0 . . . ) \u00E2\u0088\u009A p 0 \u00E2\u0088\u009A p 1 ( a 0 ,0 a 0 ,1 a 1 ,0 . . . ) \u00E2\u0088\u009A p 1 \u00E2\u0088\u009A p 0 ( a 0 ,0 a 0 ,1 a 1 ,0 . . . ) . . . \u00EF\u00A3\u00B6 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B8 \u00CF\u0081 Q (0 ) T h e I n it ia l J o in t D e n s it y M a tr ix T h e I n it ia l J o in t D e n s it y M a tr ix \u00CF\u0081 O Q = \u00EF\u00A3\u00AB \u00EF\u00A3\u00AC \u00EF\u00A3\u00AC \u00EF\u00A3\u00AC \u00EF\u00A3\u00AC \u00EF\u00A3\u00AD\u00E2\u0088\u009A p 0 \u00E2\u0088\u009A p 0 \u00E2\u0084\u00A6 (0 )\u00E2\u0080\u00A0 ( a 0 ,0 a 0 ,1 a 1 ,0 . . . ) \u00E2\u0084\u00A6( 0) \u00E2\u0088\u009A p 0 \u00E2\u0088\u009A p 1 \u00E2\u0084\u00A6 (0 )\u00E2\u0080\u00A0 ( a 0 ,0 a 0 ,1 a 1 ,0 . . . ) \u00E2\u0084\u00A6( 1) \u00E2\u0088\u009A p 1 \u00E2\u0088\u009A p 0 \u00E2\u0084\u00A6 (1 )\u00E2\u0080\u00A0 ( a 0 ,0 a 0 ,1 a 1 ,0 . . . ) \u00E2\u0084\u00A6( 0) \u00E2\u0080\u00A0 . . . \u00EF\u00A3\u00B6 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B8 \u00CF\u0081 O Q (0 ) = \u00E2\u0088\u0091 x,y\u00E2\u0088\u0091 i, j \u00E2\u0088\u009A p x \u00E2\u0088\u009A p y |x\u00E3\u0080\u0089 \u00E3\u0080\u0088y |\u00E2\u008A\u0097 a i, j |i\u00E3\u0080\u0089 \u00E3\u0080\u0088j | \u00CF\u0081 O Q (0 ) = \u00EF\u00A3\u00AB \u00EF\u00A3\u00AC \u00EF\u00A3\u00AC \u00EF\u00A3\u00AC \u00EF\u00A3\u00AC \u00EF\u00A3\u00AD\u00E2\u0088\u009A p 0 \u00E2\u0088\u009A p 0 ( a 0 ,0 a 0 ,1 a 1 ,0 . . . ) \u00E2\u0088\u009A p 0 \u00E2\u0088\u009A p 1 ( a 0 ,0 a 0 ,1 a 1 ,0 . . . ) \u00E2\u0088\u009A p 1 \u00E2\u0088\u009A p 0 ( a 0 ,0 a 0 ,1 a 1 ,0 . . . ) . . . \u00EF\u00A3\u00B6 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B7 \u00EF\u00A3\u00B8 \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 \u00CF\u0081 O Q (0 )\u00E2\u0084\u00A6 \u00E2\u0086\u0092 \u00E2\u0088\u0091 x,y\u00E2\u0088\u0091 i, j \u00E2\u0088\u009A p x \u00E2\u0088\u009A p y | x\u00E3\u0080\u0089 \u00E3\u0080\u0088 y |\u00E2\u008A\u0097 \u00E2\u0084\u00A6 (x )\u00E2\u0080\u00A0 a i, j | i\u00E3\u0080\u0089 \u00E3\u0080\u0088 j | \u00E2\u0084\u00A6 (y ) \u00CF\u0081 Q (0 ) Q u a n tu m A lg o ri th m Q u a n tu m A lg o ri th m \u00E2\u0086\u0092\u00E2\u0086\u0092 S D P ( 1 ) S D P ( 1 ) \u00CF\u0081 O Q N e e d b o th a n o b je c ti v e a n d a s e t o f lin e a r c o n s tr a in ts o v e r (S tr a ig h tf o rw a rd ) C o n s tr a in ts \u00CF\u0081 O Q (t ) \u00E2\u0089\u00A5 0, \u00CF\u0081 O (t ) \u00E2\u0089\u00A5 0 \u00CF\u0081 O (t ) = tr Q (\u00CF\u0081 O Q (t )) \u00CF\u0081 O (0 ) = \u00CF\u0081 0 t \u00E2\u0088\u0088 {0 .. .t f } Q u a n tu m A lg o ri th m Q u a n tu m A lg o ri th m \u00E2\u0086\u0092\u00E2\u0086\u0092 S D P ( 2 ) S D P ( 2 ) |\u00CF\u0088 (t )\u00E3\u0080\u0089 = U t\u00E2\u0084\u00A6 U t\u00E2\u0088\u0092 1 \u00E2\u0084\u00A6 .. .\u00E2\u0084\u00A6 U 0 |\u00CF\u0088 (0 )\u00E3\u0080\u0089 \u00CF\u0081 O (t ) = tr Q A (U \u00E2\u0080\u00A0 Q A t \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q A (t \u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 O Q U Q A t ) Q u a n tu m A lg o ri th m Q u a n tu m A lg o ri th m \u00E2\u0086\u0092\u00E2\u0086\u0092 S D P ( 2 ) S D P ( 2 ) |\u00CF\u0088 (t )\u00E3\u0080\u0089 = U t\u00E2\u0084\u00A6 U t\u00E2\u0088\u0092 1 \u00E2\u0084\u00A6 .. .\u00E2\u0084\u00A6 U 0 |\u00CF\u0088 (0 )\u00E3\u0080\u0089 \u00CF\u0081 O (t ) = tr Q A (U Q A t U \u00E2\u0080\u00A0 Q A t \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q A (t \u00E2\u0088\u0092 1 )\u00E2\u0084\u00A6 O Q ) \u00CF\u0081 O (t ) = tr Q A (U \u00E2\u0080\u00A0 Q A t \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q A (t \u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 O Q U Q A t ) Q u a n tu m A lg o ri th m Q u a n tu m A lg o ri th m \u00E2\u0086\u0092\u00E2\u0086\u0092 S D P ( 2 ) S D P ( 2 ) |\u00CF\u0088 (t )\u00E3\u0080\u0089 = U t\u00E2\u0084\u00A6 U t\u00E2\u0088\u0092 1 \u00E2\u0084\u00A6 .. .\u00E2\u0084\u00A6 U 0 |\u00CF\u0088 (0 )\u00E3\u0080\u0089 \u00CF\u0081 O (t ) = tr Q (\u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q (t \u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 O Q ) \u00CF\u0081 O (t ) = tr Q A (U Q A t U \u00E2\u0080\u00A0 Q A t \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q A (t \u00E2\u0088\u0092 1 )\u00E2\u0084\u00A6 O Q ) \u00CF\u0081 O (t ) = tr Q A (U \u00E2\u0080\u00A0 Q A t \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q A (t \u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 O Q U Q A t ) Q u a n tu m A lg o ri th m Q u a n tu m A lg o ri th m \u00E2\u0086\u0092\u00E2\u0086\u0092 S D P ( 2 ) S D P ( 2 ) L e a d s t o t h e S D P S E , c o rr e s p o n d in g to t h e a p p lic a ti o n o f o ra c le a n d u n it a ry o p e ra to rs a s a b o v e |\u00CF\u0088 (t )\u00E3\u0080\u0089 = U t\u00E2\u0084\u00A6 U t\u00E2\u0088\u0092 1 \u00E2\u0084\u00A6 .. .\u00E2\u0084\u00A6 U 0 |\u00CF\u0088 (0 )\u00E3\u0080\u0089 S E = \u00EF\u00A3\u00B1 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B2 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B3\u00CF\u0081O Q (t ) \u00E2\u0089\u00A5 0 , \u00CF\u0081 O (t ) \u00E2\u0089\u00A5 0 \u00CF\u0081 O (t ) = tr Q (\u00CF\u0081 O Q (t )) \u00CF\u0081 O (t ) = tr Q (\u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q (t \u00E2\u0088\u0092 1 )\u00E2\u0084\u00A6 O Q ) \u00CF\u0081 O (0 ) = \u00CF\u0081 0 t \u00E2\u0088\u0088 {0 .. .t f } \u00CF\u0081 O (t ) = tr Q (\u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q (t \u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 O Q ) \u00CF\u0081 O (t ) = tr Q A (U Q A t U \u00E2\u0080\u00A0 Q A t \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q A (t \u00E2\u0088\u0092 1 )\u00E2\u0084\u00A6 O Q ) \u00CF\u0081 O (t ) = tr Q A (U \u00E2\u0080\u00A0 Q A t \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q A (t \u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 O Q U Q A t ) M e a s u re m e n t a n d R e m o te S ta te P re p a ra ti o n M e a s u re m e n t a n d R e m o te S ta te P re p a ra ti o n T h e f o llo w in g p ro to c o l d e s c ri b e s t h e m e a s u re m e n t p ro c e s s a t th e e n d o f th e c o m p u ta ti o n a t ti m e t f. [6 ] 1 . Q m a k e s a m e a s u re m e n t w it h a n y c o m p le te P O V M {P Q A i } i M e a s u re m e n t a n d R e m o te S ta te P re p a ra ti o n M e a s u re m e n t a n d R e m o te S ta te P re p a ra ti o n T h e f o llo w in g p ro to c o l d e s c ri b e s t h e m e a s u re m e n t p ro c e s s a t th e e n d o f th e c o m p u ta ti o n a t ti m e t f. [6 ] 1 . Q m a k e s a m e a s u re m e n t w it h a n y c o m p le te P O V M 2 . C o n d it io n a l o n m e a s u re m e n t o u tc o m e i , th e o ra c le s y s te m s ta te i s ( u p t o n o rm a liz a ti o n ) {P Q A i } i \u00CF\u0083 i = tr Q A (P Q A i \u00CF\u0081 O Q A (t f )) M e a s u re m e n t a n d R e m o te S ta te P re p a ra ti o n M e a s u re m e n t a n d R e m o te S ta te P re p a ra ti o n T h e f o llo w in g p ro to c o l d e s c ri b e s t h e m e a s u re m e n t p ro c e s s a t th e e n d o f th e c o m p u ta ti o n a t ti m e t f. [6 ] 1 . Q m a k e s a m e a s u re m e n t w it h a n y c o m p le te P O V M 2 . C o n d it io n a l o n m e a s u re m e n t o u tc o m e i , th e o ra c le s y s te m s ta te i s ( u p t o n o rm a liz a ti o n ) 3 . W e m e a s u re a c o s t fu n c ti o n A i o n t h is r e m o te ly p re p a re d s ta te , w h ic h i n d ic a te s h o w s u c c e s s fu l o u r a lg o ri th m w a s {P Q A i } i \u00CF\u0083 i = tr Q A (P Q A i \u00CF\u0081 O Q A (t f )) M e a s u re m e n t a n d R e m o te S ta te P re p a ra ti o n M e a s u re m e n t a n d R e m o te S ta te P re p a ra ti o n T h e f o llo w in g p ro to c o l d e s c ri b e s t h e m e a s u re m e n t p ro c e s s a t th e e n d o f th e c o m p u ta ti o n a t ti m e t f. [6 ] 1 . Q m a k e s a m e a s u re m e n t w it h a n y c o m p le te P O V M 2 . C o n d it io n a l o n m e a s u re m e n t o u tc o m e i , th e o ra c le s y s te m s ta te i s ( u p t o n o rm a liz a ti o n ) 3 . W e m e a s u re a c o s t fu n c ti o n A i o n t h is r e m o te ly p re p a re d s ta te , w h ic h i n d ic a te s h o w s u c c e s s fu l o u r a lg o ri th m w a s Q \u00E2\u0080\u0099s P O V M i s u n c o n s tr a in e d , b u t th e s e t o f s ta te s t h a t c a n b e p re p a re d o n O i s r e s tr ic te d b y : {P Q A i } i \u00CF\u0083 i = tr Q A (P Q A i \u00CF\u0081 O Q A (t f )) \u00E2\u0088\u0091 i\u00CF\u0083 O i = \u00CF\u0081 O (t f ) T h e C o m p le te S D P T h e C o m p le te S D P S = S M \u00E2\u0088\u00AA S E S E = \u00EF\u00A3\u00B1 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B2 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B3\u00CF\u0081O Q (t ) \u00E2\u0089\u00A5 0 , \u00CF\u0081 O (t ) \u00E2\u0089\u00A5 0 \u00CF\u0081 O (t ) = tr Q (\u00CF\u0081 O Q (t )) \u00CF\u0081 O (t ) = tr Q (\u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q (t \u00E2\u0088\u0092 1 )\u00E2\u0084\u00A6 O Q ) \u00CF\u0081 O (0 ) = \u00CF\u0081 0 t \u00E2\u0088\u0088 {0 .. .t f } S M = \u00EF\u00A3\u00B1 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B2 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B4 \u00EF\u00A3\u00B3M in im iz e \u00E2\u0088\u0091 it r (\u00CF\u0083 iA i) s u bj e ct to : \u00E2\u0088\u0080 i \u00CF\u0083 i \u00E2\u0089\u00A5 0 \u00E2\u0088\u0091 i\u00CF\u0083 O i = \u00CF\u0081 O (t f ) C o n v e n ti o n a l C o s t F u n c ti o n C o n v e n ti o n a l C o s t F u n c ti o n \u0001\u0001 E a c h m e a s u re m e n t o u tc o m e E a c h m e a s u re m e n t o u tc o m e ii c o rr e s p o n d s t o t h e c o rr e s p o n d s t o t h e q u e ri e r q u e ri e r \u00E2\u0080\u0099\u00E2\u0080\u0099 ss g u e s s o f w h ic h o ra c le w a s a p p lie d g u e s s o f w h ic h o ra c le w a s a p p lie d \u0001\u0001 S e a rc h : S e a rc h : i = 2 i = 2 \u00E2\u0080\u0093\u00E2\u0080\u0093 T h e m a rk e d e le m e n t is i n p o s it io n T h e m a rk e d e le m e n t is i n p o s it io n 22 \u0001\u0001 A v e ra g e P ro b a b ili ty o f E rr o r: P ro b a b ili ty t h a t y o u h a d A v e ra g e P ro b a b ili ty o f E rr o r: P ro b a b ili ty t h a t y o u h a d o ra c le o ra c le xx , m e a s u re d o u tc o m e , m e a s u re d o u tc o m e ii , a n d t h a t y o u s h o u ld n , a n d t h a t y o u s h o u ld n \u00E2\u0080\u0099\u00E2\u0080\u0099 t t m e a s u re o u tc o m e m e a s u re o u tc o m e ii o n o ra c le o n o ra c le xx \u0001\u0001 S e a rc h : S e a rc h : x = 1 0 0 0 , i = 2 x = 1 0 0 0 , i = 2 \u0001\u0001 T h is e rr o r p ro b a b ili ty w ill b e T h is e rr o r p ro b a b ili ty w ill b e e x a c t e x a c t . Q i s f re e t o c h o o s e . Q i s f re e t o c h o o s e th e P O V M w h ic h o p ti m iz e s t h e c o s t fu n c ti o n , a n d t h e th e P O V M w h ic h o p ti m iz e s t h e c o s t fu n c ti o n , a n d t h e S D P w ill f in d t h is o p ti m u m s u b je c t to i ts c o n s tr a in ts . S D P w ill f in d t h is o p ti m u m s u b je c t to i ts c o n s tr a in ts . (\u00CF\u0083 i) x ,x = P (m e a s u r e d i \u00E2\u0088\u00A9 o r a cl e = x ) \u00C7\u00AB = \u00E2\u0088\u0091 i\u00E2\u0088\u0091 x :x \u0003 = i( \u00CF\u0083 i) x ,x \u00E3\u0080\u0088x |A i|x \u00E3\u0080\u0089= 1 \u00E2\u0088\u0092 \u00CE\u00B4 (i ,x ) R e s tr ic te d C o m p u ta ti o n R e s tr ic te d C o m p u ta ti o n \u0001\u0001 A ll e x p e ri m e n ta lly a v a ila b le q u a n tu m A ll e x p e ri m e n ta lly a v a ila b le q u a n tu m c o m p u te rs a re s u b je c t to n o is e c o m p u te rs a re s u b je c t to n o is e \u0001\u0001 D e c o h e re n c e c a n r e d u c e o r e lim in a te a n y D e c o h e re n c e c a n r e d u c e o r e lim in a te a n y q u a n tu m a d v a n ta g e . q u a n tu m a d v a n ta g e . \u0001\u0001 A ll c u rr e n t, g e n e ra l q u a n tu m l o w e r b o u n d A ll c u rr e n t, g e n e ra l q u a n tu m l o w e r b o u n d m e th o d s a s s u m e p e rf e c t q u a n tu m m e th o d s a s s u m e p e rf e c t q u a n tu m c o m p u ta ti o n . c o m p u ta ti o n . \u0001\u0001 W e w o u ld l ik e a w a y t o c h a ra c te ri z e h o w W e w o u ld l ik e a w a y t o c h a ra c te ri z e h o w \u00E2\u0080\u009C\u00E2\u0080\u009C q u a n tu m q u a n tu m \u00E2\u0080\u009D\u00E2\u0080\u009D o u r d e v ic e i s o u r d e v ic e i s D e c o h e re n c e D e c o h e re n c e A ft e r e a c h q u e ry , th e e n v ir o n m e n t w ill i n te ra c t w it h th e c o m p u te r a n d w ill d e c o h e re th e q u e ri e r [1 1 ] P o s t U n it a ry , P re -Q u e ry |\u00CF\u0088 (0 )\u00E3\u0080\u0089O Q E = \u00E2\u0088\u0091 x,ia x x ,i |x \u00E3\u0080\u0089O |i\u00E3\u0080\u0089 Q |\u00C7\u00AB 0 \u00E3\u0080\u0089E 1 D e c o h e re n c e D e c o h e re n c e A ft e r e a c h q u e ry , th e e n v ir o n m e n t w ill i n te ra c t w it h th e c o m p u te r a n d w ill d e c o h e re th e q u e ri e r [1 1 ] P o s t U n it a ry , P re -Q u e ry P o s t Q u e ry T h e s iz e o f th e e n v ir o n m e n t g ro w s w it h e v e ry q u e ry , s o a t ti m e t : |\u00CF\u0088 (0 )\u00E3\u0080\u0089O Q E = \u00E2\u0088\u0091 x,ia x x ,i |x \u00E3\u0080\u0089O |i\u00E3\u0080\u0089 Q |\u00C7\u00AB 0 \u00E3\u0080\u0089E 1 |\u00CF\u0088 (1 )\u00E3\u0080\u0089O Q E = \u00E2\u0088\u0091 x,ia x i, a |x\u00E3\u0080\u0089 O (\u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 (x ) i |i\u00E3\u0080\u0089 Q |\u00C7\u00AB i \u00E3\u0080\u0089E 1 |\u00C7\u00AB 0 \u00E3\u0080\u0089E 2 E (t ) \u00E2\u0089\u00A1 E = E 1 \u00E2\u008A\u0097 E 2 .. . \u00E2\u008A\u0097 E t A d d in g t h e E n v ir o n m e n t A d d in g t h e E n v ir o n m e n t Q : Q u e ri e r s y s te m A : A n c ill a O : O ra c le S y s te m E 1 E t 2 E : T h e e n v ir o n m e n t is p a rt o f th e o ra c le s y s te m t h a t th e q u e ri e r h a s n o a c c e s s t o , b u t a c ts o n t h e q u e ri e r d u ri n g e a c h q u e ry . T h e E x te n d e d S D P T h e E x te n d e d S D P M in im iz e tr (\u00E2\u0088\u0091 i \u00CF\u0083 iA i) su b je ct to : \u00E2\u0088\u0080 i \u00CF\u0083 O E i \u00E2\u0089\u00A5 0 \u00CF\u0081 O Q E (t ) \u00E2\u0089\u00A5 0 , \u00CF\u0081 O E (t ) \u00E2\u0089\u00A5 0 \u00E2\u0088\u0091 i\u00CF\u0083 O E i = \u00CF\u0081 O E (T ) \u00CF\u0081 O E (t ) = tr Q (\u00CF\u0081 O Q E (t )) \u00CF\u0081 O E (t ) = tr Q (D \u00E2\u0080\u00A0 Q E t \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 O Q \u00CF\u0081 O Q E (t \u00E2\u0088\u0092 1 ) \u00E2\u008A\u0097 |\u00C7\u00AB 0 \u00E3\u0080\u0089E t E t \u00E3\u0080\u0088\u00C7\u00AB 0 |\u00E2\u0084\u00A6 O Q D Q E t ) \u00CF\u0081 O E (0 ) = \u00CF\u0081 0 t \u00E2\u0088\u0088 {0 .. .t f } Q u a n tu m /C la s s ic a l In te rp o la ti o n Q u a n tu m /C la s s ic a l In te rp o la ti o n O n e o r m o re q u b it s m a y d e c o h e re in d e p e n d e n tl y w it h p ro b a b ili ty p R e d : O n e q u b it d e c o h e re n c e G re e n : T w o q u b it d e c o h e re n c e |x\u00E3\u0080\u0089 O |i\u00E3\u0080\u0089 Q |\u00C7\u00AB 0 \u00E3\u0080\u0089E \u00E2\u0086\u0092 \u00E2\u0088\u009A 1\u00E2\u0088\u0092 p |x\u00E3\u0080\u0089 O (\u00E2\u0088\u0092 1 )\u00E2\u0084\u00A6 (x ) i |i\u00E3\u0080\u0089 Q |\u00C7\u00AB 0 \u00E3\u0080\u0089E + \u00E2\u0088\u009A p |x\u00E3\u0080\u0089 O (\u00E2\u0088\u0092 1) \u00E2\u0084\u00A6 (x ) i |i\u00E3\u0080\u0089 Q |\u00C7\u00AB( i) \u00E3\u0080\u0089E C o m m e n ts C o m m e n ts \u0001\u0001 T h e s iz e o f th e S D P g ro w s r a p id ly , p a rt ic u la rl y w h e n T h e s iz e o f th e S D P g ro w s r a p id ly , p a rt ic u la rl y w h e n m o d e lin g m o d e lin g d e c o h e re n c e d e c o h e re n c e . ( < 1 0 q u b it s ) . ( < 1 0 q u b it s ) \u0001\u0001 S in c e t h e S D P o u tp u ts t h e o p ti m a l d e n s it y m a tr ix a t S in c e t h e S D P o u tp u ts t h e o p ti m a l d e n s it y m a tr ix a t e v e ry t im e s te p , w e c a n r e c o n s tr u c t th e i n te r e v e ry t im e s te p , w e c a n r e c o n s tr u c t th e i n te r -- q u e ry q u e ry u n it a ri e s u n it a ri e s , a n d h e n c e t h e o p ti m a l a lg o ri th m , a n d h e n c e t h e o p ti m a l a lg o ri th m \u0001\u0001 W e h a v e r e c e n tl y e x p lo re d t h e s e i s s u e s f ro m a n W e h a v e r e c e n tl y e x p lo re d t h e s e i s s u e s f ro m a n a lt e rn a te a n g le b y a s k in g : a lt e rn a te a n g le b y a s k in g : Is t h e re a n e q u a lly o p ti m a l Is t h e re a n e q u a lly o p ti m a l a lg o ri th m t h a t u s e s f e w e r q u a n tu m r e s o u rc e s ? a lg o ri th m t h a t u s e s f e w e r q u a n tu m r e s o u rc e s ? \u0001\u0001 U s e a n a lt e rn a te S D P w h ic h t ri e s t o s p lit t h e o p ti m a l a lg o ri th m U s e a n a lt e rn a te S D P w h ic h t ri e s t o s p lit t h e o p ti m a l a lg o ri th m in to t w o o r m o re p a rt s t h a t c a n b e c la s s ic a lly c o m b in e d in to t w o o r m o re p a rt s t h a t c a n b e c la s s ic a lly c o m b in e d \u0001\u0001 U s e t h e V o n N e u m a n n e n tr o p y t o q u a n ti fy t h e q u a n tu m U s e t h e V o n N e u m a n n e n tr o p y t o q u a n ti fy t h e q u a n tu m re s o u rc e s n e e d e d i n e a c h b ra n c h re s o u rc e s n e e d e d i n e a c h b ra n c h \u0001\u0001 S e e s lid e s a t e n d o f ta lk f o r d e ta ils S e e s lid e s a t e n d o f ta lk f o r d e ta ils C lo c k s C lo c k s \u0001\u0001 O u r S D P f o rm u la ti o n i s h ig h ly g e n e ra l, a n d c a n O u r S D P f o rm u la ti o n i s h ig h ly g e n e ra l, a n d c a n d e s c ri b e q u a n tu m d e s c ri b e q u a n tu m p ro c e s s e s p ro c e s s e s a s w e ll a s q u a n tu m a s w e ll a s q u a n tu m q u e ry a lg o ri th m s q u e ry a lg o ri th m s \u0001\u0001 S p e c if ic a lly , if a n e le m e n t d ra w n f ro m a c o n ti n u o u s S p e c if ic a lly , if a n e le m e n t d ra w n f ro m a c o n ti n u o u s s e t o f u n it a ry o p e ra to rs , in d e x e d b y s o m e s e t o f u n it a ry o p e ra to rs , in d e x e d b y s o m e p a ra m e te r, a c ts o n a s ta te , o u r fo rm u la ti o n c a n b e p a ra m e te r, a c ts o n a s ta te , o u r fo rm u la ti o n c a n b e u s e d t o o p ti m a lly e s ti m a te t h e v a lu e o f th is u s e d t o o p ti m a lly e s ti m a te t h e v a lu e o f th is p a ra m e te r p a ra m e te r \u0001\u0001 W e w ill u s e t h is i d e a t o o p ti m iz e t h e a c c u ra c y o f W e w ill u s e t h is i d e a t o o p ti m iz e t h e a c c u ra c y o f q u a n tu m c lo c k s q u a n tu m c lo c k s \u0001\u0001 G o a l G o a l : E x p re s s t h e o p e ra ti o n o f th e a q u a n tu m : E x p re s s t h e o p e ra ti o n o f th e a q u a n tu m c lo c k a s a b la c k b o x o ra c le p ro b le m . c lo c k a s a b la c k b o x o ra c le p ro b le m . A to m ic C lo c k B a s ic s A to m ic C lo c k B a s ic s \u0001\u0001 C o u n t th e t ic k s o f s o m e C o u n t th e t ic k s o f s o m e p e ri o d ic s y s te m a n d i n te rp re t p e ri o d ic s y s te m a n d i n te rp re t a s t im e . a s t im e . \u0001\u0001 A to m s h a v e a d is c re te s e t o f A to m s h a v e a d is c re te s e t o f e n e rg y l e v e ls a n d c a n e n e rg y l e v e ls a n d c a n tr a n s it io n b e tw e e n t h e m b y tr a n s it io n b e tw e e n t h e m b y a b s o rb in g o r e m it ti n g p h o to n s . a b s o rb in g o r e m it ti n g p h o to n s . ( E = ( E = h f h f )) \u0001\u0001 A to m ic c lo c k s c o u n t th e A to m ic c lo c k s c o u n t th e o s c ill a ti o n s o f a l a s e r w h o s e o s c ill a ti o n s o f a l a s e r w h o s e fr e q u e n c y i s s ta b ili z e d t o s o m e fr e q u e n c y i s s ta b ili z e d t o s o m e a to m ic t ra n s it io n a to m ic t ra n s it io n \u0001\u0001 1 s e c o n d 1 s e c o n d \u00C2\u00AA\u00C2\u00AA 9 ,1 9 2 ,6 3 1 ,7 7 0 9 ,1 9 2 ,6 3 1 ,7 7 0 c y c le s o f th e r a d ia ti o n c y c le s o f th e r a d ia ti o n c o rr e s p o n d in g t o a h y p e rf in e c o rr e s p o n d in g t o a h y p e rf in e tr a n s it io n i n C e s iu m tr a n s it io n i n C e s iu m N IS T F 1 S p e c tr o s c o p y S p e c tr o s c o p y \u00E2\u0080\u00A2 T h is a c ts a s o u r b la c k b o x /o ra c le o p e ra ti o n . G o a l: P h a s e E s ti m a ti o n \u00E2\u0080\u00A2 C o n s id e r a s e t o f N io n s a n d t h e s e t o f s ta te s l a b e le d b y w h ic h h a v e k io n s i n t h e e x c it e d s ta te a n d N - k io n s i n t h e g ro u n d s ta te . ( D ic k e s ta te s ) \u00E2\u0080\u00A2 O v e r ti m e , o u r la s e r/ c la s s ic a l o s c ill a to r w ill d ri ft f ro m t h e a to m ic r e s o n a n c e . W e n e e d t o m e a s u re a n d c o rr e c t th is d e tu n in g . \u00E2\u0080\u00A2 A ft e r a n i n te rr o g a ti o n p e ri o d o f le n g th T w it h a l a s e r tu n e d n e a r re s o n a n c e [ 7 ] | k\u00E3\u0080\u0089 |k \u00E3\u0080\u0089 \u00E2\u0086\u0092 e\u00E2\u0088\u0092 ik (f \u00E2\u0088\u0092 f 0 )T |k \u00E3\u0080\u0089 F re q u e n c y P ri o rs a n d t h e C lo c k O ra c le F re q u e n c y P ri o rs a n d t h e C lo c k O ra c le G iv e n f - f 0 w e k n o w t h a t: W e d o n \u00E2\u0080\u0099t k n o w f - f 0 , b u t w e c a n c o n s tr u c t a p ri o r p ro b a b ili ty d is tr ib u ti o n o v e r f - f 0 . L ik e w is e , b e fo re , w e d id n \u00E2\u0080\u0099t k n o w w h ic h o ra c le o u r a lg o ri th m w o u ld b e g iv e n , s o w e a s s ig n e d e a c h a p ro b a b ili ty . |k\u00E3\u0080\u0089 \u00E2\u0086\u0092 e\u00E2\u0088\u0092 ik (f \u00E2\u0088\u0092 f 0 )T |k\u00E3\u0080\u0089 T . R o s e n b a n d , N IS T C lo c k S D P C lo c k S D P A ft e r o n e q u e ry \u00E2\u0084\u00A6 = \u00E2\u0088\u0091 x| x \u00E3\u0080\u0089\u00E3\u0080\u0088x |e\u00E2\u0088\u0092 i\u00E2\u0088\u0086 f x \u00CF\u0083 z T / 2 \u00CF\u0081 O = \u00E2\u0088\u0091 x,y\u00E2\u0088\u009A p x \u00E2\u0088\u009A p y |x\u00E3\u0080\u0089 \u00E3\u0080\u0088y | \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 \u00CF\u0081 O Q \u00E2\u0084\u00A6 \u00E2\u0086\u0092 \u00E2\u0088\u0091 x,y\u00E2\u0088\u0091 k ,l a x ,y ,k ,l |x\u00E3\u0080\u0089 \u00E3\u0080\u0088y |\u00E2\u008A\u0097 ei \u00E2\u0088\u0086 f x k T |k\u00E3\u0080\u0089 \u00E3\u0080\u0088l| e\u00E2\u0088\u0092 i\u00E2\u0088\u0086 f y lT \u00CF\u0081 Q = \u00E2\u0088\u0091 k,la k |k \u00E3\u0080\u0089 \u00E3\u0080\u0088l | G o a ls : 1 . D e te rm in e o p ti m a l in it ia l s ta te o f Q 2 . D e te rm in e o p ti m a l m e a s u re m e n t C lo c k C o s t F u n c ti o n C lo c k C o s t F u n c ti o n \u0001\u0001 M e a s u re w it h a d is c re te , c o m p le te P O V M M e a s u re w it h a d is c re te , c o m p le te P O V M w h o s e e le m e n ts e a c h c o rr e s p o n d t o a f re q u e n c y g u e s s , w h o s e e le m e n ts e a c h c o rr e s p o n d t o a f re q u e n c y g u e s s , \u00E2\u0088\u0086\u00E2\u0088\u0086 ff ii \u0001\u0001 R e m o te S ta te P re p a ra ti o n : R e m o te S ta te P re p a ra ti o n : \u0001\u0001 P e n a liz e g u e s s e s f a r fr o m t h e t ru e f re q u e n c y P e n a liz e g u e s s e s f a r fr o m t h e t ru e f re q u e n c y \u0001\u0001 F ro m t h e f in a l d e n s it y m a tr ix a n d t h e r e m o te ly p re p a re d F ro m t h e f in a l d e n s it y m a tr ix a n d t h e r e m o te ly p re p a re d m ix e d s ta te s , w e c a n r e c o n s tr u c t th is o p ti m a l P O V M m ix e d s ta te s , w e c a n r e c o n s tr u c t th is o p ti m a l P O V M \u00CF\u0083 i = tr Q (P Q i \u00CF\u0081 O Q ) (\u00CF\u0083 i) x ,x = P (m ea su r ed \u00E2\u0088\u0086 f i \u00E2\u0088\u00A9 f r eq u en cy = \u00E2\u0088\u0086 f x ) {P Q i } i. \u00E3\u0080\u0088 \u00E2\u0088\u0086 f x | A i| \u00E2\u0088\u0086 f x \u00E3\u0080\u0089 = (\u00E2\u0088\u0086 f i \u00E2\u0088\u0092 \u00E2\u0088\u0086 f x )2 D is c u s s io n D is c u s s io n \u0001\u0001 P ri o r w o rk h a s a s s u m e d a u n if o rm p ro b a b ili ty P ri o r w o rk h a s a s s u m e d a u n if o rm p ro b a b ili ty d is tr ib u ti o n o v e r c lo c k o ra c le s . d is tr ib u ti o n o v e r c lo c k o ra c le s . [4 ] [4 ] \u0001\u0001 T h is t e c h n iq u e i s s u b je c t to T h is t e c h n iq u e i s s u b je c t to d is c re ti z a ti o n d is c re ti z a ti o n e rr o r e rr o r \u0001\u0001 W o rk in g o n b o u n d s W o rk in g o n b o u n d s \u00E2\u0080\u0093\u00E2\u0080\u0093 e rr o r a p p e a rs s m a ll e rr o r a p p e a rs s m a ll \u0001\u0001 A l A l++ C lo c k a t N IS T i s a n a tu ra l a p p lic a ti o n o f th is C lo c k a t N IS T i s a n a tu ra l a p p lic a ti o n o f th is te c h n iq u e . U s e s o n ly 1 te c h n iq u e . U s e s o n ly 1 -- 2 i o n s a n d i s t h e m o s t 2 i o n s a n d i s t h e m o s t a c c u ra te c lo c k i n t h e w o rl d ( 8 .6 x 1 0 a c c u ra te c lo c k i n t h e w o rl d ( 8 .6 x 1 0 -- 1 8 1 8 ) ) [5 ,9 ] [5 ,9 ] R e s u lt s R e s u lt s \u00E2\u0080\u00A2 O p ti m a l in it ia l s ta te s h a v e e q u a l a m p lit u d e s f o r k io n s i n t h e e x c it e d s ta te a n d N \u00E2\u0080\u0093 k in t h e g ro u n d s ta te . e .g . fo r N = 3 : \u00E2\u0080\u00A2 O n e q u e ry o n 2 i o n s i s e q u iv a le n t to 2 q u e ri e s o n o n e i o n . N o t n e c e s s a ri ly t ru e w it h m o re i o n s a n d m o re q u e ri e s . |\u00CF\u0088 0 \u00E3\u0080\u0089= a 0 (|0 \u00E3\u0080\u0089+ |3\u00E3\u0080\u0089 ) + a 1 (|1 \u00E3\u0080\u0089+ |2\u00E3\u0080\u0089 ) A n a rr o w e r p o s te ri o r c o rr e s p o n d s t o a n i n c re a s e in k n o w le d g e . G re e n : P ri o rs R e d : P o s te ri o rs P (\u00E2\u0088\u0086 f |\u00E2\u0088\u0086 f i = 0) C o n c lu s io n s C o n c lu s io n s \u0001\u0001 T h is S D P f o rm u la ti o n i s a p o w e rf u l a n d h ig h ly T h is S D P f o rm u la ti o n i s a p o w e rf u l a n d h ig h ly g e n e ra l w a y o f d e s c ri b in g q u a n tu m a lg o ri th m s a n d g e n e ra l w a y o f d e s c ri b in g q u a n tu m a lg o ri th m s a n d q u a n tu m p ro c e s s e s q u a n tu m p ro c e s s e s \u0001\u0001 T h e s iz e o f th e S D P g ro w s q u ic k ly , b u t th is T h e s iz e o f th e S D P g ro w s q u ic k ly , b u t th is te c h n iq u e r e m a in s a p p lic a b le t o m a n y i n te re s ti n g te c h n iq u e r e m a in s a p p lic a b le t o m a n y i n te re s ti n g p ro b le m s . p ro b le m s . \u0001\u0001 H e re w e a n a ly z e d q u a n tu m c o m p u te rs s u b je c t to H e re w e a n a ly z e d q u a n tu m c o m p u te rs s u b je c t to d e c o h e re n c e d e c o h e re n c e , a n d d e v e lo p e d a t e c h n iq u e t o , a n d d e v e lo p e d a t e c h n iq u e t o e x a m in e t h e e x a m in e t h e \u00E2\u0080\u009C\u00E2\u0080\u009C q u a n tu m n e s s q u a n tu m n e s s \u00E2\u0080\u009D\u00E2\u0080\u009D o f a d e v ic e . o f a d e v ic e . \u0001\u0001 T h e a p p lic a ti o n o f o u r S D P t o q u a n tu m c lo c k s T h e a p p lic a ti o n o f o u r S D P t o q u a n tu m c lo c k s in d ic a te s t h a t it l ik e ly h a s m a n y o th e r a p p lic a ti o n s in d ic a te s t h a t it l ik e ly h a s m a n y o th e r a p p lic a ti o n s R e fe re n c e s R e fe re n c e s 1 . 1 . A . A . A m b a in is A m b a in is , , Q u a n tu m l o w e r b o u n d s b y q u a n tu m a rg u m e n ts Q u a n tu m l o w e r b o u n d s b y q u a n tu m a rg u m e n ts 2 . 2 . H . B a rn u m , M . S a k s , a n d M . H . B a rn u m , M . S a k s , a n d M . S z e g e d y S z e g e d y , , Q u a n tu m q u e ry c o m p le x it y Q u a n tu m q u e ry c o m p le x it y a n d s e m id e fi n it e p ro g ra m m in g a n d s e m id e fi n it e p ro g ra m m in g 3 . 3 . H . B a rn u m , H . B a rn u m , S e m id e fi n it e p ro g ra m m in g c h a ra c te ri z a ti o n a n d s p e c tr a l S e m id e fi n it e p ro g ra m m in g c h a ra c te ri z a ti o n a n d s p e c tr a l a d v e rs a ry m e th o d f o r q u a n tu m c o m p le x it y w it h a d v e rs a ry m e th o d f o r q u a n tu m c o m p le x it y w it h n o n c o m m u ti n g n o n c o m m u ti n g u n it a ry q u e ri e s u n it a ry q u e ri e s 4 . 4 . V . V . B u z e k B u z e k , R . , R . D e rk a D e rk a , a n d S . , a n d S . M a s s a r M a s s a r , , O p ti m a l q u a n tu m c lo c k s O p ti m a l q u a n tu m c lo c k s 5 . 5 . C .W . C h o u , e t. a l. , C .W . C h o u , e t. a l. , F re q u e n c y c o m p a ri s o n o f tw o h ig h F re q u e n c y c o m p a ri s o n o f tw o h ig h -- a c c u ra c y A l a c c u ra c y A l++ o p ti c a l c lo c k s o p ti c a l c lo c k s 6 . 6 . L . L . H u g h s to n H u g h s to n , R . , R . J o z s a J o z s a , a n d W . , a n d W . W o o te rs W o o te rs , , A c o m p le te c la s s if ic a ti o n o f A c o m p le te c la s s if ic a ti o n o f q u a n tu m e n s e m b le s h a v in g a g iv e n d e n s it y m a tr ix q u a n tu m e n s e m b le s h a v in g a g iv e n d e n s it y m a tr ix 7 . 7 . N .F . R a m s e y , N .F . R a m s e y , M o le c u la r B e a m s M o le c u la r B e a m s 8 . 8 . B . B . R e ic h a rd t R e ic h a rd t , R e fl e c ti o n s f o r q u a n tu m q u e ry c o m p le x it y : , R e fl e c ti o n s f o r q u a n tu m q u e ry c o m p le x it y : T h e g e n e ra l T h e g e n e ra l a d v e rs a ry b o u n d i s t ig h t fo r e v e ry a d v e rs a ry b o u n d i s t ig h t fo r e v e ry b o o le a n b o o le a n fu n c ti o n fu n c ti o n 9 . 9 . P .O . S c h m id t, e t. a l. , P .O . S c h m id t, e t. a l. , S p e c tr o s c o p y u s in g q u a n tu m l o g ic S p e c tr o s c o p y u s in g q u a n tu m l o g ic 1 0 . 1 0 . B . S c h u m a c h e r, B . S c h u m a c h e r, Q u a n tu m c o d in g Q u a n tu m c o d in g 1 1 . 1 1 . W . W . Z u re k Z u re k , , D e c o h e re n c e , D e c o h e re n c e , e in s e le c ti o n e in s e le c ti o n a n d t h e q u a n tu m o ri g in s o f th e a n d t h e q u a n tu m o ri g in s o f th e c la s s ic a l c la s s ic a l A lg o ri th m R e c o n s tr u c ti o n A lg o ri th m R e c o n s tr u c ti o n \u00E2\u0080\u00A2 S D P o u tp u ts a d e n s it y m a tr ix c o rr e s p o n d in g t o t h e s ta te o f th e c o m p u te r a t e v e ry t im e s te p \u00E2\u0080\u00A2 P u ri fy t h e f o llo w in g p a ir s o f s ta te s i n to A , w h e re | A | = | O || Q |E | \u00E2\u0080\u00A2 S in c e w e k n o w t h a t w e c a n s o lv e f o r th e i n te r- q u e ry u n it a ri e s . S in c e t h e S D P y ie ld s t h e s o lu ti o n w it h t h e o p ti m a l p ro b a b ili ty o f s u c c e s s , th is re c o n s tr u c ts a n o p ti m a l a lg o ri th m . (q u a n tu m o r c la s s ic a l) D \u00E2\u0080\u00A0 Q E t \u00E2\u0084\u00A6 \u00E2\u0080\u00A0 Q O \u00CF\u0081 O Q E (t )\u00E2\u0084\u00A6 Q O D Q E t \u00E2\u0086\u0092 \u00CF\u0081 \u00E2\u0080\u00B2O Q E A (t ) \u00CF\u0081 O Q E (t + 1 ) \u00E2\u0086\u0092 \u00CF\u0081 O Q E A (t + 1 ) \u00CF\u0081 O Q E A (t + 1) = U (t )\u00E2\u0080\u00A0 Q A \u00CF\u0081 \u00E2\u0080\u00B2 O Q E A (t )U (t )Q A M e a s u ri n g Q u a n tu m R e s o u rc e s M e a s u ri n g Q u a n tu m R e s o u rc e s \u0001\u0001 O u r S D P f o rm u la ti o n w ill y ie ld t h e a lg o ri th m w it h O u r S D P f o rm u la ti o n w ill y ie ld t h e a lg o ri th m w it h th e o p ti m a l p ro b a b ili ty o f s u c c e s s . th e o p ti m a l p ro b a b ili ty o f s u c c e s s . \u0001\u0001 B u t c a n w e f in d a n B u t c a n w e f in d a n \u00E2\u0080\u009C\u00E2\u0080\u009C a lt e rn a te a lt e rn a te \u00E2\u0080\u009D\u00E2\u0080\u009D a lg o ri th m w it h t h e a lg o ri th m w it h t h e s a m e p ro b a b ili ty o f s u c c e s s t h a t u s e s f e w e r s a m e p ro b a b ili ty o f s u c c e s s t h a t u s e s f e w e r q u a n tu m r e s o u rc e s ? q u a n tu m r e s o u rc e s ? \u0001\u0001 Q u a n ti fy q u a n tu m r e s o u rc e s v ia V o n N e u m a n n Q u a n ti fy q u a n tu m r e s o u rc e s v ia V o n N e u m a n n e n tr o p y e n tr o p y \u0001\u0001 B y S c h u m a c h e r B y S c h u m a c h e r \u00E2\u0080\u0099\u00E2\u0080\u0099 s q u a n tu m c o d in g , w e k n o w t h is s q u a n tu m c o d in g , w e k n o w t h is is t h e m in im u m n u m b e r o f q u b it s n e e d e d t o is t h e m in im u m n u m b e r o f q u b it s n e e d e d t o re p re s e n t a q u a n tu m s ta te re p re s e n t a q u a n tu m s ta te [ 1 0 ] [1 0 ] S (\u00CF\u0081 ) \u00E2\u0089\u00A1 tr (\u00CF\u0081 lg (\u00CF\u0081 )) S e p a ra te C o m p u ta ti o n a l P a th s S e p a ra te C o m p u ta ti o n a l P a th s \u0001\u0001 L e t th e o p ti m a l a lg o ri th m r u n n o rm a lly u n ti l ti m e L e t th e o p ti m a l a lg o ri th m r u n n o rm a lly u n ti l ti m e tt ss , th e n m e a s u re , th e n m e a s u re \u0001\u0001 Q u a n ti fy t h e q u a n tu m r e s o u rc e s n e e d e d t o r e a c h Q u a n ti fy t h e q u a n tu m r e s o u rc e s n e e d e d t o r e a c h ti m e s te p ti m e s te p tt ss + 1 + 1 \u0001\u0001 T ry t o e x p re s s a s t h e i n c o h e re n t s u m o f T ry t o e x p re s s a s t h e i n c o h e re n t s u m o f \u0001\u0001 T h e s e i n d e p e n d e n t c o m p u ta ti o n a l p a th s c a n b e T h e s e i n d e p e n d e n t c o m p u ta ti o n a l p a th s c a n b e c la s s ic a lly c o m b in e d . c la s s ic a lly c o m b in e d . \u0001\u0001 C a lc u la te e n tr o p y a s : C a lc u la te e n tr o p y a s : \u0001\u0001 S in c e t h e f u ll d e n s it y m a tr ix i s p u re : S in c e t h e f u ll d e n s it y m a tr ix i s p u re : \u00CF\u0081 O (t s ) \u00CF\u0081 O 1 (t s ), \u00CF\u0081 O 2 (t s ) .. .\u00CF\u0081 O n (t s ) S T = tr (\u00CF\u0081 O 1 )S ( \u00CF\u0081 O 1 tr (\u00CF\u0081 O 1 ) ) + tr (\u00CF\u0081 O 2 )S ( \u00CF\u0081 O 2 tr (\u00CF\u0081 O 2 ) ) + .. . S (\u00CF\u0081 O ) = S (\u00CF\u0081 Q A ) S p li tt in g S D P S p li tt in g S D P \u0001\u0001 A d d t h e f o llo w in g c o n s tr a in ts t o a n e w S D P A d d t h e f o llo w in g c o n s tr a in ts t o a n e w S D P \u0001\u0001 A d d a n o b je c ti v e w h ic h m a x im iz e s t h e d is ta n c e b e tw e e n A d d a n o b je c ti v e w h ic h m a x im iz e s t h e d is ta n c e b e tw e e n th e t w o s u b p a rt s o f th e o ra c le d e n s it y m a tr ix . th e t w o s u b p a rt s o f th e o ra c le d e n s it y m a tr ix . \u0001\u0001 T h is w ill b e a n o n lin e a r o b je c ti v e s o w e u s e a n i te ra ti v e T h is w ill b e a n o n lin e a r o b je c ti v e s o w e u s e a n i te ra ti v e s tr a te g y s tr a te g y w it h t h e u s u a l s e ts o f c o n s tr a in ts o n t h e s e n e w d e n s it y w it h t h e u s u a l s e ts o f c o n s tr a in ts o n t h e s e n e w d e n s it y m a tr ic e s . H e re , th e o ra c le d e n s it y m a tr ix i s t h e o p ti m a l m a tr ic e s . H e re , th e o ra c le d e n s it y m a tr ix i s t h e o p ti m a l s o lu ti o n t o o u r o ri g in a l S D P . s o lu ti o n t o o u r o ri g in a l S D P . tr Q (\u00CF\u0081 O Q 1 (t )) = \u00CF\u0081 O 1 (t ) tr Q (\u00CF\u0081 O Q 2 (t )) = \u00CF\u0081 O 2 (t ) \u00CF\u0081 O o p t( t) = \u00CF\u0081 O 1 (t ) + \u00CF\u0081 O 2 (t ) t \u00E2\u0089\u00A5 t s S p li tt in g R e s u lt s S p li tt in g R e s u lt s \u0001\u0001 R e c u rs iv e ly p e rf o rm t h is s p lit ti n g , c a lc u la ti n g t h e R e c u rs iv e ly p e rf o rm t h is s p lit ti n g , c a lc u la ti n g t h e e n tr o p y a t e a c h i te ra ti o n . e n tr o p y a t e a c h i te ra ti o n . \u0001\u0001 P a ri ty l o o k s c la s s ic a l in t h e P a ri ty l o o k s c la s s ic a l in t h e H a d a m a rd H a d a m a rd b a s is . b a s is . \u0001\u0001 E n tr o p y i s a b a s is i n d e p e n d e n t q u a n ti ty . E n tr o p y i s a b a s is i n d e p e n d e n t q u a n ti ty . 8 E le m e n t S e a rc h /O R : 0 . 2 .0 5 6 2 . 2 .0 0 9 6 4 . 2 .0 0 9 3 8 . 2 .0 0 9 3 4 E le m e n t P A R IT Y 0 . 2 2 . 1 4 . 0 8 . 0"@en . "Presentation"@en . "10.14288/1.0103170"@en . "eng"@en . "Unreviewed"@en . "Vancouver : University of British Columbia Library"@en . "Attribution-NonCommercial-NoDerivatives 4.0 International"@en . "http://creativecommons.org/licenses/by-nc-nd/4.0/"@en . "Graduate"@en . "adversary"@en . "semidefinite"@en . "clock"@en . "decoherence"@en . "algorithm"@en . "A Numerical Quantum and Classical Adversary"@en . "Text"@en . "Moving Image"@en . "http://hdl.handle.net/2429/30937"@en .