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:1904.11446 · Leibniz international proceedings in informatics

Quantum Walk Sampling by Growing Seed Sets

Simon Apers

Published Jan 1, 2019• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.esa.2019.9

Related papers

Quantum Sampling of Random Spanning Trees via Amortized Data Structures

Yassine Hamoudi, Adrian Tanasa, Shrinidhi Teganahally Sridhara

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.

quant-pharXiv:2609.40314•Oct 1, 2026•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-Inspired Random Walk Algorithms for Graph Search

Jincheng Zhang

This paper explores the potential of quantum-inspired algorithms for graph search problems. Traditional random walk approaches often suffer from inefficiencies, particularly in complex graphs. We propose a novel framework that leverages concepts from quantum walks – specifically interference and tunneling – within a classical computational environment. Our algorithms dynamically adjust the probability distribution of node visits based on graph connectivity and the history of previous steps, mimicking the probabilistic nature of quantum mechanics. We demonstrate that this approach can, in certain scenarios, outperform standard random walks, offering a more adaptable and potentially faster search strategy. The core of the method lies in approximating the quantum effects through carefully designed classical simulations, without requiring actual quantum hardware. We present a mathematical formulation of the core algorithm and discuss its key parameters, focusing on the balance between classical simulation fidelity and computational cost. The results suggest a promising direction for graph search optimization, drawing inspiration from the principles of quantum mechanics.

•Sep 6, 2026•0 citations

Improvement of quantum walk-based search algorithms in single marked vertex graphs

Li, Xinying, Yun Shang

Quantum walks are powerful tools for building quantum search algorithms or quantum sampling algorithms named the construction of quantum stationary state. However, the success probability of those algorithms are all far away from 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problems follow. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in practical application of the algorithm when the optimal number of steps is not known. In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the soufflé problems. Then we combine generalized interpolation quantum walks with quantum fast-forwarding. The combination both reduce the times of calling walk operator of searching algorithm from $Θ((\varepsilon^{-1})\sqrt{\Heg})$ to $Θ(\log(\varepsilon^{-1})\sqrt{\Heg})$ and reduces the number of ancilla qubits required from $Θ(\log(\varepsilon^{-1})+\log\sqrt{\Heg})$ to $Θ(\log\log(\varepsilon^{-1})+\log\sqrt{\Heg})$, and the souffle problem is avoided while the success probability is improved, where $\varepsilon$ denotes the precision and $\Heg$ denotes the classical hitting time. Besides, we show that our generalized interpolated quantum walks can be used to improve the construction of quantum states corresponding to stationary distributions as well. Finally, we give an application that can be used to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.

arXiv:2209.04162•Sep 9, 2022•0 citations

Quantum Walk-Based Algorithms for Large-Scale Graph Search

Jincheng Zhang

This paper investigates the application of quantum walk algorithms to large-scale graph search problems. Classical algorithms often struggle with the computational complexity of exploring vast graphs, particularly when searching for specific patterns or nodes. Quantum walks, inspired by the probabilistic nature of random walks, provide a promising alternative by utilizing quantum superposition and interference to accelerate the search process. We explore the theoretical framework and potential advantages of employing quantum walks for graph traversal, focusing on scenarios where exponential speedups are theoretically possible. This work aims to demonstrate the potential of quantum computing to tackle computationally demanding graph search tasks that are currently intractable for classical methods. The core concept leverages the ability to simultaneously explore multiple paths within a graph, drastically reducing the search time compared to sequential exploration. We present a foundational understanding of quantum walk implementation and analyze its suitability for various graph search algorithms.

•Aug 28, 2026•0 citations

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
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 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.
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 paper explores the potential of quantum-inspired algorithms for graph search problems. Traditional random walk approaches often suffer from inefficiencies, particularly in complex graphs. We propose a novel framework that leverages concepts from quantum walks – specifically interference and tunneling – within a classical computational environment. Our algorithms dynamically adjust the probability distribution of node visits based on graph connectivity and the history of previous steps, mimicking the probabilistic nature of quantum mechanics. We demonstrate that this approach can, in certain scenarios, outperform standard random walks, offering a more adaptable and potentially faster search strategy. The core of the method lies in approximating the quantum effects through carefully designed classical simulations, without requiring actual quantum hardware. We present a mathematical formulation of the core algorithm and discuss its key parameters, focusing on the balance between classical simulation fidelity and computational cost. The results suggest a promising direction for graph search optimization, drawing inspiration from the principles of quantum mechanics.
Quantum walks are powerful tools for building quantum search algorithms or quantum sampling algorithms named the construction of quantum stationary state. However, the success probability of those algorithms are all far away from 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problems follow. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in practical application of the algorithm when the optimal number of steps is not known. In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the soufflé problems. Then we combine generalized interpolation quantum walks with quantum fast-forwarding. The combination both reduce the times of calling walk operator of searching algorithm from $Θ((\varepsilon^{-1})\sqrt{\Heg})$ to $Θ(\log(\varepsilon^{-1})\sqrt{\Heg})$ and reduces the number of ancilla qubits required from $Θ(\log(\varepsilon^{-1})+\log\sqrt{\Heg})$ to $Θ(\log\log(\varepsilon^{-1})+\log\sqrt{\Heg})$, and the souffle problem is avoided while the success probability is improved, where ε\varepsilonε denotes the precision and $\Heg$ denotes the classical hitting time. Besides, we show that our generalized interpolated quantum walks can be used to improve the construction of quantum states corresponding to stationary distributions as well. Finally, we give an application that can be used to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.
This paper investigates the application of quantum walk algorithms to large-scale graph search problems. Classical algorithms often struggle with the computational complexity of exploring vast graphs, particularly when searching for specific patterns or nodes. Quantum walks, inspired by the probabilistic nature of random walks, provide a promising alternative by utilizing quantum superposition and interference to accelerate the search process. We explore the theoretical framework and potential advantages of employing quantum walks for graph traversal, focusing on scenarios where exponential speedups are theoretically possible. This work aims to demonstrate the potential of quantum computing to tackle computationally demanding graph search tasks that are currently intractable for classical methods. The core concept leverages the ability to simultaneously explore multiple paths within a graph, drastically reducing the search time compared to sequential exploration. We present a foundational understanding of quantum walk implementation and analyze its suitability for various graph search algorithms.
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.