Abstract
Generalizing earlier work characterizing the quantum query
complexity of computing a function of an unknown classical ``black box''
function
drawn from some set of such black box functions,
we investigate a more general quantum query model in which
the goal is to compute
functions of $N imes N$ ``black box'' unitary matrices drawn from
a set of such matrices, a problem with
applications to determining properties of quantum physical systems.
We characterize the existence of an algorithm for such a query problem,
with given query and error, as equivalent to the feasibility of a certain set of semidefinite
programming constraints, or equivalently the infeasibility of a dual of these
constraints, which we construct. Relaxing the primal constraints to correspond
to mere pairwise nearorthogonality of the final states of a quantum computer, conditional
on the various blackbox inputs, rather than boundederror distinguishability,
we obtain a relaxed primal program the feasibility of
whose dual still implies the nonexistence of a quantum algorithm. We use this to obtain
a generalization, to our notnecessarilycommutative setting,
of the ``spectral adversary method'' for quantum query lower bounds.
BibTeX  Entry
@InProceedings{barnum:DSP:2007:876,
author = {Howard Barnum},
title = {Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries},
booktitle = {Algorithms and Complexity for Continuous Problems},
year = {2007},
editor = {Stephan Dahlke and Klaus Ritter and Ian H. Sloan and Joseph F. Traub},
number = {06391},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/876},
annote = {Keywords: Quantum query complexity semidefinite programming}
}
Keywords: 

Quantum query complexity semidefinite programming 
Seminar: 

06391  Algorithms and Complexity for Continuous Problems 
Issue Date: 

2007 
Date of publication: 

31.01.2007 