Properties constant-query testable classically in the bidirectional bounded-degree directed graph model admit n^{1/2 - Ω(1)} quantum query testers in the unidirectional model, with an almost-matching lower bound.
An optimal separation between two property testing models for bounded degree directed graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
quant-ph 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Quantum Property Testing for Bounded-Degree Directed Graphs
Properties constant-query testable classically in the bidirectional bounded-degree directed graph model admit n^{1/2 - Ω(1)} quantum query testers in the unidirectional model, with an almost-matching lower bound.