A Semidefinite Programming A Semidefinite Programming Formulation of Quantum and Formulation of Quantum and Classical Oracle ProblemsClassical Oracle ProblemsMike Mullan and Emanuel Mike Mullan and Emanuel KnillKnillUniversity of Colorado at Boulder and the University of Colorado at Boulder and the National Institute of Standards and TechnologyNational Institute of Standards and TechnologyOutlineOutline1.1.Semidefinite Programming Formulation of Quantum Semidefinite Programming Formulation of Quantum Computation Computation [2,3][2,3]••Can calculate Can calculate exactexacterror probabilities for a quantum error probabilities for a quantum computer optimally solving arbitrary quantum oracle computer optimally solving arbitrary quantum oracle problems problems 2.2.Remote State Preparation, and a Generalized Remote State Preparation, and a Generalized ObjectiveObjective3.3.Restricted ComputationRestricted Computation••Decoherence and analyzing a computation subject to Decoherence and analyzing a computation subject to noisenoise••Optimal algorithms using reduced quantum resources Optimal algorithms using reduced quantum resources (briefly)(briefly)4.4.Quantum ClocksQuantum ClocksQuantum Algorithms, GenericallyQuantum Algorithms, GenericallyQuantum Query Algorithm:Arbitrary unitary operators interspersed with oracle operators acting on some initial state, followed by a measurementSemidefinite Programming: Linear programming with semidefinite constraints|ψ(t)〉=UtΩUt−1Ω...ΩU0|ψ(0)〉Goal: Minimize the number of queries of a quantum query algorithmvia a generalization of Ambainis’adversary method [1] (and recent progress given in [8])Try to express a quantum query algorithmas a semidefinite program (SDP):GroverGrover’’s Algorithms Algorithm00001100U= Inversion about the Mean1. 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 2parenleftbig(−1)Ω0|0〉+(−1)Ω1|1〉+(−1)Ω2|2〉+(−1)Ω3|3〉parenrightbigai→−ai+2∗〈a〉Goal: Search –Find the marked elementΩ|ψ(t)〉=summationdisplay iaiΩ|i〉→summationdisplay iai(−1)Ωi |i〉Other Oracles Are PossibleOther Oracles Are Possible0000001100001100We can also have: 1100000000110000Assume each oracle can be given to our computer with some probabilityNew Goal: Find the marked element →Identify the applied oracleΩ(0)Ω(1)Ω(2)Ω(3)ρO=summationdisplay x,y√ px√py|x〉〈y|Q: QueriersystemρQ=summationdisplay i,jai,j|i〉〈j|O: Oracle systemPure state over possible oraclesThe ComputerThe ComputerA: AncillaρO=summationdisplay x,y√ px√py|x〉〈y|Q: QueriersystemρQ=summationdisplay i,jai,j|i〉〈j|O: Oracle systemΩOQ=summationdisplay x|x〉〈x|ΩQ(x) Pure state over possible oraclesThe ComputerThe ComputerA: AncillaρO=summationdisplay x,y√ px√py|x〉〈y|Q: QueriersystemρQ=summationdisplay i,jai,j|i〉〈j|O: Oracle systemΩOQ=summationdisplay x|x〉〈x|ΩQ(x) Pure state over possible oraclesThe ComputerThe ComputerA: AncillaΩOQ(|x〉O⊗|ψ〉Q)→(|x〉O⊗ΩQ(x)|ψ〉Q)The Initial Joint Density MatrixThe Initial Joint Density MatrixρOQ(0)=summationdisplay x,ysummationdisplay i,j√ px√py|x〉〈y|⊗ai,j|i〉〈j|ρOQ(0)= √ p0√p0parenleftBigga0,0a0,1a1,0. . .parenrightBigg√ p0√p1parenleftBigga0,0a0,1a1,0. . .parenrightBigg√ p1√p0parenleftBigga0,0a0,1a1,0. . .parenrightBigg. . . ρQ(0)The Initial Joint Density MatrixThe Initial Joint Density MatrixρOQ= √ p0√p0Ω(0)†parenleftBigga0,0a0,1a1,0. . .parenrightBiggΩ(0)√ p0√p1Ω(0)†parenleftBigga0,0a0,1a1,0. . .parenrightBiggΩ(1)√ p1√p0Ω(1)†parenleftBigga0,0a0,1a1,0. . .parenrightBiggΩ(0)†. . . ρOQ(0)=summationdisplay x,ysummationdisplay i,j√ px√py|x〉〈y|⊗ai,j|i〉〈j|ρOQ(0)= √ p0√p0parenleftBigga0,0a0,1a1,0. . .parenrightBigg√ p0√p1parenleftBigga0,0a0,1a1,0. . .parenrightBigg√ p1√p0parenleftBigga0,0a0,1a1,0. . .parenrightBigg. . . Ω†ρOQ(0)Ω→summationdisplay x,ysummationdisplay i,j√ px√py|x〉〈y|⊗Ω(x)† ai,j|i〉〈j|Ω(y)ρQ(0)Quantum Algorithm Quantum Algorithm →→SDP (1)SDP (1)ρOQNeed both an objective and a set of linear constraints over(Straightforward) ConstraintsρOQ(t)≥0,ρO(t)≥0ρO(t)=trQ(ρOQ(t))ρO(0)=ρ0t∈{0...tf}Quantum Algorithm Quantum Algorithm →→SDP (2)SDP (2)|ψ(t)〉=UtΩUt−1Ω...ΩU0|ψ(0)〉ρO(t)=trQA(U†QAtΩ†OQρOQA(t−1)ΩOQUQAt)Quantum Algorithm Quantum Algorithm →→SDP (2)SDP (2)|ψ(t)〉=UtΩUt−1Ω...ΩU0|ψ(0)〉ρO(t)=trQA(UQA tU†QA tΩ†OQρOQA(t−1)ΩOQ)ρO(t)=trQA(U†QAtΩ†OQρOQA(t−1)ΩOQUQAt)Quantum Algorithm Quantum Algorithm →→SDP (2)SDP (2)|ψ(t)〉=UtΩUt−1Ω...ΩU0|ψ(0)〉ρO(t)=trQ(Ω†OQρOQ(t−1)ΩOQ)ρO(t)=trQA(UQA tU†QA tΩ†OQρOQA(t−1)ΩOQ)ρO(t)=trQA(U†QAtΩ†OQρOQA(t−1)ΩOQUQAt)Quantum Algorithm Quantum Algorithm →→SDP (2)SDP (2)Leads to the SDP S E,corresponding to the application of oracle and unitary operators as above|ψ(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)=ρ0t∈{0...tf}ρO(t)=trQ(Ω†OQρOQ(t−1)ΩOQ)ρO(t)=trQA(UQA tU†QA tΩ†OQρOQA(t−1)ΩOQ)ρO(t)=trQA(U†QAtΩ†OQρOQA(t−1)ΩOQUQAt)Measurement and Remote State PreparationMeasurement and Remote State PreparationThe following protocol describes the measurement process at the end of the computation at time tf. [6]1.Q makes a measurement with any complete POVM{PQAi}iMeasurement and Remote State PreparationMeasurement and Remote State PreparationThe following protocol describes the measurement process at the end of the computation at time tf. [6]1.Q makes a measurement with any complete POVM2.Conditional on measurement outcome i, the oracle system state is (up to normalization) {PQAi}iσi=trQA(PQAiρOQA(tf))Measurement and Remote State PreparationMeasurement and Remote State PreparationThe following protocol describes the measurement process at the end of the computation at time tf. [6]1.Q makes a measurement with any complete POVM2.Conditional on measurement outcome i, the oracle system state is (up to normalization) 3. We measure a cost function Aion this remotely prepared state, which indicates how successful our algorithm was{PQAi}iσi=trQA(PQAiρOQA(tf))Measurement and Remote State PreparationMeasurement and Remote State PreparationThe following protocol describes the measurement process at the end of the computation at time tf. [6]1.Q makes a measurement with any complete POVM2.Conditional on measurement outcome i, the oracle system state is (up to normalization) 3. We measure a cost function Aion this remotely prepared state, which indicates how successful our algorithm wasQ’s POVM is unconstrained, but the set of states that can be prepared on O is restricted by:{PQAi}iσi=trQA(PQAiρOQA(tf)) summationtext iσO i=ρO(tf)The Complete SDPThe Complete SDPS=SM∪SESE= ρOQ(t)≥0,ρO(t)≥0ρO(t)=trQ(ρOQ(t))ρO(t)=trQ(Ω†OQρOQ(t−1)ΩOQ)ρO(0)=ρ0t∈{0...tf}SM= Minimizesummationdisplay itr(σiAi)subjectto:∀iσi≥0summationdisplay iσO i=ρO(tf)Conventional Cost FunctionConventional Cost Functioncircle6circle6Each measurement outcome Each measurement outcome iicorresponds to the corresponds to the querierquerier’’ssguess of which oracle was appliedguess of which oracle was appliedcircle6circle6Search: Search: i = 2i = 2––The marked element is in position The marked element is in position 22circle6circle6Average Probability of Error: Probability that you had Average Probability of Error: Probability that you had oracle oracle xx, measured outcome , measured outcome ii, and that you shouldn, and that you shouldn’’t t measure outcome measure outcome iion oracle on oracle xxcircle6circle6Search: Search: x = 1000, i = 2 x = 1000, i = 2 circle6circle6This error probability will be This error probability will be exactexact. Q is free to choose . Q is free to choose the POVM which optimizes the cost function, and the the POVM which optimizes the cost function, and the SDP will find this optimum subject to its constraints. SDP will find this optimum subject to its constraints. (σi)x,x=P(measuredi∩oracle=x)ǫ=summationtextisummationtextx:xnegationslash=i(σi)x,x〈x|Ai|x〉=1−δ(i,x)Restricted ComputationRestricted Computationcircle6circle6All experimentally available quantum All experimentally available quantum computers are subject to noise computers are subject to noise circle6circle6Decoherence can reduce or eliminate any Decoherence can reduce or eliminate any quantum advantage.quantum advantage.circle6circle6All current, general quantum lower bound All current, general quantum lower bound methods assume perfect quantum methods assume perfect quantum computation.computation.circle6circle6We would like a way to characterize how We would like a way to characterize how ““quantumquantum””our device isour device isDecoherenceDecoherenceAfter each query, the environment will interact with the computer and will decoherethe querier[11]Post Unitary, Pre-Query|ψ(0)〉OQE=summationdisplay x,iax x,i|x〉O|i〉Q|ǫ0〉E1DecoherenceDecoherenceAfter each query, the environment will interact with the computer and will decoherethe querier[11]Post Unitary, Pre-QueryPost QueryThe size of the environment grows with every query, so at time t:|ψ(0)〉OQE=summationdisplay x,iax x,i|x〉O|i〉Q|ǫ0〉E1|ψ(1)〉OQE=summationdisplay x,iax i,a|x〉O(−1)Ω(x)i|i〉Q|ǫi〉E1 |ǫ0〉E2E(t)≡E=E1⊗E2...⊗EtAdding the Environment Adding the Environment Q: QueriersystemA: AncillaO: Oracle SystemE 1E telipsisE:The environment is part of the oracle system that the querierhas no access to, but acts on the querierduring each query.The Extended SDPThe Extended SDPMinimizetr(summationtextiσiAi)subjectto:∀iσOEi≥0ρOQE(t)≥0,ρOE(t)≥0summationdisplay iσOEi=ρOE(T)ρOE(t)=trQ(ρOQE(t))ρOE(t)=trQ(D†QEtΩ†OQρOQE(t−1)⊗|ǫ0〉Et Et〈ǫ0|ΩOQDQEt)ρOE(0)=ρ0t∈{0...tf}Quantum/Classical InterpolationQuantum/Classical InterpolationOne or more qubits may decohereindependently with probability pRed: One qubitdecoherenceGreen: Two qubitdecoherence|x〉O|i〉Q|ǫ0〉E→radicalbig1−p|x〉O(−1)Ω(x)i|i〉Q|ǫ0〉E+√ p|x〉O(−1)Ω(x)i|i〉Q|ǫ(i)〉ECommentsCommentscircle6circle6The size of the SDP grows rapidly, particularly when The size of the SDP grows rapidly, particularly when modeling modeling decoherencedecoherence. ( < 10 qubits ). ( < 10 qubits )circle6circle6Since the SDP outputs the optimal density matrix at Since the SDP outputs the optimal density matrix at every time step, we can reconstruct the interevery time step, we can reconstruct the inter--query query unitariesunitaries, and hence the optimal algorithm, and hence the optimal algorithmcircle6circle6We have recently explored these issues from an We have recently explored these issues from an alternate angle by asking: alternate angle by asking: Is there an equally optimal Is there an equally optimal algorithm that uses fewer quantum resources?algorithm that uses fewer quantum resources?circle6circle6Use an alternate SDP which tries to split the optimal algorithm Use an alternate SDP which tries to split the optimal algorithm into two or more parts that can be classically combinedinto two or more parts that can be classically combinedcircle6circle6Use the Von Neumann entropy to quantify the quantum Use the Von Neumann entropy to quantify the quantum resources needed in each branchresources needed in each branchcircle6circle6See slides at end of talk for detailsSee slides at end of talk for detailsClocksClockscircle6circle6Our SDP formulation is highly general, and can Our SDP formulation is highly general, and can describe quantum describe quantum processesprocessesas well as quantum as well as quantum query algorithmsquery algorithmscircle6circle6Specifically, if an element drawn from a continuous Specifically, if an element drawn from a continuous set of unitary operators, indexed by some set of unitary operators, indexed by some parameter, acts on a state, our formulation can be parameter, acts on a state, our formulation can be used to optimally estimate the value of this used to optimally estimate the value of this parameterparametercircle6circle6We will use this idea to optimize the accuracy of We will use this idea to optimize the accuracy of quantum clocksquantum clockscircle6circle6GoalGoal: Express the operation of the a quantum : Express the operation of the a quantum clock as a black box oracle problem. clock as a black box oracle problem. Atomic Clock BasicsAtomic Clock Basicscircle6circle6Count the ticks of some Count the ticks of some periodic system and interpret periodic system and interpret as time.as time.circle6circle6Atoms have a discrete set of Atoms have a discrete set of energy levels and can energy levels and can transition between them by transition between them by absorbing or emitting photons. absorbing or emitting photons. ( E = ( E = hfhf))circle6circle6Atomic clocks count the Atomic clocks count the oscillations of a laser whose oscillations of a laser whose frequency is stabilized to some frequency is stabilized to some atomic transitionatomic transitioncircle6circle61 second 1 second ªª9,192,631,770 9,192,631,770 cycles of the radiation cycles of the radiation corresponding to a hyperfine corresponding to a hyperfine transition in Cesiumtransition in CesiumNIST F1SpectroscopySpectroscopy•This acts as our black box/oracle operation.Goal:Phase Estimation •Consider a set of Nions and the set of states labeled by which have kions in the excited state and N -kions in the ground state. (Dickestates) •Over time, our laser/classical oscillator will drift from the atomic resonance. We need to measure and correct this detuning.•After an interrogation period of length T with a laser tuned near resonance [7]|k〉|k〉→e−ik(f−f0)T |k〉Frequency Priors and the Clock OracleFrequency Priors and the Clock OracleGiven f -f0we know that:We don’t know f -f 0, but we can construct a prior probability distribution over f -f 0. Likewise, before, we didn’t know which oracle our algorithm would be given, so we assigned each a probability. |k〉→e−ik(f−f0)T |k〉T. Rosenband, NISTClock SDPClock SDPAfter one queryΩ=summationdisplay x|x〉〈x|e−i∆fxσzT/2ρO=summationdisplay x,y√ px√py|x〉〈y|Ω†ρOQΩ→summationdisplay x,ysummationdisplay k,lax,y,k,l|x〉〈y|⊗ei∆fxkT|k〉〈l|e−i∆fylTρQ=summationdisplay k,lak|k〉〈l|Goals: 1.Determine optimal initial state of Q2. Determine optimal measurementClock Cost FunctionClock Cost Functioncircle6circle6Measure with a discrete, complete POVM Measure with a discrete, complete POVM whose elements each correspond to a frequency guess, whose elements each correspond to a frequency guess, ∆∆ff iicircle6circle6Remote State Preparation:Remote State Preparation:circle6circle6Penalize guesses far from the true frequencyPenalize guesses far from the true frequencycircle6circle6From the final density matrix and the remotely prepared From the final density matrix and the remotely prepared mixed states, we can reconstruct this optimal POVM mixed states, we can reconstruct this optimal POVM σi=trQ(PQ iρOQ)(σi)x,x=P(measured∆fi∩frequency=∆fx){PQ i}i.〈∆fx|Ai|∆fx〉=(∆fi−∆fx)2DiscussionDiscussioncircle6circle6Prior work has assumed a uniform probability Prior work has assumed a uniform probability distribution over clock oracles. distribution over clock oracles. [4][4]circle6circle6This technique is subject to This technique is subject to discretizationdiscretizationerrorerrorcircle6circle6Working on bounds Working on bounds ––error appears smallerror appears smallcircle6circle6AlAl++Clock at NIST is a natural application of this Clock at NIST is a natural application of this technique. Uses only 1technique. Uses only 1--2 ions and is the most 2 ions and is the most accurate clock in the world ( 8.6 x 10accurate clock in the world ( 8.6 x 10--1818) ) [5,9][5,9]ResultsResults•Optimal initial states have equal amplitudes for kions in the excited state and N –kin the ground state. e.g. for N = 3:•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〉)A narrower posterior corresponds to an increase in knowledge. Green: PriorsRed: PosteriorsP(∆f|∆fi=0)ConclusionsConclusionscircle6circle6This SDP formulation is a powerful and highly This SDP formulation is a powerful and highly general way of describing quantum algorithms and general way of describing quantum algorithms and quantum processesquantum processescircle6circle6The size of the SDP grows quickly, but this The size of the SDP grows quickly, but this technique remains applicable to many interesting technique remains applicable to many interesting problems.problems.circle6circle6Here we analyzed quantum computers subject to Here we analyzed quantum computers subject to decoherencedecoherence, and developed a technique to , and developed a technique to examine the examine the ““quantumnessquantumness””of a device.of a device.circle6circle6The application of our SDP to quantum clocks The application of our SDP to quantum clocks indicates that it likely has many other applicationsindicates that it likely has many other applicationsReferencesReferences1.1.A. A. AmbainisAmbainis, , Quantum lower bounds by quantum argumentsQuantum lower bounds by quantum arguments2.2.H. Barnum, M. Saks, and M. H. Barnum, M. Saks, and M. SzegedySzegedy, , Quantum query complexity Quantum query complexity and semidefinite programmingand semidefinite programming3.3.H. Barnum, H. Barnum, Semidefinite programming characterization and spectral Semidefinite programming characterization and spectral adversary method for quantum complexity with adversary method for quantum complexity with noncommutingnoncommutingunitary queriesunitary queries4.4.V. V. BuzekBuzek, R. , R. DerkaDerka, and S. , and S. MassarMassar, , Optimal quantum clocksOptimal quantum clocks5.5.C.W. Chou, et. al., C.W. Chou, et. al., Frequency comparison of two highFrequency comparison of two high--accuracy Alaccuracy Al++optical clocksoptical clocks6.6.L. L. HughstonHughston, R. , R. JozsaJozsa, and W. , and W. WootersWooters, , A complete classification of A complete classification of quantum ensembles having a given density matrixquantum ensembles having a given density matrix7.7.N.F. Ramsey, N.F. Ramsey, Molecular BeamsMolecular Beams8.8.B. B. ReichardtReichardt, Reflections for quantum query complexity: , Reflections for quantum query complexity: The general The general adversary bound is tight for every adversary bound is tight for every booleanbooleanfunctionfunction9.9.P.O. Schmidt, et. al., P.O. Schmidt, et. al., Spectroscopy using quantum logicSpectroscopy using quantum logic10.10.B. Schumacher, B. Schumacher, Quantum codingQuantum coding11.11.W. W. ZurekZurek, , Decoherence, Decoherence, einselectioneinselectionand the quantum origins of the and the quantum origins of the classicalclassicalAlgorithm ReconstructionAlgorithm Reconstruction•SDP outputs a density matrix corresponding to the state of the computer at every timestep•Purify the following pairs of states into A, where |A| = |O||Q|E|•Since we know thatwe 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)D†QEtΩ†QOρOQE(t)ΩQODQEt→ρ′OQEA(t)ρOQE(t+1)→ρOQEA(t+1)ρOQEA(t+1)=U(t)†QAρ′OQEA(t)U(t)QAMeasuring Quantum ResourcesMeasuring Quantum Resourcescircle6circle6Our SDP formulation will yield the algorithm with Our SDP formulation will yield the algorithm with the optimal probability of success.the optimal probability of success.circle6circle6But can we find an But can we find an ““alternatealternate””algorithm with the algorithm with the same probability of success that uses fewer same probability of success that uses fewer quantum resources?quantum resources?circle6circle6Quantify quantum resources via Von Neumann Quantify quantum resources via Von Neumann entropyentropycircle6circle6By SchumacherBy Schumacher’’s quantum coding, we know this s quantum coding, we know this is the minimum number of qubits needed to is the minimum number of qubits needed to represent a quantum state represent a quantum state [10][10]S(ρ)≡tr(ρlg(ρ))Separate Computational PathsSeparate Computational Pathscircle6circle6Let the optimal algorithm run normally until time Let the optimal algorithm run normally until time tt ss, then measure, then measurecircle6circle6Quantify the quantum resources needed to reach Quantify the quantum resources needed to reach timesteptimesteptt ss+ 1+ 1circle6circle6Try to express as the incoherent sum of Try to express as the incoherent sum of circle6circle6These independent computational paths can be These independent computational paths can be classically combined.classically combined.circle6circle6Calculate entropy as:Calculate entropy as:circle6circle6Since the full density matrix is pure:Since the full density matrix is pure:ρO(ts)ρO 1(ts),ρO 2(ts)...ρO n(ts)ST=tr(ρO 1)SparenleftbiggρO 1 tr(ρO 1)parenrightbigg+tr(ρO 2)SparenleftbiggρO 2 tr(ρO 2)parenrightbigg+...S(ρO)=S(ρQA)Splitting SDPSplitting SDPcircle6circle6Add the following constraints to a new SDPAdd the following constraints to a new SDPcircle6circle6Add an objective which maximizes the distance between Add an objective which maximizes the distance between the two subparts of the oracle density matrix.the two subparts of the oracle density matrix.circle6circle6This will be a nonlinear objective so we use an iterative This will be a nonlinear objective so we use an iterative strategystrategywith the usual sets of constraints on these new density with the usual sets of constraints on these new density matrices. Here, the oracle density matrix is the optimal matrices. Here, the oracle density matrix is the optimal solution to our original SDP.solution to our original SDP.trQ(ρOQ 1(t))=ρO 1(t)trQ(ρOQ 2(t))=ρO 2(t)ρO opt(t)=ρO 1(t)+ρO 2(t)t≥tsSplitting ResultsSplitting Resultscircle6circle6Recursively perform this splitting, calculating the Recursively perform this splitting, calculating the entropy at each iteration.entropy at each iteration.circle6circle6Parity looks classical in the Parity looks classical in the HadamardHadamardbasis. basis. circle6circle6Entropy is a basis independent quantity.Entropy is a basis independent quantity.8 Element Search/OR:0. 2.0562. 2.00964. 2.00938. 2.00934 Element PARITY0. 22. 14. 08. 0
- 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
- MullanQAMF.pdf [ 1.28MB ]
- [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 |
---|---|---|
China | 30 | 9 |
United States | 11 | 0 |
Canada | 7 | 17 |
Russia | 1 | 0 |
France | 1 | 0 |
City | Views | Downloads |
---|---|---|
Beijing | 23 | 0 |
Shenzhen | 7 | 9 |
Ashburn | 5 | 0 |
Vancouver | 5 | 0 |
Unknown | 3 | 0 |
Mountain View | 3 | 0 |
Buffalo | 1 | 0 |
Wilmington | 1 | 0 |
Ottawa | 1 | 0 |
Montreal | 1 | 17 |
{[{ 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.29986.1-0103170/manifest