Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.06796

Approximating Random Walks in $\widetilde{O}(\log n + \log^2 κ)$ Space for $κ$-Conditioned Graphs

Junzhao Yang

Published Oct 5, 2026• 0 citations
arXivHTMLPDF

Abstract

For $κ>1$, a directed graph is $κ$-conditioned if it is $κ$-mixing and its stationary distribution is approximated by the uniform distribution within a factor of $κ$. We present a deterministic algorithm that approximates the stationary distribution of a $κ$-conditioned graph to inverse polynomial relative error in $O((\log n + \log^2 κ) \log \log n)$ space. In the regime $κ= \exp(Θ(\log^αn))$ for any $α\in (0, 2/3)$, our result improves the best-known $O(\log n \sqrt{\log κ} / \sqrt{\log \log n})$ space bound for approximating $κ$-step random walks in general directed graphs by [Hoza, RANDOM 2021]. We release this preliminary version due to recent rumors of LLM-based progress on related problems and uncertainty about when those results may appear. Further implementation details will be provided in a subsequent version.

DOI
10.48550/arxiv.2610.06796

Related papers

Almost uniform sampling via quantum walks

Peter C. Richter

Many classical randomized algorithms (e.g. approximation algorithms for #P-complete problems) utilize the following random walk algorithm for almost uniform sampling from a state space S of cardinality N : run a symmetric ergodic Markov chain P on S for long enough to obtain a random state from within total variation distance of the uniform distribution over S . The running time of this algorithm, the so-called mixing time of P , is O (δ −1 (log N +log −1 )), where δ is the spectral gap of P . We present a natural quantum version of this algorithm based on repeated measurements of the quantum walk U t = e −i Pt . We show that it samples almost uniformly from S with logarithmic dependence on −1 just as the classical walk P does; previously, no such quantum walk algorithm was known. We then outline a framework for analysing its running time and formulate two plausible conjectures which together would imply that it runs in time O (δ −1/2 log N log −1 ) when P is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.

arXiv:quant-ph/0606202•New Journal of Physics•Mar 22, 2007•54 citations

Quantum Walk on the Line

Nayak Ashwin, Ashvin Vishwanath

Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider {\em quantum\/} walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''''. In particular, we show that after~$t$ time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval~$[-t/\sqrt{2},\;t/\sqrt{2}]$. This implies that the same walk defined on the circle mixes in {\em linear\/} time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.

•Dec 13, 2000•122 citations

Quantum Walk on the Line

Ashwin Nayak, Ashvin Vishwanath

Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''. We show that after t time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)]. This implies that the same walk defined on the circle mixes in_linear_ time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.

arXiv:quant-ph/0010117•Oct 31, 2000•14 citations

Quantum Walk Sampling by Growing Seed Sets

Simon Apers

This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as $\widetilde{O}(m^{1/3} δ^{-1/3})$, with $m$ the number of edges and $δ$ the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for $st$-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an $n$-node graph in time $\widetilde{O}(2^{n/3})$, surpassing the $Ω(2^{n/2})$ barrier set by index erasure.

arXiv:1904.11446•Leibniz international proceedings in informatics•Jan 1, 2019•2 citations

A Tale of Two Walks: From Kac to KMP and Back

Qian Chen, Jingcheng Liu, Minglong Qin +4 more

We reveal an unexpected connection between two interacting particle systems: Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. We first establish a mixing-time analogue of Aldous's conjecture for the KMP process on general graphs: the mixing time of the $t$-particle process on any connected $d$-vertex graph is at most $O(\log d)$ times the corresponding single-particle mixing time, uniformly in $t$. As an application, we improve the mixing-time bound for coordinate hit-and-run on the $n$-dimensional standard simplex from $\widetilde{O}(n^3)$ [KV26] to $O(n\log n)$, while removing the dependence on the initial distribution. We then show that the twirling channel induced by the parallel Kac's walk on the symmetric subspace can be exactly encoded by a Markov chain on partitions, which naturally lifts to a parallel KMP chain on the complete graph. We prove that $O(\log d+\log(1/\varepsilon))$ repetitions of the parallel Kac's walk suffice to approximate Haar twirling on the symmetric subspace of $(\mathbb{C}^d)^{\otimes t}$ to error $\varepsilon$, uniformly in all $t$. Our main technical contribution is a new structural property of KMP-type dynamics: conditional product structure, which holds for both the standard KMP processes on general graphs and the parallel KMP processes on complete graphs. Conditioned on suitable auxiliary randomness, the evolution of the labeled KMP process factorizes into independent single-particle updates. Combining this structure with an exact coupling inspired by the analysis of Kac's walk, we remove the dependence on the number of particles from the mixing bounds for both unlabeled KMP models. This bypasses the $\log(π_{\min}^{-1})$ dependency from spectral-gap arguments, which is often prohibitively large for many-particle systems. Using this framework, we prove mixing bounds that are sharp up to logarithmic factors for both unlabeled KMP models.

quant-pharXiv:2609.38044•Sep 30, 2026•0 citations

Quantum walk search algorithms and effective resistance

Stephen Piddock

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$.

arXiv:1912.04196•Dec 9, 2019•4 citations
Approximating Random Walks in O~(log⁡n+log⁡2κ)\widetilde{O}(\log n + \log^2 κ)O(logn+log2κ) Space for κκκ-Conditioned Graphs
For κ>1κ>1κ>1, a directed graph is κκκ-conditioned if it is κκκ-mixing and its stationary distribution is approximated by the uniform distribution within a factor of κκκ. We present a deterministic algorithm that approximates the stationary distribution of a κκκ-conditioned graph to inverse polynomial relative error in O((log⁡n+log⁡2κ)log⁡log⁡n)O((\log n + \log^2 κ) \log \log n)O((logn+log2κ)loglogn) space. In the regime κ=exp⁡(Θ(log⁡αn))κ= \exp(Θ(\log^αn))κ=exp(Θ(logαn)) for any α∈(0,2/3)α\in (0, 2/3)α∈(0,2/3), our result improves the best-known O(log⁡nlog⁡κ/log⁡log⁡n)O(\log n \sqrt{\log κ} / \sqrt{\log \log n})O(lognlogκ​/loglogn​) space bound for approximating κκκ-step random walks in general directed graphs by [Hoza, RANDOM 2021]. We release this preliminary version due to recent rumors of LLM-based progress on related problems and uncertainty about when those results may appear. Further implementation details will be provided in a subsequent version.
Many classical randomized algorithms (e.g. approximation algorithms for #P-complete problems) utilize the following random walk algorithm for almost uniform sampling from a state space S of cardinality N : run a symmetric ergodic Markov chain P on S for long enough to obtain a random state from within total variation distance of the uniform distribution over S . The running time of this algorithm, the so-called mixing time of P , is O (δ −1 (log N +log −1 )), where δ is the spectral gap of P . We present a natural quantum version of this algorithm based on repeated measurements of the quantum walk U t = e −i Pt . We show that it samples almost uniformly from S with logarithmic dependence on −1 just as the classical walk P does; previously, no such quantum walk algorithm was known. We then outline a framework for analysing its running time and formulate two plausible conjectures which together would imply that it runs in time O (δ −1/2 log N log −1 ) when P is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.
Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider {\em quantum\/} walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''''. In particular, we show that after~ttt time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval~[−t/2,  t/2][-t/\sqrt{2},\;t/\sqrt{2}][−t/2​,t/2​]. This implies that the same walk defined on the circle mixes in {\em linear\/} time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.
Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''. We show that after t time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)]. This implies that the same walk defined on the circle mixes in_linear_ time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as O~(m1/3δ−1/3)\widetilde{O}(m^{1/3} δ^{-1/3})O(m1/3δ−1/3), with mmm the number of edges and δδδ the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for ststst-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an nnn-node graph in time O~(2n/3)\widetilde{O}(2^{n/3})O(2n/3), surpassing the Ω(2n/2)Ω(2^{n/2})Ω(2n/2) barrier set by index erasure.
We reveal an unexpected connection between two interacting particle systems: Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. We first establish a mixing-time analogue of Aldous's conjecture for the KMP process on general graphs: the mixing time of the ttt-particle process on any connected ddd-vertex graph is at most O(log⁡d)O(\log d)O(logd) times the corresponding single-particle mixing time, uniformly in ttt. As an application, we improve the mixing-time bound for coordinate hit-and-run on the nnn-dimensional standard simplex from O~(n3)\widetilde{O}(n^3)O(n3) [KV26] to O(nlog⁡n)O(n\log n)O(nlogn), while removing the dependence on the initial distribution. We then show that the twirling channel induced by the parallel Kac's walk on the symmetric subspace can be exactly encoded by a Markov chain on partitions, which naturally lifts to a parallel KMP chain on the complete graph. We prove that O(log⁡d+log⁡(1/ε))O(\log d+\log(1/\varepsilon))O(logd+log(1/ε)) repetitions of the parallel Kac's walk suffice to approximate Haar twirling on the symmetric subspace of (Cd)⊗t(\mathbb{C}^d)^{\otimes t}(Cd)⊗t to error ε\varepsilonε, uniformly in all ttt. Our main technical contribution is a new structural property of KMP-type dynamics: conditional product structure, which holds for both the standard KMP processes on general graphs and the parallel KMP processes on complete graphs. Conditioned on suitable auxiliary randomness, the evolution of the labeled KMP process factorizes into independent single-particle updates. Combining this structure with an exact coupling inspired by the analysis of Kac's walk, we remove the dependence on the number of particles from the mixing bounds for both unlabeled KMP models. This bypasses the log⁡(πmin⁡−1)\log(π_{\min}^{-1})log(πmin−1​) dependency from spectral-gap arguments, which is often prohibitively large for many-particle systems. Using this framework, we prove mixing bounds that are sharp up to logarithmic factors for both unlabeled KMP models.
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(RW)O(\sqrt{RW})O(RW​) quantum walk steps, where RRR is the effective resistance and WWW 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 RRR.