Monte Carlo to Las Vegas for Recursively Composed Functions

Abstract

For a (possibly partial) Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^{\ast }(f)={\lim }_{k\to \infty }M(f^k{)}^{1/k}$. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^{\ast }(f)=\max \{R^{\ast }(f),C^{\ast }(f)\}$. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.

25 pages