Open Collections

A Numerical Quantum and Classical Adversary

University of British Columbia. Department of Physics and Astronomy; Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics; Pacific Institute for the Mathematical Sciences; Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.)

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.

Presentation

eng

Vancouver : University of British Columbia Library

10.14288/1.0103170

Non UBC

Graduate

DSpace