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.
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.
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=P∘PT 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 ε-close to the state Dt∣v⟩/∥Dt∣v⟩∥. The algorithm uses O(∥Dt∣v⟩∥−1tlog(ε∥Dt∣v⟩∥)−1) expected quantum walk steps and O(∥Dt∣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.
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) 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 O(N1/3) queries, showing a polynomial speedup. They also proved that Ω(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) 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.
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 = root P omicron P-T its discriminant matrix (D = P if P is symmetric), we construct a quantum walk algorithm that for any quantum state vertical bar v > and integer t returns a quantum state epsilon-close to the state D-t vertical bar v > /parallel to D-t vertical bar v > parallel to. The algorithm uses O(parallel to D-t vertical bar v > parallel to(-1) root t log(epsilon parallel to D-t vertical bar v > parallel to(-1)) expected quantum walk steps and O(parallel to D-t vertical bar v > parallel to(-1)) expected reflections around vertical bar 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.
We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure.
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 ε, we prove that every property testable with 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) 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, there is a degree bound d=d(ε) and an explicit property Pε for d-bounded-degree digraphs that is ε-testable with 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′(ε)→0 as ε→0.