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:2609.40314

Quantum Sampling of Random Spanning Trees via Amortized Data Structures

Yassine Hamoudi, Adrian Tanasa, Shrinidhi Teganahally Sridhara

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

We present a quantum algorithm that generates a uniform superposition over the spanning trees of a graph -- also known as a q-sample -- using only a sub-linear number of queries to the graph. This goes beyond previous work that focuses on generating classical samples, including a recent quantum algorithm by Apers, Gao, Ji, and Liu [ICALP 2025]. For an $n$-vertex, $m$-edge graph, our algorithm admits a pre-processing step of $\tilde{O}(\sqrt{mn} + m^{1-δ})$, after which each q-sample can be generated in $\tilde{O}(n^{1+2δ})$ for any $δ$. Alternatively, $k$ independent q-samples can be generated at a total cost of $\tilde{O}(\sqrt{kmn})$. We also prove a matching lower bound up to logarithmic factors, showing that our algorithm is essentially optimal. Further tradeoffs are given in the paper. In comparison, the optimal classical algorithms (Anari, Liu and Vuong [FOCS 2022]) need an $\tilde{O}(m)$ pre-processing step, after which each sample costs $\tilde{O}(n)$ operations. These results yield faster quantum walk-based algorithms for counting spanning trees or finding a marked one. Our result is obtained via quantum walk sampling over a sequence of slowly-changing Markov chains. Each chain is an isotropized up-down walk that mixes rapidly to the spanning tree distribution of the input graph. A key ingredient is an amortized data structure supporting fast implementation of the associated quantum walk operators throughout the sequence. This data structure maintains access to a spectral sparsifier and a leverage score sampler that evolve with the underlying graph.

AI Summary

The paper studies coherent sampling of spanning trees: given adjacency-list oracle access to a connected weighted graph with $n$ vertices and $m$ edges, prepare $|\pi\rangle=\sum_T\sqrt{\pi(T)}|T\rangle$, where $\pi(T)\propto\prod_{e\in T}w(e)$. This differs from outputting a classical random tree, since a classical sampler’s random-seed register cannot generally be erased efficiently. For $m\ge100n$ and $\rho\in[n/m,1]$, the algorithm uses $\widetilde O(\sqrt{mn/\rho})$ preprocessing queries, followed by $\widetilde O(\sqrt{mn\rho})$ queries per approximate q-sample. Reflections about the target state cost $\widetilde O(\sqrt{m\rho})$ queries. Optimizing the tradeoff gives $\widetilde O(\sqrt{kmn})$ total queries for $k\le m/n$ independent q-samples. A reduction from multiple threshold problems establishes a matching lower bound up to logarithmic factors, assuming per-copy error $O(1/k)$; beyond this range, query complexity saturates at $\widetilde\Theta(m)$. The construction uses quantum simulated annealing along $\widetilde O(\sqrt n)$ distributions obtained by uniformly rescaling edges outside a fixed spanning tree. A marginal-aware up-down walk has spectral gap $\widetilde\Omega(1/n)$ while retaining a temperature-independent tree encoding. Reusable sparsification data and a static envelope containing all potentially high-leverage edges reduce walk-implementation queries throughout the schedule. Applications include approximate counting and searching for marked trees. The speedups concern input-oracle queries, not runtime. The stated implementation takes $\widetilde O(n^2)$ time for preprocessing and each q-sample, uses quantum-readable classical memory, and leaves faster coherent dynamic-tree operations for future work.

Little sign of AI-generated textStrong assumptions

Error found: The abstract's unrestricted matching lower bound is false for k > m/n, where reading the entire graph caps query complexity at O(m). The advertised Õ(√(mn)) single-sample bound does not guarantee sublinear total queries for sparse graphs with m = Θ(n). The schedule-length proof drops the logarithm and uses π_G(S) where its reciprocal is required, although the corrected calculation recovers Õ(√n). The approximate-sampling lower-bound reduction asserts one-sided error without filtering zero-weight-edge trees that a TV-close distribution may output.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum Speedup for Sampling Random Spanning Trees

Simon Apers, Gao, Minbo, Zhengfeng Ji +1 more

We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.

Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

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 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•4 citations

Faster quantum sampling of Markov chains in nonregular graphs with fewer qubits

Xinying Li, Yun Shang

Sampling from the stationary distribution is one of the fundamental tasks of Markov-chain-based algorithms and has important applications in machine learning, combinatorial optimization, and network science. For the quantum case, quantum sampling from Markov chains corresponds to preparing quantum states with amplitudes arbitrarily close to the square root of a stationary distribution instead of classical sampling from a stationary distribution. A different quantum sampling algorithm for all reversible Markov chains is constructed by discrete-time quantum walks. We build a quantum sampling algorithm that not only accelerates nonregular graphs, but also keeps the speed up of existing quantum algorithms for regular graphs. In nonregular graphs, the invocation of the quantum fast-forwarding algorithm accelerates previous state-of-the-art quantum sampling algorithms for both discrete-time and continuous-time cases, especially on sparse graphs. Compared to existing algorithms, we decrease the runtime by a factor of $logn$, where $n$ is the number of graph vertices. In regular graphs, our results match other quantum algorithms and the reliance on the gap of Markov chains achieves quadratic speedup compared with classical cases. For both cases, we reduce the number of ancilla qubits required compared with the existing results. In some widely used graphs and a series of sparse graphs where stationary distributions are difficult to reach quickly, our algorithm achieves complete quadratic acceleration (without log factor) over the classical case without any limit. In addition, we construct a different reflection around the stationary state with fewer ancilla qubits and believe it may have an independent application.

arXiv:2205.06099•Physical Review A•Feb 27, 2023•4 citations

Quantum walks through generalized graph composition

Arjan Cornelissen

In this work, we generalize the recently-introduced graph composition framework to the non-boolean setting. A quantum algorithm in this framework is represented by a hypergraph, where each hyperedge is adjacent to multiple vertices. The input and output to the quantum algorithm is represented by a set of boundary vertices, and the hyperedges act like switches, connecting the input vertex to the output that the algorithm computes. Apart from generalizing the graph composition framework, our new proposed framework unifies the quantum divide and conquer framework, the decision-tree framework, and the unified quantum walk search framework. For the decision trees, we additionally construct a quantum algorithm from an improved weighting scheme in the non-boolean case. For quantum walk search, we show how our techniques naturally allow for amortization of the subroutines' costs. Previous work showed how one can speed up ``detection'' of marked vertices by amortizing the costs of the quantum walk. In this work, we extend these results to the setting of ``finding'' such marked vertices, albeit in some restricted settings. Along the way, we provide a novel analysis of irreducible, reversible Markov processes, by linear-algebraically connecting its effective resistance to the random walk operator. This significantly simplifies the algorithmic implementation of the quantum walk search algorithm, achieves an amortization speed-up for quantum walks over Johnson graphs, avoids the need for quantum fast-forwarding, and removes the log-factors from the query complexity statements.

arXiv:2510.04973•Oct 6, 2025•2 citations

Quantum approximate counting for Markov chains and collision counting

François Le Gall, Iu-Iong Ng

In this paper we show how to generalize the quantum approximate counting technique developed by Brassard, H{\o}yer and Tapp [ICALP 1998] to a more general setting: estimating the number of marked states of a Markov chain (a Markov chain can be seen as a random walk over a graph with weighted edges). This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful ``quantum walk based search'' framework established by Magniez, Nayak, Roland and Santha [SIAM Journal on Computing 2011]. As an application, we apply this approach to the quantum element distinctness algorithm by Ambainis [SIAM Journal on Computing 2007]: for two injective functions over a set of $N$ elements, we obtain a quantum algorithm that estimates the number $m$ of collisions of the two functions within relative error $\epsilon$ by making $\tilde{O}\left(\frac{1}{\epsilon^{25/24}}\big(\frac{N}{\sqrt{m}}\big)^{2/3}\right)$ queries, which gives an improvement over the $\Theta\big(\frac{1}{\epsilon}\frac{N}{\sqrt{m}}\big)$-query classical algorithm based on random sampling when $m\ll N$.

arXiv:2204.02552•Quantum Information and Computation•Oct 27, 2022•2 citations
We present a quantum algorithm that generates a uniform superposition over the spanning trees of a graph -- also known as a q-sample -- using only a sub-linear number of queries to the graph. This goes beyond previous work that focuses on generating classical samples, including a recent quantum algorithm by Apers, Gao, Ji, and Liu [ICALP 2025]. For an nnn-vertex, mmm-edge graph, our algorithm admits a pre-processing step of O~(mn+m1−δ)\tilde{O}(\sqrt{mn} + m^{1-δ})O~(mn​+m1−δ), after which each q-sample can be generated in O~(n1+2δ)\tilde{O}(n^{1+2δ})O~(n1+2δ) for any δδδ. Alternatively, kkk independent q-samples can be generated at a total cost of O~(kmn)\tilde{O}(\sqrt{kmn})O~(kmn​). We also prove a matching lower bound up to logarithmic factors, showing that our algorithm is essentially optimal. Further tradeoffs are given in the paper. In comparison, the optimal classical algorithms (Anari, Liu and Vuong [FOCS 2022]) need an O~(m)\tilde{O}(m)O~(m) pre-processing step, after which each sample costs O~(n)\tilde{O}(n)O~(n) operations. These results yield faster quantum walk-based algorithms for counting spanning trees or finding a marked one.
Our result is obtained via quantum walk sampling over a sequence of slowly-changing Markov chains. Each chain is an isotropized up-down walk that mixes rapidly to the spanning tree distribution of the input graph. A key ingredient is an amortized data structure supporting fast implementation of the associated quantum walk operators throughout the sequence. This data structure maintains access to a spectral sparsifier and a leverage score sampler that evolve with the underlying graph.
The paper studies coherent sampling of spanning trees: given adjacency-list oracle access to a connected weighted graph with nnn vertices and mmm edges, prepare ∣π⟩=∑Tπ(T)∣T⟩|\pi\rangle=\sum_T\sqrt{\pi(T)}|T\rangle∣π⟩=∑T​π(T)​∣T⟩, where π(T)∝∏e∈Tw(e)\pi(T)\propto\prod_{e\in T}w(e)π(T)∝∏e∈T​w(e). This differs from outputting a classical random tree, since a classical sampler’s random-seed register cannot generally be erased efficiently.
For m≥100nm\ge100nm≥100n and ρ∈[n/m,1]\rho\in[n/m,1]ρ∈[n/m,1], the algorithm uses O~(mn/ρ)\widetilde O(\sqrt{mn/\rho})O(mn/ρ​) preprocessing queries, followed by O~(mnρ)\widetilde O(\sqrt{mn\rho})O(mnρ​) queries per approximate q-sample. Reflections about the target state cost O~(mρ)\widetilde O(\sqrt{m\rho})O(mρ​) queries. Optimizing the tradeoff gives O~(kmn)\widetilde O(\sqrt{kmn})O(kmn​) total queries for k≤m/nk\le m/nk≤m/n independent q-samples. A reduction from multiple threshold problems establishes a matching lower bound up to logarithmic factors, assuming per-copy error O(1/k)O(1/k)O(1/k); beyond this range, query complexity saturates at Θ~(m)\widetilde\Theta(m)Θ(m).
The construction uses quantum simulated annealing along O~(n)\widetilde O(\sqrt n)O(n​) distributions obtained by uniformly rescaling edges outside a fixed spanning tree. A marginal-aware up-down walk has spectral gap Ω~(1/n)\widetilde\Omega(1/n)Ω(1/n) while retaining a temperature-independent tree encoding. Reusable sparsification data and a static envelope containing all potentially high-leverage edges reduce walk-implementation queries throughout the schedule. Applications include approximate counting and searching for marked trees.
The speedups concern input-oracle queries, not runtime. The stated implementation takes O~(n2)\widetilde O(n^2)O(n2) time for preprocessing and each q-sample, uses quantum-readable classical memory, and leaves faster coherent dynamic-tree operations for future work.
We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.
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.
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.
Sampling from the stationary distribution is one of the fundamental tasks of Markov-chain-based algorithms and has important applications in machine learning, combinatorial optimization, and network science. For the quantum case, quantum sampling from Markov chains corresponds to preparing quantum states with amplitudes arbitrarily close to the square root of a stationary distribution instead of classical sampling from a stationary distribution. A different quantum sampling algorithm for all reversible Markov chains is constructed by discrete-time quantum walks. We build a quantum sampling algorithm that not only accelerates nonregular graphs, but also keeps the speed up of existing quantum algorithms for regular graphs. In nonregular graphs, the invocation of the quantum fast-forwarding algorithm accelerates previous state-of-the-art quantum sampling algorithms for both discrete-time and continuous-time cases, especially on sparse graphs. Compared to existing algorithms, we decrease the runtime by a factor of lognlognlogn, where nnn is the number of graph vertices. In regular graphs, our results match other quantum algorithms and the reliance on the gap of Markov chains achieves quadratic speedup compared with classical cases. For both cases, we reduce the number of ancilla qubits required compared with the existing results. In some widely used graphs and a series of sparse graphs where stationary distributions are difficult to reach quickly, our algorithm achieves complete quadratic acceleration (without log factor) over the classical case without any limit. In addition, we construct a different reflection around the stationary state with fewer ancilla qubits and believe it may have an independent application.
In this work, we generalize the recently-introduced graph composition framework to the non-boolean setting. A quantum algorithm in this framework is represented by a hypergraph, where each hyperedge is adjacent to multiple vertices. The input and output to the quantum algorithm is represented by a set of boundary vertices, and the hyperedges act like switches, connecting the input vertex to the output that the algorithm computes. Apart from generalizing the graph composition framework, our new proposed framework unifies the quantum divide and conquer framework, the decision-tree framework, and the unified quantum walk search framework. For the decision trees, we additionally construct a quantum algorithm from an improved weighting scheme in the non-boolean case. For quantum walk search, we show how our techniques naturally allow for amortization of the subroutines' costs. Previous work showed how one can speed up ``detection'' of marked vertices by amortizing the costs of the quantum walk. In this work, we extend these results to the setting of ``finding'' such marked vertices, albeit in some restricted settings. Along the way, we provide a novel analysis of irreducible, reversible Markov processes, by linear-algebraically connecting its effective resistance to the random walk operator. This significantly simplifies the algorithmic implementation of the quantum walk search algorithm, achieves an amortization speed-up for quantum walks over Johnson graphs, avoids the need for quantum fast-forwarding, and removes the log-factors from the query complexity statements.
In this paper we show how to generalize the quantum approximate counting technique developed by Brassard, H{\o}yer and Tapp [ICALP 1998] to a more general setting: estimating the number of marked states of a Markov chain (a Markov chain can be seen as a random walk over a graph with weighted edges). This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful ``quantum walk based search'' framework established by Magniez, Nayak, Roland and Santha [SIAM Journal on Computing 2011]. As an application, we apply this approach to the quantum element distinctness algorithm by Ambainis [SIAM Journal on Computing 2007]: for two injective functions over a set of NNN elements, we obtain a quantum algorithm that estimates the number mmm of collisions of the two functions within relative error ϵ\epsilonϵ by making O~(1ϵ25/24(Nm)2/3)\tilde{O}\left(\frac{1}{\epsilon^{25/24}}\big(\frac{N}{\sqrt{m}}\big)^{2/3}\right)O~(ϵ25/241​(m​N​)2/3) queries, which gives an improvement over the Θ(1ϵNm)\Theta\big(\frac{1}{\epsilon}\frac{N}{\sqrt{m}}\big)Θ(ϵ1​m​N​)-query classical algorithm based on random sampling when m≪Nm\ll Nm≪N.