Separations in query complexity based on pointer functions

ABSTRACT

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₀(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.

We also construct a total boolean function g on n variables that has zero-error randomized query complexity Ω(n/log(n)) and bounded-error randomized query complexity R(g) = Õ(√n). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q_E(g) = Õ(√n).

These functions show that the relations D(f) = O(R₁(f)²) and R₀(f) = Õ(R(f)²) are optimal, up to poly-logarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R₀, a 3/2-power separation between Q_E and R, and a 4th power separation between approximate degree and bounded-error randomized query complexity.

All of these examples are variants of a function recently introduced by Goos, Pitassi, and Watson which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

References

1. S. Aaronson and A. Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Proc. of 47th ACM STOC, pages 307–316, 2015.
2. A. Ambainis. Superlinear advantage for exact quantum algorithms. In Proc. of 45th ACM STOC, pages 891–900, 2013.
3. R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001.
4. arXiv:quant-ph/9802049.
5. S. Ben-David. A super-Grover separation between randomized and quantum query complexities. arXiv:1506.08106, 2015.
6. M. Blum and R. Impagliazzo. Generic oracles and oracle classes. In Proc. of 28th IEEE FOCS, pages 118–126, 1987.
7. G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53–74, 2002.
8. G. Brassard, P. Høyer, and A. Tapp. Quantum counting. In Proc. of 25th ICALP, volume 1443 of LNCS, pages 820–831. Springer, 1998.
9. arXiv:quant-ph/9805082.
10. H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288:21–43, 2002.
11. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 454(1969):339–354, 1998.
12. D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proc. of the Royal Society London A, 439:553–558, 1992.
13. M. Göös, T. Pitassi, and T. Watson. Deterministic communication vs. partition number. In Proc. of 56th IEEE FOCS, pages 1077–1088, 2015.
14. L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc. of 28th ACM STOC, pages 212–219, 1996.
15. J. Hartmanis and L. A. Hemachandra. One-way functions, robustness, and non-isomorphism of NP-complete sets. In Proceedings of 2nd Structure in Complexity Theory, pages 160–173, 1987.
16. R. Kulkarni and A. Tal. On fractional block sensitivity. ECCC:2013/168, 2013.
17. G. Midrij¯ anis. Exact quantum query complexity for total boolean functions. arXiv:quant-ph/0403168, 2004.
18. G. Midrij¯ anis. On randomized and quantum query complexities. arXiv:quant-ph/0501142, 2005.
19. S. Mukhopadhyay and S. Sanyal. Towards better separation between deterministic and randomized query complexity. arXiv:1506.06399, 2015.
20. N. Nisan. CREW PRAMs and decision trees. SIAM Journal on Computing, 20(6):999–1007, 1991.
21. N. Nisan and M. Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4(4):301–313, 1994.
22. M. Saks and A. Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating game trees. In Proc. of 27th IEEE FOCS, pages 29–38, 1986.
23. M. Santha. On the Monte Carlo boolean decision tree complexity of read-once formulae. Random Structures and Algorithms, 6(1):75–87, 1995.
24. M. Snir. Lower bounds for probabilistic linear decision trees. Theoretical Computer Science, 38:69–82, 1985.
25. G. Tardos. Query complexity or why is it difficult to separate NP A ∩ coNP A from P A by a random oracle. Combinatorica, 9:385–392, 1990.
26. A. C. Yao. Probabilistic computations: toward a unified measure of complexity. In Proc. of 18th IEEE FOCS, pages 222–227, 1977.

Index Terms

• Theory of computation

  • Logic

  • Models of computation