Abstract
We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time \(\tilde O(N^{1/3})\), beating the \(\Omega(\sqrt{N})\) classical lower bound. For testing expansion, we also prove an \(\tilde\Omega(N^{1/4})\) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aaronson, S.: Quantum lower bound for the collision problem. In: STOC, pp. 635–642 (2002)
Aaronson, S.: BQP and the polynomial hierarchy. In: STOC, pp. 141–150 (2010)
Aaronson, S., Ambainis, A.: The need for structure in quantum speedups. In: Innovations in Computer Science, pp. 338–352 (2011)
Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. of Algorithms 7(4), 567–583 (1986)
Alon, N., Goldreich, O., Hastad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms 3(3), 289–304 (1992)
Ambainis, A.: Quantum lower bounds by quantum arguments. J. of Computer and System Sciences 64(4), 750–767 (2002)
Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. on Computing 37(1), 210–239 (2007)
Ambainis, A., Childs, A.M., Liu, Y.-K.: Quantum property testing for bounded-degree graphs, arXiv:1012.3174 (2010)
Atici, A., Servedio, R.: Quantum algorithms for learning and testing juntas. Quantum Information Processing 6(5), 323–348 (2007)
Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. of the ACM 48(4), 778–797 (2001)
Buhrman, H., Durr, C., Heiligman, M., Hoyer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM J. on Computing 34(6), 1324–1330 (2005)
Buhrman, H., Fortnow, L., Newman, I., Rohrig, H.: Quantum property testing. SIAM J. on Computing 37(5), 1387–1400 (2008)
Bravyi, S., Harrow, A.W., Hassidim, A.: Quantum algorithms for testing properties of distributions. In: STACS, pp. 131–142 (2010)
Chakraborty, S., Fischer, E., Matsliah, A., de Wolf, R.: New results on quantum property testing. In: FSTTCS, pp. 145–156 (2010)
Childs, A.M., Kothari, R.: Quantum query complexity of minor-closed graph properties. To appear in STACS (2011)
Czumaj, A., Sohler, C.: Testing expansion in bounded-degree graphs. In: FOCS, pp. 570–578 (2007)
Durr, C., Heiligman, M., Hoyer, P., Mhalla, M.: Quantum query complexity of some graph problems. SIAM J. on Computing 35(6), 1310–1328 (2006)
Goldreich, O.: Randomized Methods in Computation, Lecture 2 (2001), http://www.wisdom.weizmann.ac.il/~oded/rnd.html
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. of the ACM 45(4), 653–750 (1998)
Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. Combinatorica 19(3), 335–373 (1999)
Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. ECCC report TR00-020 (2000)
Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32(2), 302–343 (2002)
Hoyer, P., Lee, T., Spalek, R.: Negative weights make adversaries stronger. In: STOC, pp. 526–535 (2007)
Inui, Y., Le Gall, F.: Quantum property testing of group solvability. In: LATIN 2008. LNCS, vol. 4957, pp. 772–783. Springer, Heidelberg (2008)
Kale, S., Seshadhri, C.: Testing expansion in bounded-degree graphs, ECCC report TR07-076 (2007)
Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. on Computing 37(2), 413–424 (2007)
Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: STOC, pp. 575–584 (2007)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Nachmias, A., Shapira, A.: Testing the expansion of a graph. Information and Computation 208, 309–314 (2010)
Paturi, R.: On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In: STOC, pp. 468–474 (1992)
Pinsker, M.: On the complexity of a concentrator. In: Proceedings of the 7th International Teletraffic Conference, pp. 318/1–318/4 (1973)
Santha, M.: Quantum walk based search algorithms. In: Theory and Applications of Models of Computation, pp. 31–46 (2008)
Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. In: FOCS, pp. 513–519 (2002)
Simon, D.R.: On the power of quantum computation. SIAM J. on Computing 26(5), 1474–1483 (1997)
Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: FOCS, pp. 32–41 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ambainis, A., Childs, A.M., Liu, YK. (2011). Quantum Property Testing for Bounded-Degree Graphs. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2011 2011. Lecture Notes in Computer Science, vol 6845. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22935-0_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-22935-0_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22934-3
Online ISBN: 978-3-642-22935-0
eBook Packages: Computer ScienceComputer Science (R0)