Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
arXiv:2311.07372 · doi:10.22331/q-2025-05-06-1733
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.
minor update
References in corpus (11)
- Exponential algorithmic speedup by quantum walk
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Quantum measurements and the Abelian Stabilizer Problem
- A quantum-inspired classical algorithm for recommendation systems
- Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
- Quantum Hamiltonian Complexity
- Quantum query complexity of state conversion
- Quantum query complexity of some graph problems
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
- Quantum Algorithm for Path-Edge Sampling