University of Colorado at Boulder and the National Institute of Standards and Technology Mike Mullan and Emanuel Knill A Semidefinite Programming Formulation of Quantum and Classical Oracle Problems 4. 3. 2. 1. • • • Quantum Clocks Decoherence and analyzing a computation subject to noise Optimal algorithms using reduced quantum resources (briefly) Remote State Preparation, and a Generalized Objective Restricted Computation Can calculate exact error probabilities for a quantum computer optimally solving arbitrary quantum oracle problems Semidefinite Programming Formulation of Quantum Computation [2,3] Outline |ψ(t) = Ut ΩUt−1 Ω...ΩU0 |ψ(0) Quantum Query Algorithm: Arbitrary unitary operators interspersed with oracle operators acting on some initial state, followed by a measurement Semidefinite Programming: Linear programming with semidefinite constraints Try to express a quantum query algorithm as a semidefinite program (SDP): [1] (and recent progress given in [8]) Goal: Minimize the number of queries of a quantum query algorithm via a generalization of Ambainis’ adversary method Quantum Algorithms, Generically Ω|ψ(t) = i ai Ω|i → i 0 1 0 0 ai → − ai + 2 ∗ a Ω0 Ω1 Ω2 Ω3 ai (−1)Ωi |i U = Inversion about the Mean 1 4. ΩU0 |ψ(0) = 2 (|0 − |1 + |2 + |3 ) 5. U1 ΩU0 |ψ(0) = |1 3. 1 (−1)Ω0 |0 + (−1)Ω1 |1 + (−1)Ω2 |2 + (−1)Ω3 |3 ΩU0 |ψ(0) = 2 1 2. U0 |ψ(0) = (|0 + |1 + |2 + |3 ) 2 1. |ψ(0) = |0 Goal: Search – Find the marked element Grover’s Algorithm 0 1 0 0 Ω(0) 1 Ω(1) 0 Ω(2) 0 Ω(3) 0 0 1 0 0 1 0 0 0 We can also have: New Goal: Find the marked element → Identify the applied oracle Assume each oracle can be given to our computer with some probability Other Oracles Are Possible x,y √ √ px py |x y| O: Oracle system ρ = O i,j ai,j |i j| Q: Querier system ρQ = A: Ancilla Pure state over possible oracles The Computer ΩOQ = x,y √ √ px py |x y| O: Oracle system ρ = O i,j ai,j |i j| Q: Querier system ρQ = x A: Ancilla Pure state over possible oracles |x x|ΩQ (x) The Computer ΩOQ (|x ΩOQ = x,y Q O ⊗ ΩQ (x)|ψ A: Ancilla Pure state over possible oracles ) → (|x |x x|ΩQ (x) ⊗ |ψ x O √ √ px py |x y| O: Oracle system ρ = O i,j ai,j |i j| Q: Querier system ρQ = The Computer Q ) (0) = x,y i,j √ √ p 0 p0 OQ ρ (0) = √ √ p 1 p0 ρ OQ √ a1,0 a1,0 a0,0 a0,0 a0,1 .. . a0,1 .. . ρQ (0) √ √ p0 p1 .. . a1,0 a0,0 √ px py |x y| ⊗ ai,j |i j| a0,1 .. . The Initial Joint Density Matrix (0) = x,y i,j ρOQ (0)Ω → a0,1 .. . a0,1 .. . ρQ (0) √ √ p0 p1 .. . a1,0 a0,0 a0,1 .. . a1,0 a1,0 a0,0 a0,0 a0,1 .. . a0,1 .. . Ω(0)† Ω(0) √ √ p0 p1 Ω(0)† .. . a1,0 a0,0 a0,1 .. . √ √ px py |x y| ⊗ Ω(x)† ai,j |i j|Ω(y) a1,0 a1,0 a0,0 a0,0 √ px py |x y| ⊗ ai,j |i j| x,y i,j √ √ √ p0 p0 Ω(0)† = √ √ p1 p0 Ω(1)† Ω ρ † OQ √ √ p 0 p0 OQ ρ (0) = √ √ p 1 p0 ρ OQ The Initial Joint Density Matrix Ω(1) ρO (t) ≥ 0 ρO (0) = ρ0 t ∈ {0 . . . tf } ρO (t) = trQ (ρOQ (t)) ρOQ (t) ≥ 0, (Straightforward) Constraints Need both an objective and a set of linear constraints over ρOQ Quantum Algorithm → SDP (1) ρO (t) = trQA (Ut†QA Ω†OQ ρOQA (t − 1)ΩOQ UtQA ) |ψ(t) = Ut ΩUt−1 Ω...ΩU0 |ψ(0) Quantum Algorithm → SDP (2) ρO (t) = trQA (UtQA Ut†QA Ω†OQ ρOQA (t − 1)ΩOQ ) ρO (t) = trQA (Ut†QA Ω†OQ ρOQA (t − 1)ΩOQ UtQA ) |ψ(t) = Ut ΩUt−1 Ω...ΩU0 |ψ(0) Quantum Algorithm → SDP (2) ρO (t) = trQ (Ω†OQ ρOQ (t − 1)ΩOQ ) ρO (t) = trQA (UtQA Ut†QA Ω†OQ ρOQA (t − 1)ΩOQ ) ρO (t) = trQA (Ut†QA Ω†OQ ρOQA (t − 1)ΩOQ UtQA ) |ψ(t) = Ut ΩUt−1 Ω...ΩU0 |ψ(0) Quantum Algorithm → SDP (2) Leads to the SDP SE, corresponding to the application of SE = ρO (t) = trQ (Ω†OQ ρOQ (t − 1)ΩOQ ) oracle and unitary O ρ (0) = ρ0 operators as above t ∈ {0 . . . t } f OQ O ρ (t) ≥ 0, ρ (t) ≥ 0 O OQ ρ (t) = tr (ρ (t)) Q ρO (t) = trQ (Ω†OQ ρOQ (t − 1)ΩOQ ) ρO (t) = trQA (UtQA Ut†QA Ω†OQ ρOQA (t − 1)ΩOQ ) ρO (t) = trQA (Ut†QA Ω†OQ ρOQA (t − 1)ΩOQ UtQA ) |ψ(t) = Ut ΩUt−1 Ω...ΩU0 |ψ(0) Quantum Algorithm → SDP (2) QA 1. Q makes a measurement with any complete POVM {Pi }i The following protocol describes the measurement process at the end of the computation at time tf. [6] Measurement and Remote State Preparation σi = trQA (PiQA ρOQA (tf )) 2. Conditional on measurement outcome i, the oracle system state is (up to normalization) QA 1. Q makes a measurement with any complete POVM {Pi }i The following protocol describes the measurement process at the end of the computation at time tf. [6] Measurement and Remote State Preparation 3. We measure a cost function Ai on this remotely prepared state, which indicates how successful our algorithm was σi = trQA (PiQA ρOQA (tf )) 2. Conditional on measurement outcome i, the oracle system state is (up to normalization) QA 1. Q makes a measurement with any complete POVM {Pi }i The following protocol describes the measurement process at the end of the computation at time tf. [6] Measurement and Remote State Preparation Q’s POVM is unconstrained, but the set of states that can be O O prepared on O is restricted by: σ = ρ (tf ) i i 3. We measure a cost function Ai on this remotely prepared state, which indicates how successful our algorithm was σi = trQA (PiQA ρOQA (tf )) 2. Conditional on measurement outcome i, the oracle system state is (up to normalization) QA 1. Q makes a measurement with any complete POVM {Pi }i The following protocol describes the measurement process at the end of the computation at time tf. [6] Measurement and Remote State Preparation O (0) = ρ0 ρ t ∈ {0 . . . t } f ρO (t) = trQ (Ω†OQ ρOQ (t − 1)ΩOQ ) OQ O (t) ≥ 0, ρ (t) ≥ 0 ρ O OQ (t) = tr (ρ (t)) ρ Q i S = S M ∪ SE SE = SM M inimize tr(σi Ai ) subject to : i = ∀i σi ≥ 0 O O σ = ρ (tf ) i The Complete SDP i x:x=i (σi )x,x x|Ai |x = 1 − δ(i, x) This error probability will be exact. Q is free to choose the POVM which optimizes the cost function, and the SDP will find this optimum subject to its constraints. ǫ= Search: x = 1000, i = 2 Average Probability of Error: Probability that you had oracle x, measured outcome i, and that you shouldn’t measure outcome i on oracle x (σi )x,x = P (measured i ∩ oracle = x) Search: i = 2 – The marked element is in position 2 Each measurement outcome i corresponds to the querier’s guess of which oracle was applied Conventional Cost Function All experimentally available quantum computers are subject to noise Decoherence can reduce or eliminate any quantum advantage. All current, general quantum lower bound methods assume perfect quantum computation. We would like a way to characterize how “quantum” our device is Restricted Computation |ψ(0) OQE = x,i axx,i |x O |i Post Unitary, Pre-Query Q |ǫ0 E1 After each query, the environment will interact with the computer and will decohere the querier [11] Decoherence OQE = OQE = x,i x,i axi,a |x axx,i |x O O Q |ǫ0 E1 (−1)Ω(x)i |i |i Q |ǫi E1 |ǫ0 E2 E(t) ≡ E = E1 ⊗ E2 . . . ⊗ Et The size of the environment grows with every query, so at time t: |ψ(1) Post Query |ψ(0) Post Unitary, Pre-Query After each query, the environment will interact with the computer and will decohere the querier [11] Decoherence E: E1 A: Ancilla The environment is part of the oracle system that the querier has no access to, but acts on the querier during each query. O: Oracle System Q: Querier system Adding the Environment Et (t) = trQ (ρOQE (t)) t ∈ {0 . . . tf } ρOE (0) = ρ0 ρOE (t) = trQ (D †QEt Ω†OQ ρOQE (t − 1) ⊗ |ǫ0 ρ i OE σi Ai ) subject to: ρOE (t) ≥ 0 i σiOE = ρOE (T ) ρOQE (t) ≥ 0, ∀i σiOE ≥ 0 Minimize tr( The Extended SDP Et Et ǫ0 |ΩOQ D QEt ) Red: One qubit decoherence Green: Two qubit decoherence One or more qubits may decohere independently with probability p √ O Q E O Ω(x)i Q E |x |i |ǫ0 → 1 − p|x (−1) |i |ǫ0 + p|x O (−1)Ω(x)i |i Q |ǫ(i) Quantum/Classical Interpolation E See slides at end of talk for details Use an alternate SDP which tries to split the optimal algorithm into two or more parts that can be classically combined Use the Von Neumann entropy to quantify the quantum resources needed in each branch The size of the SDP grows rapidly, particularly when modeling decoherence. ( < 10 qubits ) Since the SDP outputs the optimal density matrix at every time step, we can reconstruct the inter-query unitaries, and hence the optimal algorithm We have recently explored these issues from an alternate angle by asking: Is there an equally optimal algorithm that uses fewer quantum resources? Comments Our SDP formulation is highly general, and can describe quantum processes as well as quantum query algorithms Specifically, if an element drawn from a continuous set of unitary operators, indexed by some parameter, acts on a state, our formulation can be used to optimally estimate the value of this parameter We will use this idea to optimize the accuracy of quantum clocks Goal: Express the operation of the a quantum clock as a black box oracle problem. Clocks Count the ticks of some periodic system and interpret as time. Atoms have a discrete set of energy levels and can transition between them by absorbing or emitting photons. ( E = hf ) Atomic clocks count the oscillations of a laser whose frequency is stabilized to some atomic transition 1 second ª 9,192,631,770 cycles of the radiation corresponding to a hyperfine transition in Cesium Atomic Clock Basics NIST F1 • This acts as our black box/oracle operation. Goal: Phase Estimation |k → e−ik(f −f0 )T |k • After an interrogation period of length T with a laser tuned near resonance [7] • Over time, our laser/classical oscillator will drift from the atomic resonance. We need to measure and correct this detuning. • Consider a set of N ions and the set of states labeled by |k which have k ions in the excited state and N - k ions in the ground state. (Dicke states) Spectroscopy |k → e−ik(f −f0 )T |k T. Rosenband, NIST We don’t know f - f0, but we can construct a prior probability distribution over f - f0. Likewise, before, we didn’t know which oracle our algorithm would be given, so we assigned each a probability. Given f - f0 we know that: Frequency Priors and the Clock Oracle x √ √ px py |x y| Ω† ρOQ Ω → x,y k,l Goals: 1. Determine optimal initial state of Q 2. Determine optimal measurement ax,y,k,l |x y| ⊗ ei∆fx kT |k l|e−i∆fy lT |x x|e−i∆fx σz T /2 x,y k,l ak |k l| After one query Ω= ρ = O ρ = Q Clock SDP From the final density matrix and the remotely prepared mixed states, we can reconstruct this optimal POVM ∆fx |Ai |∆fx = (∆fi − ∆fx )2 Penalize guesses far from the true frequency (σi )x,x = P (measured ∆fi ∩ f requency = ∆fx ) σi = trQ (PiQ ρOQ ) Remote State Preparation: Measure with a discrete, complete POVM {PiQ }i . whose elements each correspond to a frequency guess, ∆fi Clock Cost Function Prior work has assumed a uniform probability distribution over clock oracles. [4] This technique is subject to discretization error Working on bounds – error appears small Al+ Clock at NIST is a natural application of this technique. Uses only 1-2 ions and is the most accurate clock in the world ( 8.6 x 10-18 ) [5,9] Discussion • P (∆f|∆fi = 0) Red: Posteriors Green: Priors A narrower posterior corresponds to an increase in knowledge. One query on 2 ions is equivalent to 2 queries on one ion. Not necessarily true with more ions and more queries. |ψ0 = a0 (|0 + |3 ) + a1 (|1 + |2 ) • Optimal initial states have equal amplitudes for k ions in the excited state and N – k in the ground state. e.g. for N = 3: Results This SDP formulation is a powerful and highly general way of describing quantum algorithms and quantum processes The size of the SDP grows quickly, but this technique remains applicable to many interesting problems. Here we analyzed quantum computers subject to decoherence, and developed a technique to examine the “quantumness” of a device. The application of our SDP to quantum clocks indicates that it likely has many other applications Conclusions 11. 10. 9. 8. 7. 6. 5. 4. 3. 2. 1. A. Ambainis, Quantum lower bounds by quantum arguments H. Barnum, M. Saks, and M. Szegedy, Quantum query complexity and semidefinite programming H. Barnum, Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries V. Buzek, R. Derka, and S. Massar, Optimal quantum clocks C.W. Chou, et. al., Frequency comparison of two high-accuracy Al+ optical clocks L. Hughston, R. Jozsa, and W. Wooters, A complete classification of quantum ensembles having a given density matrix N.F. Ramsey, Molecular Beams B. Reichardt, Reflections for quantum query complexity: The general adversary bound is tight for every boolean function P.O. Schmidt, et. al., Spectroscopy using quantum logic B. Schumacher, Quantum coding W. Zurek, Decoherence, einselection and the quantum origins of the classical References we can solve for the inter-query unitaries. Since the SDP yields the solution with the optimal probability of success, this reconstructs an optimal algorithm. (quantum or classical) ρOQEA (t + 1) = U (t)†QA ρ′OQEA (t)U (t)QA • Since we know that ρOQE (t + 1) → ρOQEA (t + 1) D †QEt Ω†QO ρOQE (t)ΩQO D QEt → ρ′OQEA (t) • Purify the following pairs of states into A, where |A| = |O||Q|E| • SDP outputs a density matrix corresponding to the state of the computer at every timestep Algorithm Reconstruction By Schumacher’s quantum coding, we know this is the minimum number of qubits needed to represent a quantum state [10] S(ρ) ≡ tr(ρ lg(ρ)) Our SDP formulation will yield the algorithm with the optimal probability of success. But can we find an “alternate” algorithm with the same probability of success that uses fewer quantum resources? Quantify quantum resources via Von Neumann entropy Measuring Quantum Resources S(ρO ) = S(ρQA ) Try to express ρO (ts ) as the incoherent sum of O O ρO (t ), ρ (t ) . . . ρ s s 1 2 n (ts ) These independent computational paths can be classically combined. Calculate entropy as: ρO ρO 1 2 O O ST = tr(ρ1 )S )S + tr(ρ + ... 2 O O tr(ρ1 ) tr(ρ2 ) Since the full density matrix is pure: Let the optimal algorithm run normally until time ts, then measure Quantify the quantum resources needed to reach timestep ts + 1 Separate Computational Paths t ≥ ts Add an objective which maximizes the distance between the two subparts of the oracle density matrix. This will be a nonlinear objective so we use an iterative strategy with the usual sets of constraints on these new density matrices. Here, the oracle density matrix is the optimal solution to our original SDP. O (t)) = ρ trQ (ρOQ 2 (t) 2 O trQ (ρOQ (t)) = ρ 1 (t) 1 O O ρO (t) = ρ (t) + ρ opt 1 2 (t) Add the following constraints to a new SDP Splitting SDP 4 Element PARITY 0. 2 2. 1 4. 0 8. 0 Parity looks classical in the Hadamard basis. Entropy is a basis independent quantity. 8 Element Search/OR: 0. 2.056 2. 2.0096 4. 2.0093 8. 2.0093 Recursively perform this splitting, calculating the entropy at each iteration. Splitting Results
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics /
- A Numerical Quantum and Classical Adversary
Open Collections
Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics
A Numerical Quantum and Classical Adversary Mullan, Michael 2010-07-25
Page Metadata
Item Metadata
Title | A Numerical Quantum and Classical Adversary |
Creator |
Mullan, Michael |
Contributor | University of British Columbia. Department of Physics and Astronomy Pacific Institute for the Mathematical Sciences. Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics |
Date Issued | 2010-07-25 |
Description | 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. |
Subject |
adversary semidefinite clock decoherence algorithm |
Type |
Moving Image Other |
Language | eng |
Date Available | 2016-02-01 |
Provider | Vancouver : University of British Columbia Library |
DOI | 10.14288/1.0103170 |
URI | http://hdl.handle.net/2429/30937 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- [if-you-see-this-DO-NOT-CLICK]
- MullanQAMF.pdf [ 1.28MB ]
- [if-you-see-this-DO-NOT-CLICK]
- [if-you-see-this-DO-NOT-CLICK]
- [if-you-see-this-DO-NOT-CLICK]
- WS Jul 25 Mullan.mp4 [ 82.29MB ]
- Metadata
- JSON: 1.0103170.json
- JSON-LD: 1.0103170+ld.json
- RDF/XML (Pretty): 1.0103170.xml
- RDF/JSON: 1.0103170+rdf.json
- Turtle: 1.0103170+rdf-turtle.txt
- N-Triples: 1.0103170+rdf-ntriples.txt
- Original Record: 1.0103170 +original-record.json
- Full Text
- 1.0103170.txt
- Citation
- 1.0103170.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
Canada | 2 | 0 |
United States | 1 | 0 |
City | Views | Downloads |
---|---|---|
Vancouver | 2 | 0 |
Ashburn | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.59373.1-0103170/manifest