2026-10-07T14:04:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24398 2025-12-12T14:01:29Z ddc:004 open_access

Quantum Property Testing in Sparse Directed Graphs Apers, Simon Magniez, Frédéric Sen, Sayantan Szabó, Dániel property testing quantum computing bounded-degree directed graphs dual polynomial method collision finding 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 show 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Simon Apers and Frédéric Magniez and Sayantan Sen and Dániel Szabó 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.32 urn:nbn:de:0030-drops-243987 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.32 eng https://creativecommons.org/licenses/by/4.0/legalcode