Quantum property testing in sparse directed graphs
<|reference_start|>Quantum property testing in sparse directed graphs: We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex.   In the classical unidirectional model the problem of testing $k$-star-freeness, and more generally $k$-source-subgraph-freeness, is almost maximally hard for large $k$. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we prove that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the $k$-collision problem that was not studied before.   To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of $3$-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.<|reference_end|>
@article{apers2024quantum,
    title={Quantum property testing in sparse directed graphs},
    author={Simon Apers, Fr'ed'eric Magniez, Sayantan Sen and D'aniel Szab'o},
    journal={arXiv preprint arXiv:2410.05001},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.05001},
    primaryClass={quant-ph cs.DS}
}