Quantum Property Testing for Bounded-Degree Directed Graphs
This work addresses the efficiency of quantum algorithms for graph property testing, providing a significant speedup over classical methods, though it is incremental in the context of quantum computing advancements.
The paper tackles the problem of quantum property testing for bounded-degree directed graphs, showing that properties testable with constant queries in the classical bidirectional model can be tested in the quantum unidirectional model with nearly quadratic speedup, using n^(1/2 - Ω(1)) queries, and proves this transformation is almost tight with an explicit property requiring Ω(n^(1/2 - f'(ε))) quantum queries.
We study quantum property testing for directed graphs with maximum in-degree and out-degree bounded by some universal constant $d$. For a proximity parameter $\varepsilon$, we show that any property that can be tested with $O_{\varepsilon,d}(1)$ queries in the classical bidirectional model, where both incoming and outgoing edges are accessible, can also be tested in the quantum unidirectional model, where only outgoing edges are accessible, using $n^{1/2 - Ω_{\varepsilon,d}(1)}$ queries. This yields an almost quadratic quantum speedup over the best known classical algorithms in the unidirectional model. Moreover, we prove that our transformation is almost tight by giving an explicit property $P_\varepsilon$ that is $\varepsilon$-testable within $O_\varepsilon(1)$ classical queries in the bidirectional model, but requires $\widetildeΩ(n^{1/2-f'(\varepsilon)})$ quantum queries in the unidirectional model, where $f'(\varepsilon)$ is a function that approaches $0$ as $\varepsilon$ approaches $0$. As a byproduct, we show that in the unidirectional model, the number of occurrences of any constant-size subgraph $H$ can be approximated up to additive error $δn$ using $o(\sqrt{n})$ quantum queries.