Abstract
The main objective of this paper is to show that the quantum query complexity Q(f) of an N-bit Boolean function f is bounded by a function of a simple and natural parameter, i.e., M = |{x|f(x) = 1}| or the size of f’s on-set. We prove that: (i) For \(poly(N)\le M\le 2^{N^d}\) for some constant 0 < d < 1, the upper bound of Q(f) is \(O(\sqrt{N\log M / \log N})\). This bound is tight, namely there is a Boolean function f such that \(Q(f) = \Omega(\sqrt{N\log M / \log N})\). (ii) For the same range of M, the (also tight) lower bound of Q(f) is \(\Omega(\sqrt{N})\). (iii) The average value of Q(f) is bounded from above and below by \(Q(f) = O(\log M +\sqrt{N})\) and \(Q(f) = \Omega (\log M/\log N+ \sqrt{N})\), respectively. The first bound gives a simple way of bounding the quantum query complexity of testing some graph properties. In particular, it is proved that the quantum query complexity of planarity testing for a graph with n vertices is Θ(N 3/4) where \(N = \frac{n(n-1)}{2}\).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aaronson, S.: Lower bounds for local search by quantum arguments. SIAM J. Comput. 35(4), 804–824 (2006)
Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51(4), 595–605 (2004)
Ambainis, A.: A note on quantum black-box complexity of almost all Boolean functions. Inf. Process. Lett. 71(1), 5–7 (1999)
Ambainis, A.: Quantum lower bounds by quantum arguments. J. Comput. Sys. Sci. 64, 750–767 (2002)
Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007)
Ambainis, A., Childs, A.M., Reichardt, B.W., Špalek, R., Zhang, S.: Any AND-OR formula of size N can be evaluated in time N 1/2 + o(1) on a quantum computer. In: Proc. 48th FOCS, pp. 363–372 (2007)
Ambainis, A., Iwama, K., Kawachi, A., Masuda, H., Putra, R.H., Yamashita, S.: Quantum identification of Boolean oracles. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 105–116. Springer, Heidelberg (2004)
Ambainis, A., Iwama, K., Kawachi, A., Raymond, R., Yamashita, S.: Improved algorithms for quantum identification of Boolean oracles. Theor. Comput. Sci. 378(1), 41–53 (2007)
Anthony, M.: Classification by polynomial surfaces. Discrete Applied Mathematics 61, 91–103 (1995)
Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48(4), 778–797 (2001)
Buhrman, H., Cleve, R., de Wolf, R., Zalka, C.: Bounds for small-error and zero-error quantum algorithms. In: Proc. 40th FOCS, pp. 358–368 (1999)
Buhrman, H., Vereschagin, N., de Wolf, R.: On computation and communication with small bias. In: Proc. 22nd CCC, pp. 24–32 (2007)
van Dam, W.: Quantum oracle interrogation: getting all information for almost half the price. In: Proc. 39th FOCS, pp. 362–367 (1998)
Diestel, R.: Graph Theory, 2nd edn. Graduate Texts in Mathematics. Springer, Heidelberg (2000)
O’Donnell, R., Servedio, R.A.: Extremal properties of polynomial threshold functions. In: Proc. 18th CCC, pp. 3–12 (2003)
Dürr, C., Heiligman, M., Høyer, P., Mhalla, M.: Quantum query complexity of some graph problems. SIAM J. Comput. 35(6), 1310–1328 (2006)
Farhi, E., Goldstone, J., Gutmann, S.: A quantum algorithm for the Hamiltonian NAND tree. quant-ph/0702144 (2007)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proc. 28th STOC, pp. 212–219 (1996)
Høyer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 291–299. Springer, Heidelberg (2003)
Høyer, P., Špalek, R.: Lower bounds on quantum query complexity. Bulletin of the EATCS 87, 78–103 (2005)
Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proc. 39th STOC, pp. 575–584 (2007)
Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. In: Proc. ACM-SIAM SODA, pp. 1109–1117 (2005)
Montanaro, A., Nishimura, H., Raymond, R.: Unbounded-error quantum query complexity. In: Proc. 19th ISAAC (to appear, 2008)
Zhang, S.: On the power of Ambainis lower bounds. Theor. Comput. Sci. 339(2-3), 241–256 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ambainis, A. et al. (2008). Quantum Query Complexity of Boolean Functions with Small On-Sets. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_79
Download citation
DOI: https://doi.org/10.1007/978-3-540-92182-0_79
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92181-3
Online ISBN: 978-3-540-92182-0
eBook Packages: Computer ScienceComputer Science (R0)