Quantum query complexity and semi-definite programming

We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1. show that the workspace of a quantum computer can be limited to at most n + k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model. 2. 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 attempts to evaluate f in t queries. 3. use semidefinite programming duality to formulate a dual SDP P̂(f, t, ε) that is feasible if and only if f can not be evaluated within error ε by a t-step quantum query algorithm Using this SDP we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations. 4. Give an interpretation of a generalized form of branching in quantum computation.