An electrical-network reformulation of near-equilibrium chemical reaction networks yields quantum walk algorithms with quadratic query speedups for reachability and flux queries, and, under a new sigma-M rigidity condition, for Gibbs dissipation estimation.
Quantum walk search algorithms and effective resistance
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We consider the problem of finding a marked vertex in a graph from an arbitrary starting distribution, using a quantum walk based algorithm. We work in the framework introduced by Belovs which showed how to detect the existence of a marked vertex in $O(\sqrt{RW})$ quantum walk steps, where $R$ is the effective resistance and $W$ is the total weight of the graph. Our algorithm outputs a marked vertex in the same runtime up to a logarithmic factor in the number of marked vertices. When starting in the stationary distribution, this recovers the recent results of Ambainis et al. We also describe a new algorithm to estimate the effective resistance $R$.
fields
quant-ph 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Quantum Walks for Chemical Reaction Networks
An electrical-network reformulation of near-equilibrium chemical reaction networks yields quantum walk algorithms with quadratic query speedups for reachability and flux queries, and, under a new sigma-M rigidity condition, for Gibbs dissipation estimation.