{"id":"arxiv/2604.07954","url":"https://arxiv.org/abs/2604.07954","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Quantum Property Testing for Bounded-Degree Directed Graphs","domain":"quant-ph","source":"arxiv","authors":["Pan Peng","Jingyu Wu"],"reviews":0,"subject":"quant-ph","summary":"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 $\\varepsilon$, we prove that every property testable with $O_{\\varepsilon,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-Ω_{\\varepsilon,d}(1)}$ queries. This gives an almost quadratic quantum speedup over the best known generic classical transformation. Our proof…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-09","reactions":{}}