Howard Barnum

We show that as far as query complexity is concerned, the workspace of a quantum computer used to evaluate f(x) by querying the bits of an n-bit string x can be limited to n + k, where f takes k bit strings as values. We give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm that attempts to evaluate f in t queries. We use semidefinite programming duality to formulate a dual SDP Phat(f, t, e) that is feasible if and only if f cannot be avluated within error e by a t-step quantum query algorithm. Using this SDP we derive a general lower bound for query complexity that encompasses a lower bound method of Ambainis and its generalizations. We give an interpretation of the primal SDP as a generalized form of branching in quantum computation.