Quantum Property Testing for Bounded-Degree Directed Graphs

Abstract

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 $\epsilon$, we prove that every property testable with $O_{\epsilon ,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-{\Omega }_{\epsilon ,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 $\epsilon >0$, there is a degree bound $d=d(\epsilon )$ and an explicit property $P_{\epsilon }$ for $d$-bounded-degree digraphs that is $\epsilon$-testable with $O_{\epsilon }(1)$ classical, and hence quantum, bidirectional queries, but requires ${\tilde{\Omega }}_{\epsilon }\left(n^{1/2-f^{\prime }(\epsilon )}\right)$ quantum queries in the unidirectional model, where $f^{\prime }(\epsilon )\to 0$ as $\epsilon \to 0$.

SODA 2027