On the probabilistic query complexity of transitively symmetric problems

Abstract

(eng) We obtain optimal lower bounds on the nonadaptive probabilistic query complexity of a class of problems defined by a rather weak symmetry condition. In fact, for each problem in this class, given a number T of queries we compute exactly the performance (i.e., the probability of success on the worst instance) of the best nonadaptive probabilistic algorithm that makes T queries. We show that this optimal performance is given by a minimax formula involving certain probability distributions. Moreover, we identify two classes of problems for which adaptivity does not help. We illustrate these results on a few natural examples, including unordered search, Simon’s problem, distinguishing one-to-one functions from two-to-one functions, and hidden translation. For these last three examples (which are of particular interest in quantum computing), the recent theorems of Aaronson, of Laplante and Magniez, and of Bar-Yossef, Kumar and Sivakumar on the probabilistic complexity of black-box problems do not yield any nonconstant lower bound. (fre) Nous dérivons des bornes inférieures optimales sur la complexité en requête des algorithmes probabilistes non adaptatifs pour une classe de problèmes définie par une condition de symétrie assez faible. En réalité, pour chaque problème de cette classe, nous calculons exactement la performance optimale d’un algorithme non adaptatif de complexité donnée T . Nous montrons que cette performance optimale est donnée par une formule min-max faisant intervenir certaines distributions de probabilité. De plus, nous identifions deux classes de problèmes pour lesquels l’adaptivité n’aide pas. Nous illustrons ces résultats sur quelques exemples naturels, dont la recherche dans un tableau non trié, le problème de Simon, le problème de la translation cachée. Pour certains de ces exemples, qui sont d’un intérêt particulier en calcul quantique, les théorèmes récents d’Aaronson, de Laplante et Magniez, et de Bar-Yossef, Kumar and Sivakumar sur la complexité en requête probabiliste ne donnent pas mieux qu’une borne inférieure constante.