This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity $\tilde{O}(N^{1/3})$ for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [arXiv:2102.07587]. Second, we prove an $\tildeΩ(\sqrt{N})$ classical query lower bound for testing clusterability, which nearly matches the upper bound from [arXiv:2102.07587]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.
This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity O~(N1/3) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [arXiv:2102.07587]. Second, we prove an Ω~(N) classical query lower bound for testing clusterability, which nearly matches the upper bound from [arXiv:2102.07587]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that Θ(N) queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where N denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform O(N1/3) queries, showing a polynomial speedup. They also proved that Ω(N1/4) queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight Ω(N1/3) quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.
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 ε, we prove that every property testable with Oε,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 n1/2−Ωε,d(1) queries. This gives an almost quadratic quantum speedup over the best known generic classical transformation.
Our proof has two main ingredients. First, we show that, in the bidirectional model for bounded-degree digraphs, the class of properties testable with constantly many classical queries coincides with the class testable with constantly many quantum queries. Second, we give a transformation from classical bidirectional testers to quantum unidirectional testers by designing a quantum unidirectional algorithm for estimating the frequency vector of constant-radius rooted discs. The algorithm combines quantum counting and Grover search with a correction procedure that removes false local appearances of smaller disc types inside larger neighborhoods.
We further show that this transformation is essentially tight. For every sufficiently small fixed ε>0, there is a degree bound d=d(ε) and an explicit property Pε for d-bounded-degree digraphs that is ε-testable with Oε(1) classical, and hence quantum, bidirectional queries, but requires $ \widetildeΩ_\varepsilon \left(n^{1/2-f'(\varepsilon)}\right) $ quantum queries in the unidirectional model, where f′(ε)→0 as ε→0.
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.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2) bound for finding a maximum-out-degree vertex in an n-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an n-vertex undirected graph requires Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)-Cut, which asks for the largest cut with one side of size k. For every constant k≥1, we give an O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)-Cut involving k-Graph Collision, which asks whether the marked vertices of a known graph contain a k-clique. For k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for k-Graph Collision, the reduction yields a lower bound matching our upper bound above.
The edge connectivity of a simple graph is the least number of edges whose removal disconnects the graph. We study the quantum query complexity of computing the edge connectivity of a simple graph with n vertices and m edges in both the adjacency matrix and adjacency array models. For classical randomized algorithms, Ω(n2) and Ω(m) lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases. In contrast, we show upper bounds of O~(n3/2) and O~(mn) on the quantum query complexity of computing edge connectivity in the adjacency matrix and adjacency array models, respectively. Our upper bound is tight up to logarithmic factors for the adjacency matrix model, while for the adjacency array model the best quantum query lower bound we know is Ω(n). Our upper bounds follow by combining a lemma on the structure of near-minimum cuts due to Rubinstein, Schramm and Weinberg (ITCS 2018) with a quantum sparsification algorithm by Apers and de Wolf (FOCS 2020).
For a weighted graph, instead of edge connectivity the relevant notion is the weight of a minimum cut, i.e. the minimum total weight of a set of edges whose removal disconnects the graph. For weighted graphs we show that in the worst case Ω(n2) queries can be needed to compute the weight of a minimum cut by a quantum algorithm in both the adjacency matrix and adjacency array models, thus no quantum speedup is possible in this case.
The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on n vertices drawn from the Erdős--Rényi distribution G(n,1/2) are considered approximately isomorphic if they can be made isomorphic by at most k edge edits.
We present a quantum algorithm based on MNRS quantum walk search over the product graph Γ(G,H) of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity O(n3/2logn/ε), where ε parameterizes the approximation threshold. We complement this with an Ω(n2) classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model.
We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.