Document Open Access Logo

Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm

Authors Mitchell Black, William Maxwell

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.31.pdf
  • Filesize: 0.86 MB
  • 27 pages

Document Identifiers

Author Details

Mitchell Black
  • Oregon State University, Corvallis, OR, USA
William Maxwell
  • Oregon State University, Corvallis, OR, USA

Funding

This research was supported by NSF grants CCF-1816442 and CCF-1617951.

Acknowledgements

We would like to thank Amir Nayyeri for a helpful discussion about Theorem 17.

Cite AsGet BibTex

Mitchell Black and William Maxwell. Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 31:1-31:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.31

Abstract

We investigate generalizations of the graph theoretic notions of effective resistance and capacitance to simplicial complexes and prove analogs of formulas known in the case of graphs. In graphs the effective resistance between two vertices is O(n); however, we show that in a simplicial complex the effective resistance of a null-homologous cycle may be exponential. This is caused by relative torsion in the simplicial complex. We provide upper bounds on both effective resistance and capacitance that are polynomial in the number of simplices as well as the maximum cardinality of the torsion subgroup of a relative homology group denoted 𝒯_{max}(𝒦). We generalize the quantum algorithm deciding st-connectivity in a graph and obtain an algorithm deciding whether or not a (d-1)-dimensional cycle γ is null-homologous in a d-dimensional simplicial complex 𝒦. The quantum algorithm has query complexity parameterized by the effective resistance and capacitance of γ. Using our upper bounds we find that the query complexity is O (n^{5/2}⋅ d^{1/2} ⋅ 𝒯_{max}(𝒦)²). Under the assumptions that γ is the boundary of a d-simplex (which may or may not be included in the complex) and that 𝒦 is relative torsion-free, we match the O(n^{3/2}) query complexity obtained for st-connectivity. These assumptions always hold in the case of st-connectivity. We provide an implementation of the algorithm whose running time is polynomial in the size of the complex and the relative torsion. Finally, we prove a duality theorem relating effective resistance and capacitance when 𝒦 is d-dimensional and admits an embedding into ℝ^{d+1}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Simplicial complexes
  • quantum computing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aleksandrs Belovs and Ben W. Reichardt. Span programs and quantum algorithms for st-connectivity and claw detection. In Algorithms endash ESA 2012, pages 193-204. Springer Berlin Heidelberg, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_18.
  2. Chris Cade, Ashley Montanaro, and Aleksandrs Belovs. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. Quantum Info. Comput., 18(1–2):18-50, February 2018. Google Scholar
  3. A. K. Chandra, P. Raghavan, W. L. Ruzzo, and R. Smolensky. The electrical resistance of a graph captures its commute and cover times. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC '89, pages 574-586, New York, NY, USA, 1989. Association for Computing Machinery. URL: https://doi.org/10.1145/73007.73062.
  4. Cecil Jose A. Delfinado and Herbert Edelsbrunner. An incremental algorithm for betti numbers of simplicial complexes. In Proceedings of the Ninth Annual Symposium on Computational Geometry, SCG '93, pages 232-239, New York, NY, USA, 1993. Association for Computing Machinery. URL: https://doi.org/10.1145/160985.161140.
  5. Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy. Optimal homologous cycles, total unimodularity, and linear programming. SIAM J. Comput., 40(4):1026-1044, July 2011. URL: https://doi.org/10.1137/100800245.
  6. Tamal K. Dey, Tao Hou, and Sayan Mandal. Computing minimal persistent cycles: Polynomial and hard cases. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pages 2587-2606, USA, 2020. Society for Industrial and Applied Mathematics. Google Scholar
  7. Christoph Dürr, Mark Heiligman, Peter HOyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310-1328, January 2006. URL: https://doi.org/10.1137/050644719.
  8. Timothy Goldberg. Combinatorial laplacians of simplicial complexes. B.S. Thesis, Bard College, Annandale-on-Hudson, NY, 2002. Google Scholar
  9. Jakob Hansen and Robert Ghrist. Toward a spectral theory of cellular sheaves. Journal of Applied and Computational Topology, 3(4):315-358, August 2019. URL: https://doi.org/10.1007/s41468-019-00038-7.
  10. Allen Hatcher. Algebraic topology. Cambridge Univ. Press, Cambridge, 2000. URL: https://cds.cern.ch/record/478079.
  11. Tsuyoshi Ito and Stacey Jeffery. Approximate span programs. Algorithmica, 81(6):2158-2195, November 2018. URL: https://doi.org/10.1007/s00453-018-0527-1.
  12. Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum algorithms for connectivity and related problems. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1-49:13, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.49.
  13. Stacey Jeffery and Shelby Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26, August 2017. URL: https://doi.org/10.22331/q-2017-08-17-26.
  14. M. Karchmer and A. Wigderson. On span programs. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference. IEEE Comput. Soc. Press, 1993. URL: https://doi.org/10.1109/sct.1993.336536.
  15. G. Kirchhoff. Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird. Annalen der Physik, 148:497-508, 1847. Google Scholar
  16. A. Yu. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. arXiv e-prints, pages quant-ph/9511026, November 1995. URL: http://arxiv.org/abs/quant-ph/9511026.
  17. D. J. Klein and M. Randić. Resistance distance. Journal of Mathematical Chemistry, 12(1):81-95, December 1993. URL: https://doi.org/10.1007/BF01164627.
  18. Woong Kook and Kang-Ju Lee. Simplicial networks and effective resistance. Advances in Applied Mathematics, 100:71-86, 2018. URL: https://doi.org/10.1016/j.aam.2018.05.004.
  19. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142-164, January 2011. URL: https://doi.org/10.1137/090745854.
  20. William Maxwell and Amir Nayyeri. Generalized max-flows and min-cuts in simplicial complexes. CoRR, abs/2106.14116, 2021. URL: http://arxiv.org/abs/2106.14116.
  21. James R. Munkres. Elements of Algebraic Topology. CRC Press, March 1984. URL: https://doi.org/10.1201/9780429493911.
  22. Andrew Newman. Small simplicial complexes with prescribed torsion in homology. Discrete & Computational Geometry, 62(2):433-460, March 2018. URL: https://doi.org/10.1007/s00454-018-9987-y.
  23. Braxton Osting, Sourabh Palande, and Bei Wang. Spectral sparsification of simplicial complexes for clustering and label propagation, 2019. URL: http://arxiv.org/abs/1708.08436.
  24. Ben Reichardt and Robert Spalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8(1):291-319, 2012. URL: https://doi.org/10.4086/toc.2012.v008a013.
  25. Ben W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, October 2009. URL: https://doi.org/10.1109/focs.2009.55.
  26. Daniel Spielman. Spectral and algebraic graph theory, 2019. Google Scholar
  27. Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pages 563-568, New York, NY, USA, 2008. Association for Computing Machinery. URL: https://doi.org/10.1145/1374376.1374456.
  28. John Steenbergen, Caroline Klivans, and Sayan Mukherjee. A cheeger-type inequality on simplicial complexes. Advances in Applied Mathematics, 56:56-77, 2014. URL: https://doi.org/10.1016/j.aam.2014.01.002.
  29. Mario Szegedy. Quantum speed-up of markov chain based algorithms. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 32-41, November 2004. URL: https://doi.org/10.1109/FOCS.2004.53.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact