Breaking the quantum barriers for Graph Collision

Introduction

In the graph collision problem, a simple undirected graph $G=(V,E)$ on $n$ vertices is known in advance, and we have query access to an input $x\in\{0,1\}^{V}$. A vertex $v$ is marked if $x_v=1$. The task is to decide whether some edge $uv\in E$ has both endpoints marked. Only queries to $x$ are counted; all computation involving the known graph is free.

Magniez, Santha, and Szegedy introduced graph collision as a subroutine for triangle finding and gave an $O(n^{2/3})$ query quantum algorithm for arbitrary graphs [21 JKLGM16]. Their algorithm uses Ambainis’s quantum walk for element distinctness [3]. Subsequent work improved this bound for graphs with few nonedges [JKLGM16], small independence number [7], or small treewidth [ABI+13]. Other bounds depend on the degrees of vertices in independent sets [15 ABI+13]. Despite these improvements for particular graph families, the $O(n^{2/3})$ bound remained the best known for arbitrary graphs.

A reduction from unstructured search gives a worst case lower bound of $\Omega(\sqrt{n})$ [6], leaving a gap between the known upper and lower bounds. Gavinsky and Ito ask whether graph collision admits a $\widetilde{O}(\sqrt{n})$ query algorithm [15 Section 6], while Ambainis et al. and Balodis and Iraids leave an $O(\sqrt{n})$ bound for arbitrary graphs open [ABI+13, BI16]. Determining the quantum query complexity of graph collision also appears among the open problems in Kothari’s thesis [19 Open Problem 4.3] and in the work of Bun, Kothari, and Thaler [11 Section 7.2]. In the other direction, Cornelissen, Gilani, and Patro report that the $n^{2/3}$ bound is believed by some in the community to be optimal [14]. Gilani, Mande, Patro, and Raja formulate a conjecture for detecting marked cliques whose $k=2$ case asserts that some graph families require $\Omega(n^{2/3})$ queries for graph collision [16 Conjecture 1.5].

We refute this conjecture. We first give a relatively elementary algorithm using $\widetilde{O}(n^{92/139})$ queries in Section 3. Its central idea is to estimate the number of marked neighbors of each vertex and use these estimates to divide the edges into parts that can be tested efficiently. In § 5, we refine the same approach to obtain the following stronger bound.

Our upper bound also applies to functions whose positive inputs can be certified by fixing at most 2 input symbols. In § 9, we reduce any such (partial) Boolean output function on $n$ input symbols from an alphabet of size $q$ to graph collision on $nq$ vertices. By Theorem 1.1, this gives a query bound of $\widetilde{O}((nq)^{11/17})$. This contrasts with the $\Omega(n^{2/3})$ lower bound for element distinctness over large alphabets [5, 2 Ros14], whose positive inputs also have certificates of size 2. More generally, our bound is $o(n^{2/3})$ for $q=O(n^{1/3-\varepsilon})$ and fixed $\varepsilon>0$, showing the importance of the alphabet size in lower bounds based on certificate structures [12].

We also improve the lower bound for graph collision. For a fixed graph this is a total Boolean function with positive certificates of size 2, so the positive adversary method cannot prove a lower bound larger than $O(\sqrt{n})$ [25 SS06]. We overcome this certificate barrier using the general adversary method, which allows negative weights [17]. Our explicit adversary matrix construction is inspired by the recent framework of Belovs [8] and gives the following result.

This rules out an $O(\sqrt{n})$ query algorithm for arbitrary graphs, while leaving open the possibility of a $\widetilde{O}(\sqrt{n})$ query algorithm.

Technical overview

We give an informal overview of the main ideas behind our two algorithms, the reduction for functions with small positive certificates, and the lower bound. Precise statements and proofs appear in Sections 3–6.

An algorithm breaking the $O(n^{2/3})$ barrier

We describe the ideas behind the algorithm of Section 3, which achieves query complexity $\widetilde{O}(n^{92/139})$. The algorithm first preprocesses the graph, then estimates neighborhood counts and uses a threshold to divide the remaining edges into two parts. We begin by explaining why such estimates suffice. The improved algorithm of § 5 builds on the same estimation and thresholding argument.

Let $G=(V,E)$ be the known graph, and let $M=\{v:x_v=1\}$ be its unknown marked set. For any set $S\subseteq V$, write $\ell_u(S)=|N_G(u)\cap S|$, where $N_G(u)$ is the neighborhood of $u$ in the graph $G$. In particular, $\ell_u(M)$ counts the marked neighbors of $u$. Suppose for a moment that we knew all these counts. We could then restrict attention to vertices with positive counts and use Grover search to find a marked vertex among them. This would decide graph collision using $O(\sqrt{n})$ additional queries.

Approximate counts and marked volume. Computing all the counts exactly would require too many queries. We instead construct a set $S$ for which the counts $\ell_u(S)$ approximate $\ell_u(M)$. Our aim is to bound their total squared error

The set $S$ need not recover the marked set. We only use its neighborhood counts. Although approximate counts need not identify which vertices have a marked neighbor, they suffice to divide the edges into two parts that can be tested efficiently.

The relevant quantity for these tests is the marked volume $\operatorname{vol}(G,x)=\sum_{v\in M}\deg_G(v)$, the total degree of marked vertices. Given an upper bound $b$ on this quantity, variable-time search gives a collision test using $\widetilde{O}(\sqrt{n}+\sqrt{b})$ queries.

Choose a threshold $\tau>0$ and let $P=\{u:\ell_u(S)\leq\tau\}$. Consider first the edges inside $P$. The marked volume of $G[P]$ equals $\sum_{u\in P}|N_G(u)\cap M\cap P|$. Each term in this sum is at most $\ell_u(M)$, which also counts marked neighbors outside $P$. The estimated counts are at most $\tau$ on $P$, and Cauchy–Schwarz bounds the sum of the absolute errors by $\sqrt{nr}$. Consequently,

For the edges with at least one endpoint outside $P$, the set $V\setminus P$ contains an endpoint of every such edge and is therefore a vertex cover. The same test applies with a bound on $\operatorname{vol}(G,V\setminus P,x)=\sum_{v\in M\setminus P}\deg_G(v)$, the sum of the degrees of marked vertices in this cover. On an input with no collision, every marked vertex has zero marked neighbors. A marked vertex outside $P$ must therefore contribute more than $\tau^2$ to the squared error, which gives $|M\setminus P|\leq r/\tau^2$. If the maximum degree is at most $d$, the marked volume of this cover is at most $dr/\tau^2$.

Thus the same error bound controls both edge sets: the counts inside $P$ bound their marked volume, while inaccurate counts at marked vertices outside $P$ limit the marked volume of the other cover. We apply the same volume test to both parts, using $P$ as the cover inside and $V\setminus P$ as the cover outside. The volume assumptions are needed for rejection on negative inputs; a test detects a collision in its edge set with high probability even if the stated volume bound fails. We can therefore analyze the estimation error on negative inputs and still detect collisions on positive inputs. Figure 1 illustrates the two marked volume bounds.

Estimating neighborhood counts. The main question is how to obtain the approximate counts with few queries. Take $q$ independent uniform vertices $w_1,\ldots,w_q$, query their input bits, and form the estimates

Each estimate is unbiased, but its sampling error may be large. The true neighborhood counts all come from the same marked set $M$. We use this common structure by choosing a single set $S \subseteq V$ minimizing

The crucial observation is that the true set $M$ is an allowed choice, so the objective value at $S$ is no larger than at $M$. We can use this inequality to compare the neighborhood counts of $S$ and $M$, even though we do not know $M$.

To analyze this comparison, let $c_{vw} = \lvert N_G(v) \cap N_G(w)\rvert$ be the number of common neighbors of $v$ and $w$. Define $z_v = \sum_{u \in N_G(v)} y_u$, which estimates the number of walks of length two from $v$ to marked vertices. A sampled marked vertex $w_i$ contributes $n/q$ to this sum once for each common neighbor of $v$ and $w_i$, so

Counting in two ways gives $\sum_u \ell_u(S)y_u = \sum_{v \in S} z_v$. Expanding the least squares objective leaves $\psi_z(S) = \sum_u \ell_u(S)^2 - 2\sum_{v \in S}z_v$, together with a term $\sum_u y_u^2$ that is independent of $S$. Thus it suffices to compute the common neighbor estimates $z_v$ and minimize $\psi_z$. All these computations use the known graph and the sampled input bits, so they require no further queries. Algorithm 1 gives the procedure.

Comparing $\psi_z(S)$ with $\psi_z(M)$ now bounds the squared estimation error by

This is the useful consequence of choosing all the estimated counts from one set: their total squared error is controlled by the sum of the absolute errors in the sampled common neighbor sums. The improved algorithm uses the same comparison.

The variance of $z_v$ is at most $(n/q)\sum_{w\in M}c_{vw}^{2}$. Applying Cauchy–Schwarz to the comparison above yields

For fixed $v,w$, the quantity $c_{vw}^{2}$ counts ordered pairs of common neighbors, or equivalently closed walks $w,a,v,b,w$ of length four. Only walks starting at marked vertices contribute, allowing us to use the reduction in marked volume obtained by sampling even if many edges remain.

Sampling and edge deletion. The squared common neighbor counts may be too large in an arbitrary graph. We therefore preprocess the graph before estimating the counts. A separate, earlier round of sampling reduces the marked volume; further edge deletions bound the degrees and the number of closed walks starting at marked vertices. Each deletion is accompanied by a search or collision test that detects a collision among the deleted edges with high probability. The algorithm returns as soon as a test finds one.

First, take $\Theta(q\log n)$ uniform vertex samples and query their input bits. Search the union of the neighborhoods of the marked samples for a marked vertex. A successful search gives a collision. Otherwise, delete all edges incident to this union. Any vertex with more than $n/q$ marked neighbors is likely to have one of those neighbors sampled, in which case the deletion isolates it. With high probability every remaining vertex has at most $n/q$ marked neighbors. Summing these counts gives $\operatorname{vol}(G,x)\le n^2/q$. Algorithm 2 gives this sampling procedure.