Go to  Advanced Search

A Numerical Quantum and Classical Adversary

Show full item record

Files in this item

Files Size Format Description   View
MullanQAMF.pdf 1.341Mb Adobe Portable Document Format   View/Open
WS Jul 25 Mullan.mp4 86.29Mb video/mp4 View in browser View/Open
Title: A Numerical Quantum and Classical Adversary
Author: Mullan, Michael
Subject Keywords adversary;semidefinite;clock;decoherence;algorithm
Issue Date: 2010-07-25
Publicly Available in cIRcle 2011-01-28
Abstract: 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.
Affiliation: Non UBC
URI: http://hdl.handle.net/2429/30937
Peer Review Status: Unreviewed
Scholarly Level: Graduate

This item appears in the following Collection(s)

Show full item record

All items in cIRcle are protected by copyright, with all rights reserved.

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893