License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.31
URN: urn:nbn:de:0030-drops-154641
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15464/
Black, Mitchell ;
Maxwell, William
Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm
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}.
BibTeX - Entry
@InProceedings{black_et_al:LIPIcs.ISAAC.2021.31,
author = {Black, Mitchell and Maxwell, William},
title = {{Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {31:1--31:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15464},
URN = {urn:nbn:de:0030-drops-154641},
doi = {10.4230/LIPIcs.ISAAC.2021.31},
annote = {Keywords: Simplicial complexes, quantum computing}
}
|
Keywords: |
|
Simplicial complexes, quantum computing |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
