Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Extended Learning Graphs for Triangle Finding

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and sparse instances. For dense graphs on n vertices, we get a query complexity of \(O(n^{5/4})\) without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS’14]. For sparse graphs with \(m\ge n^{5/4}\) edges, we get a query complexity of \(O(n^{11/12}m^{1/6}\sqrt{\log n})\), which is better than the one obtained by Le Gall and Nakajima [ISAAC’15] when \(m \ge n^{3/2}\). We also obtain an algorithm with query complexity \({O}(n^{5/6}(m\log n)^{1/6}+d_2\sqrt{n})\) where \(d_2\) is the quadratic mean of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall et al. based on the MNRS quantum walk framework [SICOMP’11].

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Aaronson, S., Ben-David, S., Kothari, R.: Separations in query complexity using cheat sheets. In: Proceedings of 48th ACM Symposium on Theory of Computing, pp. 863–876 (2016)

  2. Ambainis, A.: Quantum search with variable times. Theory Comput. Syst. 47(3), 786–807 (2010)

    Article  MathSciNet  Google Scholar 

  3. Ambainis, A.: Understanding quantum algorithms via query complexity (2017). arXiv:1712.06349

  4. Ambainis, A., Balodis, K., Belovs, A., Lee, T., Santha, M., Smotrovs, J.: Separations in query complexity based on pointer functions. In: Proceedings of 48th ACM Symposium on Theory of Computing, pp. 800–813 (2016)

  5. Beals, R., Buhrman, H., Cleve, R., Mosca, M., Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48(4), 778–797 (2001)

    Article  MathSciNet  Google Scholar 

  6. Belovs, A.: Learning-graph-based quantum algorithm for k-distinctness. In: Prooceedings of 53rd IEEE Symposium on Foundations of Computer Science, pp. 207–216 (2012)

  7. Belovs, A.: Span programs for functions with constant-sized 1-certificates. In: Proceedings of 44th Symposium on Theory of Computing Conference, pp. 77–84 (2012)

  8. Belovs, A., Childs, A., Jeffery, S., Kothari, R., Magniez, F.: Time-efficient quantum walks for 3-distinctness. In: Proceedings of 40th International Colloquium on Automata, Languages and Programming, pp. 105–122 (2013)

    Chapter  Google Scholar 

  9. Belovs, A., Lee, T.: Quantum algorithm for k-distinctness with prior knowledge on the input. Tech. Rep. arXiv:1108.3022 (2011)

  10. Belovs, A., Rosmanis, A.: On the power of non-adaptive learning graphs. In: Proceedings of 28th IEEE Conference on Computational Complexity, pp. 44–55 (2013)

  11. Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Quantum computation and information (Washington, DC, 2000), Contemp. Math., vol. 305, pp. 53–74. Amer. Math. Soc., Providence, RI (2002). https://doi.org/10.1090/conm/305/05215

  12. Buhrman, H., Dürr, C., Heiligman, M., Høyer, P., Magniez, F., Santha, M., Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Comput. 34(6), 1324–1330 (2005)

    Article  MathSciNet  Google Scholar 

  13. Childs, A: Lecture notes on quantum algorithms. Technical report, University of Maryland (2017). https://cs.umd.edu/~amchilds/qa/

  14. Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 454(1969), 339–354 (1998). https://doi.org/10.1098/rspa.1998.0164. Quantum coherence and decoherence (Santa Barbara, CA, 1996)

    Article  MathSciNet  Google Scholar 

  15. Le Gall, F.: Improved quantum algorithm for triangle finding via combinatorial arguments. In: Proceedings of 55th IEEE Foundations of Computer Science, pp. 216–225 (2014)

  16. Le Gall, F.: Nakajima, S.: Quantum algorithm for triangle finding in sparse graphs. In: Proceedings of 26th International Symposium Algorithms and Computation, pp. 590–600 (2015)

  17. Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of 28th ACM Symposium on the Theory of Computing, pp. 212–219 (1996)

  18. Høyer, P., Lee, T., Špalek, R.: Negative weights make adversaries stronger. In: Proceedings of 39th ACM Symposium on Theory of Computing, pp. 526–535 (2007)

  19. Høyer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error imputs. In: Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 2719, pp. 291–299. Springer, Berlin (2003). https://doi.org/10.1007/3-540-45061-0_25

    Chapter  Google Scholar 

  20. Høyer, P., Špalek, R.: Lower bounds on quantum query complexity. Bull. Eur. Assoc. Theor. Comput. Sci. 87, 78–103 (2005)

    MathSciNet  MATH  Google Scholar 

  21. Kitaev, A.: Quantum measurements and the Abelian stabilizer problem. Tech. Rep. arXiv:quant-ph/9511026 (1995)

  22. Kitaev, A.Y., Shen, A.H., Vyalyi, M.N.: Classical and quantum computation, Graduate Studies in Mathematics, vol. 47. American Mathematical Society, Providence, RI (2002). https://doi.org/10.1090/gsm/047. Translated from the 1999 Russian original by Lester J. Senechal

  23. Lee, T., Magniez, F., Santha, M.: Improved quantum query algorithms for triangle detection and associativity testing. Algorithmica 77, 459–486 (2017)

    Article  MathSciNet  Google Scholar 

  24. Lee, T., Mittal, R., Reichardt, B., Špalek, R., Szegedy, M.: Quantum query complexity of state conversion. In: Proceedings of 52nd IEEE Symposium on Foundations of Computer Science, pp. 344–353 (2011)

  25. Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. SIAM J. Comput. 40(1), 142–164 (2011)

    Article  MathSciNet  Google Scholar 

  26. Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413–424 (2007)

    Article  MathSciNet  Google Scholar 

  27. Nisan, N.: Crew prams and decision trees. SIAM J. Comput. 20(6), 999–1007 (1991)

    Article  MathSciNet  Google Scholar 

  28. Reichardt, B.: Reflections for quantum query algorithms. In: Proceedings of 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 560–569 (2011)

  29. Shor, P.: Algorithms for quantum computation: Discrete logarithm and factoring. SIAM J. Comput. 26(5), 1484–1509 (1997)

    Article  MathSciNet  Google Scholar 

  30. S̆palek, R.: Quantum algorithms, lower bounds, and time-space tradeoffs. PhD thesis (2006)

Download references

Acknowledgements

We would like to thank the anonymous referees for their comments which helped improving the exposition. This project was partially supported by the ERA-NET Cofund in Quantum Technologies project QuantAlgo and the French ANR Blanc project QuData.

Author information

Authors and Affiliations

  1. Ecole Normale Supérieure de Lyon, 69007, Lyon, France

    Titouan Carette

  2. ORFE, Princeton University, Princeton, NJ, 08540, USA

    Mathieu Laurière

  3. Université de Paris, IRIF, CNRS, 75013, Paris, France

    Frédéric Magniez

Authors
  1. Titouan Carette
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mathieu Laurière
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Frédéric Magniez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mathieu Laurière.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work has been partially supported by the European Commission project Quantum Algorithms (QALGO) and the French ANR Blanc Project RDAM.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Carette, T., Laurière, M. & Magniez, F. Extended Learning Graphs for Triangle Finding. Algorithmica 82, 980–1005 (2020). https://doi.org/10.1007/s00453-019-00627-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-019-00627-z

Keywords

Search

Navigation