Tight bounds for hybrid quantum-classical query algorithms

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most q oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision ε requires Θ(1 over q ε squared) queries; (ii) (Unbiased) Amplitude estimation up to a precision ε requires Θ(p(1-p) over q ε squared) queries; (iii) Search among N items requires Θ(N over q) queries; (iv) Two level AND-OR tree (AND of m ORs, with n inputs to each OR) requires Θ(nm over q) queries. All of these bounds are optimal up to a constant factor, for all q from 1, corresponding to the classical complexity, to Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.