On the uselessness of quantum queries (Q433109)

The paper treats the classical and quantum query complexity of oracles. These provide the values of an unknown function in response to queries and the task is to determine a property of the function. In the introduction, some easy-to-follow examples of useful and useless queries are presented. Afterwards, classical ``uselessness'' of \(k\) queries to the oracle is strictly defined: Knowledge of any \(k\) function values does not change the probability of the function to belong to a particular property class. The quantum generalization is straightforward: \(k\) quantum queries are useless if afterwards no measurement (described by a generalized POVM) changes the probability of the function to have the sought-after property. For example, in Deutsch's problem, a single classical query is useless whereas a single quantum query may be useful. The main result of the paper is that when \(2k\) classical queries are useless, also \(k\) quantum queries are, which gives a lower bound to useful quantum queries as \(k+1\). The paper provides three examples (a parity problem, a generalization of Deutsch's problem, and a polynomial interpolation problem) and of course the proof of the main theorem. The authors suggest to use their theorem for obtaining a lower bound of quantum query complexities. Although a bit technical, the paper is easy to read and recommendable for researchers interested in quantum query complexity with background in quantum algorithms.