Quantum Property Testing for Bounded-Degree Directed Graphs
2026-04-09 • Computational Complexity
Computational ComplexityData Structures and Algorithms
AI summaryⓘ
The authors study how quantum algorithms can test properties of directed graphs where each node has a limited number of incoming and outgoing edges. They show that any property testable efficiently with classical algorithms accessing both incoming and outgoing edges can also be tested quantumly accessing only outgoing edges, using significantly fewer queries than classical methods. This provides nearly a quadratic improvement in query complexity. They also identify a property showing that their results are close to the best possible. Additionally, they demonstrate that certain small patterns in graphs can be counted approximately with even fewer quantum queries in this restricted model.
quantum property testingdirected graphsin-degreeout-degreequery complexitybidirectional modelunidirectional modelsubgraph countingapproximationquantum speedup
Authors
Pan Peng, Jingyu Wu
Abstract
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.