Separations in query complexity based on pointer functions

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function f on n =2 k bits defined by a complete binary tree of NAND gates of depth k , which achieves R 0 ( f ) = O ( D ( f ) 0.7537… ). We show this is false by giving an example of a total boolean function f on n bits whose deterministic query complexity is Ω( n /log( n )) while its zero-error randomized query complexity is Õ(√ n ). We further show that the quantum query complexity of the same function is Õ( n 1/4 ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.

Authors

• Andris Ambainis
• Kaspars Balodis
• Aleksandrs Belovs
• Troy Lee
• Miklos Santha
• Juris Smotrovs

Keywords

• Deterministic algorithms
• Las Vegas
• Monte Carlo
• Quantum algorithms
• Randomized algorithms