Having query access to a bounded degree directed graph in the unidirectional model means that querying a vertex v reveals the list of vertices u such that there is a directed edge from v to u. Quantum algorithms can make these queries in superposition. In this model, we consider the problem of property testing k-star-freeness, i.e. the algorithm has to distinguish, with high probability, between (1) the graph having no vertex with at least k incoming edges (k-star); (2) the graph being “far” from this, meaning that one has to delete a constant fraction of the edges to make the graph free from k-stars.
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 (but constant) k, i.e. the query complexity is almost linear in the number of vertices. We give a quantum algorithm to show that this problem has almost quadratic advantage in the quantum setting. Moreover, we prove that this advantage is nearly tight, by proving a quantum lower bound using the method of dual polynomials on an intermediate problem that is a previously unstudied, property testing version of the k-collision problem.
Joint work with Simon Apers, Frédéric Magniez and Sayantan Sen.