On the probabilistic query complexity of transitively symmetric problems

Pascal Koiran (1) , Vincent Nesme (1) , Natacha Portier (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

We obtain optimal lower bounds on the nonadaptive probabilistic query complexityof a class of problems defined by a rather weak symmetry condition. Infact, for each problem in this class, given a number T of queries we computeexactly the performance (i.e., the probability of success on the worst instance)of the best nonadaptive probabilistic algorithm that makes T queries. We showthat this optimal performance is given by a minimax formula involving certainprobability distributions. Moreover, we identify two classes of problems forwhich adaptivity does not help.We illustrate these results on a few natural examples, including unorderedsearch, Simon’s problem, distinguishing one-to-one functions from two-to-onefunctions, and hidden translation. For these last three examples (which are ofparticular interest in quantum computing), the recent theorems of Aaronson,of Laplante and Magniez, and of Bar-Yossef, Kumar and Sivakumar on theprobabilistic complexity of black-box problems do not yield any nonconstantlower bound.

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 adaptabilité 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.

Mots clés: Lower bounds; Probabilistic query complexity; Symmetry

Mots clés: Algorithmes probabilistes; Bornes inférieures; Complexité en requête; Symétrie

Domaines: Informatique [cs]

Pascal Koiran, Vincent Nesme, Natacha Portier. On the probabilistic query complexity of transitively symmetric problems. [Research Report] LIP RR-2006-27, Laboratoire de l'informatique du parallélisme. 2006, 2+18p. ⟨hal-02102308⟩