Quantum Property Testing for Bounded-Degree Directed Graphs

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.