  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 by 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 error and number
of queries, 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 near-orthogonality of the final states of a quantum computer,
conditional on black-box inputs having distinct function values, rather than
bounded-error determinability of the function value via a single measurement on
the output states, 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 not-necessarily-commutative setting, of the
``spectral adversary method'' for quantum query lower bounds.
