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:1907.02369 · Quantum

Expansion Testing using Quantum Fast-Forwarding and Seed Sets

Simon Apers

Published Sep 16, 2020• 3 citations
arXivHTMLPDF

Abstract

Expansion testing aims to decide whether an n -node graph has expansion at least Φ , or is far from any such graph. We propose a quantum expansion tester with complexity O~(n1/3Φ−1) . This accelerates the O~(n1/2Φ−2) classical tester by Goldreich and Ron [Algorithmica '02] \cite{goldreich2002property}, and combines the O~(n1/3Φ−2) and O~(n1/2Φ−1) quantum speedups by Ambainis, Childs and Liu [RANDOM '11] and Apers and Sarlette [QIC '19] \cite{apers2019quantum}, respectively. The latter approach builds on a quantum fast-forwarding scheme, which we improve upon by initially growing a seed set in the graph. To grow this seed set we use a so-called evolving set process from the graph clustering literature, which allows to grow an appropriately local seed set.

DOI
10.22331/q-2020-09-16-323

Related papers

Quantum fast-forwarding: Markov chains and graph property testing

Simon Apers, Alain Scarlet

We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with P the Markov chain transition matrix and D = \sqrt{P\circ P^T} its discriminant matrix (D=P if P is symmetric), we construct a quantum walk algorithm that for any quantum state |v> and integer t returns a quantum state \epsilon-close to the state D^t|v>/\|D^t|v>. The algorithm uses O(|D^t|v>|^{-1}\sqrt{t\log(\epsilon\|D^t|v>})^{-1}}) expected quantum walk steps and O(\|D^t|v>|^{-1}) expected reflections around |v>. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.

arXiv:1804.02321•Quantum Information and Computation•Mar 1, 2019•65 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

Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model

Chandrima Kayal, Sayantan Sen, Dániel Szabó

In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that $\widetildeΘ(\sqrt{N})$ queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where $N$ denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform $\widetilde{O}(N^{1/3})$ queries, showing a polynomial speedup. They also proved that $\widetildeΩ(N^{1/4})$ queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight $\widetildeΩ(N^{1/3})$ quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.

quant-pharXiv:2610.01752•Oct 2, 2026•0 citations

(Quantum) Complexity of Testing Signed Graph Clusterability

Chen, Kuo-Chin, Simon Apers, Min-Hsiu Hsieh

This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity $\tilde{O}(N^{1/3})$ for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [arXiv:2102.07587]. Second, we prove an $\tildeΩ(\sqrt{N})$ classical query lower bound for testing clusterability, which nearly matches the upper bound from [arXiv:2102.07587]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.

arXiv:2311.10480•Leibniz international proceedings in informatics•Nov 17, 2023•3 citations

Quantum Property Testing for Bounded-Degree Directed Graphs

Pan Peng, Jingyu Wu

We study quantum property testing of directed graphs whose maximum in-degree and out-degree are bounded by a fixed constant $d$. For a proximity parameter $\varepsilon$, we prove that every property testable with $O_{\varepsilon,d}(1)$ quantum queries in the bidirectional model, where both incoming and outgoing neighbors are accessible, can also be tested in the quantum unidirectional model, where only outgoing neighbors are accessible, using $n^{1/2-Ω_{\varepsilon,d}(1)}$ queries. This gives an almost quadratic quantum speedup over the best known generic classical transformation. Our proof has two main ingredients. First, we show that, in the bidirectional model for bounded-degree digraphs, the class of properties testable with constantly many classical queries coincides with the class testable with constantly many quantum queries. Second, we give a transformation from classical bidirectional testers to quantum unidirectional testers by designing a quantum unidirectional algorithm for estimating the frequency vector of constant-radius rooted discs. The algorithm combines quantum counting and Grover search with a correction procedure that removes false local appearances of smaller disc types inside larger neighborhoods. We further show that this transformation is essentially tight. For every sufficiently small fixed $\varepsilon>0$, there is a degree bound $d=d(\varepsilon)$ and an explicit property $P_\varepsilon$ for $d$-bounded-degree digraphs that is $\varepsilon$-testable with $O_\varepsilon(1)$ classical, and hence quantum, bidirectional queries, but requires $ \widetildeΩ_\varepsilon \left(n^{1/2-f'(\varepsilon)}\right) $ quantum queries in the unidirectional model, where $f'(\varepsilon)\to 0$ as $\varepsilon\to 0$.

quant-pharXiv:2604.07954•Apr 10, 2026•2 citations

Quantum walks : speed limits on mixing and fast-forwarding classical walks

Simon Apers

The theme that underlies this thesis is the mutualist relation between classical walks and quantum walks on graphs, the latter being a promising algorithmic component of future quantum computers.We study both sides of this coin.On the one side we prove how classical walks can simulate quantum walks.This allows the use of folklore bounds on the behavior of classical walks to study speed limits on quantum walks, a question which had long evaded progress.On the other side, we prove how quantum walks can be used to speed up the behavior of a large class of classical walks.This leads to a new quantum algorithm which we call quantum walk fast-forwarding.We show that this algorithm allows to naturally speed up classical walk algorithms for search and property testing on graphs.The work is theoretical and mathematical, and supposed to be relevant for quantum computers that should some day exist.I feel proud of this work, and am indebted to many people.Foremost I must thank my supervisor Alain Sarlette, you have been the best supervisor I could wish for, if only for learning me that no-go proofs are traffic diversions rather than dead ends.

•Jan 1, 2019•1 citation
Expansion testing aims to decide whether an n -node graph has expansion at least Φ , or is far from any such graph. We propose a quantum expansion tester with complexity O~(n1/3Φ−1) . This accelerates the O~(n1/2Φ−2) classical tester by Goldreich and Ron [Algorithmica '02] \cite{goldreich2002property}, and combines the O~(n1/3Φ−2) and O~(n1/2Φ−1) quantum speedups by Ambainis, Childs and Liu [RANDOM '11] and Apers and Sarlette [QIC '19] \cite{apers2019quantum}, respectively. The latter approach builds on a quantum fast-forwarding scheme, which we improve upon by initially growing a seed set in the graph. To grow this seed set we use a so-called evolving set process from the graph clustering literature, which allows to grow an appropriately local seed set.
We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with P the Markov chain transition matrix and D = \sqrt{P\circ P^T} its discriminant matrix (D=P if P is symmetric), we construct a quantum walk algorithm that for any quantum state |v> and integer t returns a quantum state \epsilon-close to the state D^t|v>/\|D^t|v>. The algorithm uses O(|D^t|v>|^{-1}\sqrt{t\log(\epsilon\|D^t|v>})^{-1}}) expected quantum walk steps and O(\|D^t|v>|^{-1}) expected reflections around |v>. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.
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.
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that Θ~(N)\widetildeΘ(\sqrt{N})Θ(N​) queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where NNN denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform O~(N1/3)\widetilde{O}(N^{1/3})O(N1/3) queries, showing a polynomial speedup. They also proved that Ω~(N1/4)\widetildeΩ(N^{1/4})Ω(N1/4) queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight Ω~(N1/3)\widetildeΩ(N^{1/3})Ω(N1/3) quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.
This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity O~(N1/3)\tilde{O}(N^{1/3})O~(N1/3) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [arXiv:2102.07587]. Second, we prove an Ω~(N)\tildeΩ(\sqrt{N})Ω~(N​) classical query lower bound for testing clusterability, which nearly matches the upper bound from [arXiv:2102.07587]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.
We study quantum property testing of directed graphs whose maximum in-degree and out-degree are bounded by a fixed constant ddd. For a proximity parameter ε\varepsilonε, we prove that every property testable with Oε,d(1)O_{\varepsilon,d}(1)Oε,d​(1) quantum queries in the bidirectional model, where both incoming and outgoing neighbors are accessible, can also be tested in the quantum unidirectional model, where only outgoing neighbors are accessible, using n1/2−Ωε,d(1)n^{1/2-Ω_{\varepsilon,d}(1)}n1/2−Ωε,d​(1) queries. This gives an almost quadratic quantum speedup over the best known generic classical transformation. Our proof has two main ingredients. First, we show that, in the bidirectional model for bounded-degree digraphs, the class of properties testable with constantly many classical queries coincides with the class testable with constantly many quantum queries. Second, we give a transformation from classical bidirectional testers to quantum unidirectional testers by designing a quantum unidirectional algorithm for estimating the frequency vector of constant-radius rooted discs. The algorithm combines quantum counting and Grover search with a correction procedure that removes false local appearances of smaller disc types inside larger neighborhoods. We further show that this transformation is essentially tight. For every sufficiently small fixed ε>0\varepsilon>0ε>0, there is a degree bound d=d(ε)d=d(\varepsilon)d=d(ε) and an explicit property PεP_\varepsilonPε​ for ddd-bounded-degree digraphs that is ε\varepsilonε-testable with Oε(1)O_\varepsilon(1)Oε​(1) classical, and hence quantum, bidirectional queries, but requires $ \widetildeΩ_\varepsilon \left(n^{1/2-f'(\varepsilon)}\right) $ quantum queries in the unidirectional model, where f′(ε)→0f'(\varepsilon)\to 0f′(ε)→0 as ε→0\varepsilon\to 0ε→0.
The theme that underlies this thesis is the mutualist relation between classical walks and quantum walks on graphs, the latter being a promising algorithmic component of future quantum computers.We study both sides of this coin.On the one side we prove how classical walks can simulate quantum walks.This allows the use of folklore bounds on the behavior of classical walks to study speed limits on quantum walks, a question which had long evaded progress.On the other side, we prove how quantum walks can be used to speed up the behavior of a large class of classical walks.This leads to a new quantum algorithm which we call quantum walk fast-forwarding.We show that this algorithm allows to naturally speed up classical walk algorithms for search and property testing on graphs.The work is theoretical and mathematical, and supposed to be relevant for quantum computers that should some day exist.I feel proud of this work, and am indebted to many people.Foremost I must thank my supervisor Alain Sarlette, you have been the best supervisor I could wish for, if only for learning me that no-go proofs are traffic diversions rather than dead ends.