A Numerical Quantum and Classical Adversary Mullan, Michael
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.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International