Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems

Jianqiang Li; Sebastian Zur

doi:10.22331/q-2025-05-06-1733

Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems

Jianqiang Li^1,2 and Sebastian Zur³

¹Department of Computer Science and Engineering, Pennsylvania State University, PA
²Department of Computer Science, Rice University, Huston, TX
³CWI & QuSoft, the Netherlands

Published:	2025-05-06, volume 9, page 1733
Editor:	Aleksandrs Belovs
Eprint:	arXiv:2311.07372v6
Doi:	https://doi.org/10.22331/q-2025-05-06-1733
Citation:	Quantum 9, 1733 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Updated version: The authors have uploaded version v7 of this work to the arXiv which may contain updates or corrections not contained in the published version v6. The authors left the following comment on the arXiv:

minor update

Abstract

Recently, Apers and Piddock [TQC '23] strengthened the connection between quantum walks and electrical networks via Kirchhoff's Law and Ohm's Law. In this work, we develop a new multidimensional electrical network by defining Alternative Kirchhoff's Law and Alternative Ohm's Law based on the multidimensional quantum walk framework by Jeffery and Zur [STOC '23]. In analogy to the connection between the incidence matrix of a graph and Kirchhoff's Law and Ohm's Law in an electrical network, we rebuild the connection between the alternative incidence matrix and Alternative Kirchhoff's Law and Alternative Ohm's Law. This new framework enables generating an alternative electrical flow over the edges on graphs, which has the potential to be applied to a broader range of graph problems, benefiting both quantum and classical algorithm design.
We first use this framework to generate quantum alternative electrical flow states and use it to find a marked vertex in one-dimensional random hierarchical graphs as defined by Balasubramanian, Li, and Harrow [arXiv '23]. In this work, they generalised the exponential quantum-classical separation of the welded tree graph by Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman [STOC '03] to random hierarchical graphs. Our result partially recovers their results with an arguably simpler analysis.
Furthermore, this framework also allows us to demonstrate an exponential quantum speedup for the pathfinding problem in a type of regular graph, which we name the welded tree circuit graph. The exponential quantum advantage is obtained by efficiently generating quantum alternative electrical flow states and then sampling from them to find an s-t path in the welded tree circuit graph. By comparison, Li [arXiv '23] constructed a non-regular graph based on welded trees and used the degree information to achieve a similar speedup.

► BibTeX data

@article{Li2025multidimensional,
  doi = {10.22331/q-2025-05-06-1733},
  url = {https://doi.org/10.22331/q-2025-05-06-1733},
  title = {Multidimensional {E}lectrical {N}etworks and their {A}pplication to {E}xponential {S}peedups for {G}raph {P}roblems},
  author = {Li, Jianqiang and Zur, Sebastian},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1733},
  month = may,
  year = {2025}
}

► References

[1] Peter G. Doyle and J. Laurie Snell. ``Random walks and electric networks''. Mathematical Association of America. (1984).
https://doi.org/10.5948/UPO9781614440222

[2] László Lovász. ``Random walks on graphs: A survey''. In Dezső Miklós, Tamás Szőnyi, and Vera T. Sós, editors, Combinatorics, Paul Erdős is Eighty (Vol. 2). Pages 1–46. Bolyai Society Mathematical Studies. János Bolyai Mathematical Society (1996). url: http://web.cs.elte.hu/ lovasz/erdos.pdf.
http://web.cs.elte.hu/~lovasz/erdos.pdf

[3] Nisheeth K. Vishnoi. ``Lx = b''. Foundations and Trends® in Theoretical Computer Science 8, 1–141 (2013).
https://doi.org/10.1561/0400000054

[4] Daniel A. Spielman and Nikhil Srivastava. ``Graph sparsification by effective resistances''. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC). Pages 563–568. ACM (2008).
https://doi.org/10.1145/1374376.1374456

[5] Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. ``Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs''. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC). Pages 273–282. ACM (2011).
https://doi.org/10.1145/1993636.1993674

[6] Aleksander Madry. ``Navigating central path with electrical flows: From flows to matchings, and back''. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). Pages 253–262. IEEE (2013).
https://doi.org/10.1109/FOCS.2013.35

[7] Yu Gao, Yang Liu, and Richard Peng. ``Fully dynamic electrical flows: Sparse maxflow faster than goldberg–rao''. SIAM Journal on Computing 52, FOCS21–85 (2023).
https://doi.org/10.1137/22M1476666

[8] Daniel A. Spielman. ``Spectral and algebraic graph theory''. https://cs.yale.edu/homes/spielman/sagt/sagt.pdf (2019). Lecture notes, Yale University.
https://cs.yale.edu/homes/spielman/sagt/sagt.pdf

[9] Aleksandrs Belovs. ``Quantum walks and electric networks''. arXiv: 1302.3143 (2013).
arXiv:1302.3143

[10] Stephen Piddock. ``Quantum walk search algorithms and effective resistance''. arXiv: 1912.04196 (2019).
arXiv:1912.04196

[11] Simon Apers and Stephen Piddock. ``Elfs, trees and quantum walks'' (2022). url: https://arxiv.org/abs/2211.16379.
arXiv:2211.16379

[12] Guoming Wang. ``Efficient quantum algorithms for analyzing large sparse electrical networks''. Quantum Information & Computation 17, 987–1026 (2017).
https://doi.org/10.26421/QIC17.11-12-5

[13] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC) . Pages 193–204. (2019).
https://doi.org/10.1145/3313276.3316366

[14] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. ``Exponential algorithmic speedup by a quantum walk''. In Proceedings of the 35th ACM Symposium on the Theory of Computing (STOC) . Pages 59–68. (2003).
https://doi.org/10.1145/780542.780552

[15] Stacey Jeffery and Sebastian Zur. ``Multidimensional quantum walks''. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC). Pages 1125–1130. ACM (2023).
https://doi.org/10.1145/3564246.3585158

[16] Guanzhong Li, Lvzhou Li, and Jingquan Luo. ``Recovering the original simplicity: Succinct and deterministic quantum algorithm for the welded tree problem''. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 2454–2480. SIAM (2024).
https://doi.org/10.1137/1.9781611977912.87

[17] Shankar Balasubramanian, Tongyang Li, and Aram Harrow. ``Exponential speedups for quantum walks in random hierarchical graphs'' (2023). url: https://arxiv.org/abs/2307.15062.
arXiv:2307.15062

[18] András Gilyén, Matthew B. Hastings, and Umesh Vazirani. ``(sub)exponential advantage of adiabatic quantum computation with no sign problem''. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC). Pages 1357–1369. ACM (2021).
https://doi.org/10.1145/3406325.3451060

[19] Jianqiang Li. ``Exponential speedup of quantum algorithms for the pathfinding problem''. Quantum Information Processing 24, 67 (2025).
https://doi.org/10.1007/s11128-025-04689-7

[20] Scott Aaronson. ``Open problems related to quantum query complexity''. ACM Transactions on Quantum Computing 2, 1–9 (2021).
https://doi.org/10.1145/3488559

[21] Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, and Christophe Petit. ``Supersingular isogeny graphs and endomorphism rings: Reductions and solutions''. In Advances in Cryptology – EUROCRYPT 2018. Volume 10822 of Lecture Notes in Computer Science, pages 329–368. Springer International Publishing (2018).
https://doi.org/10.1007/978-3-319-78372-7_11

[22] Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren. ``Cryptographic hash functions from expander graphs''. Journal of Cryptology 22, 93–113 (2009).
https://doi.org/10.1007/s00145-007-9002-x

[23] Anamaria Costache, Brooke Feigon, Kristin Lauter, Maike Massierer, and Anna Puskás. ``Ramanujan graphs in cryptography''. In Research Directions in Number Theory. Volume 19 of Association for Women in Mathematics Series, pages 1–40. Springer International Publishing (2019).
https://doi.org/10.1007/978-3-030-19478-9_1

[24] Benjamin Wesolowski. ``The supersingular isogeny path and endomorphism ring problems are equivalent''. In Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Pages 1100–1111. IEEE (2021).
https://doi.org/10.1109/FOCS52979.2021.00109

[25] David Jao and Luca De Feo. ``Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies''. In Post-Quantum Cryptography – 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29–December 2, 2011, Proceedings. Volume 7071 of Lecture Notes in Computer Science, pages 19–34. Springer International Publishing (2011).
https://doi.org/10.1007/978-3-642-25405-5_2

[26] Sean Hallgren and Jianqiang Li. ``A quantum algorithm for the pathfinding problem via quantum electrical flow''. Manuscript in preparation (2023).

[27] Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. ``Quantum algorithm for path-edge sampling''. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Volume 266 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:28. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023).
https://doi.org/10.4230/LIPIcs.TQC.2023.5

[28] Adam Wesołowski and Stephen Piddock. ``Advances in quantum algorithms for the shortest path problem'' (2024). arXiv:2408.10427.
arXiv:2408.10427

[29] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. ``Quantum query complexity of some graph problems''. SIAM Journal on Computing 35, 1310–1328 (2006). arXiv:quant-ph/0401091.
https://doi.org/10.1137/050644719
arXiv:quant-ph/0401091

[30] Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani. ``Quantum algorithms and the power of forgetting''. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 37:1–37:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023). arXiv:2211.12447.
https://doi.org/10.4230/LIPIcs.ITCS.2023.37
arXiv:2211.12447

[31] Ewin Tang. ``A quantum-inspired classical algorithm for recommendation systems''. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC). Pages 217–228. (2019).
https://doi.org/10.1145/3313276.3316310

[32] Ewin Tang. ``Quantum-inspired classical algorithms for principal component analysis and supervised clustering''. arXiv: 1811.00414 (2018).
https://doi.org/10.1103/PhysRevLett.127.060503

[33] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. ``Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning''. In Proceedings of the 52nd ACM Symposium on the Theory of Computing (STOC). Page 387–400. (2020).
https://doi.org/10.1145/3357713.3384314

[34] Scott Aaronson. ``Read the fine print''. Nature Physics-7(t. Phys. 11, 291–293 (2015).
https://doi.org/10.1038/nphys3272

[35] Yu-Ao Chen and Xiao-Shan Gao. ``Quantum algorithm for boolean equation solving and quantum algebraic attack on cryptosystems''. Journal of Systems Science and Complexity 35, 373–412 (2022).
https://doi.org/10.1007/s11424-020-0028-6

[36] Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, and Jianqiang Li. ``Limitations of the macaulay matrix approach for using the hhl algorithm to solve multivariate polynomial systems''. Quantum 7, 1069 (2023).
https://doi.org/10.22331/q-2023-07-26-1069

[37] Dorit Aharonov and Amnon Ta‐Shma. ``Adiabatic quantum state generation''. SIAM Journal on Computing SIAM J. Comp. 37, 47–82 (2007).
https://doi.org/10.1137/060648829

[38] Lior Eldar and Sean Hallgren. ``An efficient quantum algorithm for lattice problems achieving subexponential approximation factor'' (2022). arXiv:2201.13450.
arXiv:2201.13450

[39] Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. ``Quantum hamiltonian complexity''. Foundations and Trends® in Theoretical Computer Science 10, 159–282 (2015). arXiv:1401.3916.
https://doi.org/10.1561/0400000066
arXiv:1401.3916

[40] Russell Lyons and Yuval Peres. ``Probability on trees and networks''. Volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics, pages xv+699. Cambridge University Press, New York. (2016).
https://doi.org/10.1017/9781316672815

[41] Alexei Y. Kitaev. ``Quantum measurements and the abelian stabilizer problem''. Technical Report TR96-003. Electronic Colloquium on Computational Complexity (ECCC) (1996). arXiv:quant-ph/9511026.
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv:quant-ph/9511026

[42] William McC. Siebert. ``Circuits, signals, and systems''. MIT Press. Cambridge, MA (1986). url: https://mitpress.mit.edu/9780262690959/circuits-signals-and-systems/.
https://mitpress.mit.edu/9780262690959/circuits-signals-and-systems/

[43] Lisa Hales and Sean Hallgren. ``An improved quantum fourier transform algorithm and applications''. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). Pages 515–525. IEEE (2000).
https://doi.org/10.1109/SFCS.2000.892139

[44] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Márió Szegedy. ``Quantum query complexity of state conversion''. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS) . Pages 344–353. (2011).
https://doi.org/10.1109/FOCS.2011.75

Cited by

[1] Guanzhong Li, Shiguang Feng, and Lvzhou Li, "Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma", Frontiers of Computer Science 20 10, 2010906 (2026).

[2] Essaddi Nejla, Khaoula Saidani, and Mongi Besbes, "Overcoming the integration bottleneck: a global review of renewable energy and grid adaptation strategies", International Journal of Sustainable Energy 44 1, 2569922 (2025).

[3] Adam Wesołowski and Stephen Piddock, "Advances in quantum algorithms for the shortest path problem", arXiv:2408.10427, (2024).

[4] Jianqiang Li and Yu Tong, "Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs", arXiv:2407.14398, (2024).

[5] Seenivasan Hariharan, Sebastian Zur, Sachin Kinge, Lucas Visscher, Kareljan Schoutens, and Stacey Jeffery, "Quantum Walks for Chemical Reaction Networks", arXiv:2509.07890, (2025).

[6] Guanzhong Li, Lvzhou Li, and Jingquan Luo, "Quantum phase discrimination with applications to quantum search on graphs", arXiv:2504.15194, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 04:04:16) and SAO/NASA ADS (last updated successfully 2026-08-07 21:58:39). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-09 04:04:16: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.