Quantum Property Testing for Bounded-Degree Directed Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.07954
curl -X POST /api/v1/records/arxiv/2604.07954/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.07954/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'