Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding

In $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖤𝖽𝗀𝖾}$, when searching for a triangle containing a target edge $\{u,v\}$, any edge in the input of the form $\{u^{\prime },v^{\prime }\}$ such that $\{u^{\prime },v^{\prime }\}\cap \{u,v\}=\mathrm{\varnothing }$ can be viewed as irrelevant data that hides the relevant part of the input. This observation motivates a general definition of hiding.

Then $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖤𝖽𝗀𝖾}$ can be seen as ${\mathrm{𝖧𝖨𝖣𝖤}}_m[{\mathrm{ED}}_d]$, where ${\mathrm{ED}}_d$ is the element distinctness function that decides whether an input string of length $d$ has two distinct positions containing the same symbol. We show the following.²²2We use the notation $\tilde{O},\tilde{\mathrm{\Omega }},\tilde{\mathrm{\Theta }}$ to denote big-$O$,$\mathrm{\Omega }$, and $\mathrm{\Theta }$ up to poly-logarithmic factors.

The study of $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖤𝖽𝗀𝖾}$ naturally led us to investigate how $Q(f)$ relates to $Q({\mathrm{𝖧𝖨𝖣𝖤}}_b[f])$ for arbitrary $f:{\mathrm{\Sigma }}^a\to \{0,1\}$. As a first step in this direction, we show $Q({\mathrm{𝖧𝖨𝖣𝖤}}_b[f])=\tilde{\mathrm{\Theta }}(\sqrt{b/a}\cdot Q(f))$ for every symmetric $f:{\{0,1\}}^a\to \{0,1\}$, where “symmetric” refers to “symmetric under permuting the positions of input symbols” throughout this work. The symmetry condition is necessary. For example, let $f:{\{0,1\}}^a\to \{0,1\}$ be the dictator function $f(x)=x_1$. Then $Q(f)=1$, but ${\mathrm{𝖧𝖨𝖣𝖤}}_b[f]$ requires finding the first non-$\ast$ symbol among the $b$ positions. On the subdomain where the last $a-1$ positions are fixed non-$\ast$ symbols and exactly one of the first $b-a+1$ positions is non-$\ast$, computing ${\mathrm{𝖧𝖨𝖣𝖤}}_b[f]$ contains unstructured search on $b-a+1$ items as a subproblem. Hence

which is not $O(\sqrt{b/a}Q(f))$ in general. On the other hand, we conjecture that the result holds for every symmetric $f:{\mathrm{\Sigma }}^a\to \{0,1\}$, even if $\left|\mathrm{\Sigma }\right|>2$. We support this conjecture by showing that its randomized analogue is true in Proposition 3.10 of the full version.

We show in Propositions 4.1 and 4.2 of the full version that the quantum query complexity of $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖵𝖾𝗋𝗍𝖾𝗑}$, when the input is a length-$m$ edge list and the target vertex $u$ has degree $d$, which need not be known in advance, satisfies

where $3\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_d$ is the $3$-distinctness function that decides whether an input string of length $d$ has three distinct positions containing the same symbol. Note that $Q(3\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_d)$ is between $\mathrm{\Omega }(d^{2/3})$ – because it is no easier than ${\mathrm{ED}}_d$ (which could be also called $2\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_d$) – and $O(d^{5/7})$ [11].

When seeking a triangle containing the target vertex $u$, it is helpful to think of the input edge list as consisting of two parts: part $A$ containing edges that are incident to $u$, and part $B$ containing edges that are not incident to $u$. We do not a priori know where parts $A$ and $B$ are but neither part contains irrelevant data – indeed two edges of the triangle must come from $A$ and one edge from $B$ (if it exists). The shuffling of parts $A$ and $B$ contributes to the hardness of $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖵𝖾𝗋𝗍𝖾𝗑}$.

The above discussion and the comparison of the edge list model with the adjacency list and adjacency matrix models naturally led us to investigate how shuffling a function’s input affects its complexity. We formalize and study two concrete versions of this problem.

Having discussed $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖤𝖽𝗀𝖾}$ and $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖵𝖾𝗋𝗍𝖾𝗑}$, we now turn to $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾}$, where we simply ask whether a triangle exists⁴⁴4While $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾}$ is a decision problem, it is essentially equivalent to its search variant via a simple reduction as explained in the preliminaries section. Therefore, we often do not distinguish between the search and decision problems. without placing any constraints. In the edge list model, we find that $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾}$ bridges the $3\text{-}\mathrm{𝖣𝖨𝖲𝖳}$ and $3\text{-}\mathrm{𝖲𝖴𝖬}$ problems since its structure lies between theirs. Recall that in $3\text{-}\mathrm{𝖣𝖨𝖲𝖳}$, the goal is to decide whether the input contains three repetitions of the same symbol. In $3\text{-}\mathrm{𝖲𝖴𝖬}$, the input contains symbols from some abelian group and the goal is to decide if there are three symbols that sum to the zero-element of the group.

Intuitively, $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾}$ should be no easier than $3\text{-}\mathrm{𝖣𝖨𝖲𝖳}$ and no harder than $3\text{-}\mathrm{𝖲𝖴𝖬}$ by considering its “certificate structure” [14]. In $3\text{-}\mathrm{𝖣𝖨𝖲𝖳}$, once we have found one symbol of a $1$-certificate, the next symbol for completing the certificate is determined. In $3\text{-}\mathrm{𝖲𝖴𝖬}$, once we have found one symbol of a $1$-certificate, the next symbol can be arbitrary. In comparison, in $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾}$, once we have found one edge $(i,j)$ of a $1$-certificate, the next edge must be incident to one of $i$ or $j$ so it is neither determined nor arbitrary. In Proposition 5.1 of the full version, we show that this intuition is formally correct by reducing $3\text{-}\mathrm{𝖣𝖨𝖲𝖳}$ to $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾}$ and $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾}$ to $3\text{-}\mathrm{𝖲𝖴𝖬}$.

Our first main result is stated informally below.

We find Theorem 6 interesting for several reasons. Firstly, proving the theorem pushed us to develop new techniques for the recording query framework, which we believe to be of independent interest. The recording query framework was pioneered by Zhandry [43] to prove the security of cryptosystems against quantum adversaries. There is now a growing line of work developing new techniques within the recording query framework, including [32, 21, 23, 9, 35, 33, 19]. Of particular relevance to our work is [23] by Hamoudi and Magniez, which generalized Zhandry’s original framework in order to lower bound the quantum query complexity of finding collision pairs.

This framework is particularly well suited for proving average-case quantum query lower bounds, where the input is sampled from certain types of distributions. The framework can also yield optimal worst-case lower bounds if the worst-case distribution is of a type it can handle – this is the case for triangle finding on graphs of low maximum degree as we will see. Ideally, to prove our lower bound, we would like to consider a hard distribution supported only on graphs with low max-degree. The low max-degree condition makes finding a cycle harder and hence proving the lower bound easier. To see this, consider the contrapositive in the special case of triangle finding. If there were no degree bound, then an edge queried at step $t$ could help the algorithm find a very large number of wedges, i.e., length-$2$ paths. In the extreme case, $\mathrm{\Omega }(t)$ wedges could be found. As each wedge can be completed to a triangle, the more wedges the algorithm finds, the easier triangle finding becomes.

Unfortunately, a product distribution on edge lists cannot be entirely supported on those with low max-degree. In other words, while sampling a graph with high max-degree is a rare event, it is always possible. The main technical contribution of our work is to develop tools to handle such rare events within the recording query framework. We name these tools the Mirroring and Exclusion lemmas. They can be used in conjunction to isolate and bound the contribution to the algorithm’s success probability when rare events occur. These tools extend the recording query framework to treat any non-product distribution that results from conditioning a product distribution on the absence of rare events.

Theorem 6 is also interesting because the lower bound curiously matches the best-known upper bound on the quantum query complexity of $3$-distinctness, which is $Q(3\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_m)\le O(m^{5/7})$, up to logarithmic factors. This upper bound was first proven by Belovs [11] over a decade ago using a ground-breaking learning graph algorithm [10]. There have been no improvements since. On the other hand, the best-known lower bound on $Q(3\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_m)$ is still $\mathrm{\Omega }(m^{2/3})$, which is simply inherited from the element distinctness lower bound of Aaronson and Shi [1] proven over two decades ago. This is despite many attempts at raising the lower bound using the polynomial method [18, 36], adversary method [40, 39], and even recording queries (equivalently, compressed oracle) method [32]. In Table 1, we summarize these results together with those to be discussed later. Note that $3\text{-}\mathrm{𝖢𝖸𝖢𝖫𝖤}$ is equivalent to $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾}$.

We strongly believe that the matching of the lower bound in Theorem 6 and the best-known upper bound on $Q(3\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_m)$ is not a coincidence. This is because the “collision structure” of a uniformly random edge list on $n$ vertices containing $m=\mathrm{\Theta }(n)$ edges resembles that of a candidate worst-case distribution on inputs to $3\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_m$. By collision structure of an edge list, we mean the number of wedges and triangles it contains; by collision structure of an input to $3$-distinctness, we mean the number of $2$-collisions and $3$-collisions it contains, where an $l$-collision refers to a length-$l$ tuple of indices at which the input contains the same symbol. (For more details about the resemblance, see the overview of cycle finding below.) Indeed, the similarities between the collision structures were so striking that we were led to ask whether Belovs’s learning graph algorithm for $3$-distinctness could be adapted to provide a matching upper bound to Theorem 6. As our second main result, we answer this question affirmatively.

Taken together, Theorems 6 and 7 give the first example of a problem for which Belovs’s learning graph algorithm in [11] is provably optimal, up to an $m^{o(1)}$ factor.⁵⁵5Note that the best known quantum query lower bound for $k\text{-}\mathrm{𝖣𝖨𝖲𝖳}$ for every $k\ge 4$ (see [18, 36]) is also polynomially far from the upper bound witnessed by Belovs’s learning graph algorithm. Theorem 6 also suggests that any quantum algorithm that polynomially improves the best-known $O(m^{5/7})$ upper bound on $Q(3\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_m)$ must exploit more than just the collision structure of the problem, which seems improbable to us.

Our results above suggest that triangle finding in a graph of low maximum degree is closely tied to $3$-distinctness. Indeed, they share essentially the same quantum query upper bound and have quite similar quantum algorithms. The $3$-distinctness problem generalizes to a well-studied family of problems known as $k$-distinctness, where $k\ge 3$ is an integer (treated as a constant) and the goal is to decide whether an input list contains $k$ distinct positions with the same symbol. Is there a family of problems generalizing triangle finding in the edge list model that can be similarly tied to $k$-distinctness?

The answer is yes with $k$-cycle finding being the sought for family. To see why, let us return to the concept of collision structure mentioned above. Let $k\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_m$ denote the function computing $k$-distinctness on length-$m$ inputs. A candidate worst-case distribution on inputs to $k\text{-}{\mathrm{𝖣𝖨𝖲𝖳}}_m$ is the uniform distribution over inputs containing exactly one $k$-collision and $\mathrm{\Omega }(m)$ many $(k-1)$-collisions, cf. [3, Section 5] and [13, Section 3]. The intuition is that the many $(k-1)$-collisions present many dead-ends that effectively hide the location of the $k$-collision. In comparison, writing $P(n,k)≔n!/(n-k)!$, a uniformly random length-$m$ edge list on $n=\mathrm{\Theta }(m)$ vertices contains

Since a length-$(k-1)$ path is analogous to a $(k-1)$-collision and a length-$k$ cycle is analogous to a $k$-collision, the collision structure of the uniformly random edge list resembles that of the aforementioned worst-case distribution on inputs to $k$-distinctness. This is also a good point to remark that the uniform distribution over inputs to $k$-distinctness, which is studied in [32], cannot be made to resemble the worst-case distribution (for any setting of input length and alphabet size) because it has the property that the number of $(k-1)$-collisions cannot be too far from the number of $k$-collisions.

Our main result for cycle finding generalizes our results for triangle finding as follows.

The upper bound is exactly the same as the best known upper bound for $k$-distinctness up to an $m^{o(1)}$ factor and is again shown by adapting Belovs’s learning graph algorithm for $k$-distinctness in [11]. We have summarized the state of affairs in Table 1.

The comparison of collision structures above suggests that the hardness of $k$-cycle and $k$-distinctness spring from a common source, which hints at the possibility of lifting our nearly tight lower bound for $k$-cycle to a nearly tight lower bound for $k$-distinctness. In fact, we propose Conjecture 6.18 in the full version, stating that the quantum query complexity of $k$-cycle should not decrease too much under a restriction of the input edges, and prove in Proposition 6.22 of the full version that it enables such lifting.

After the appearance of this work, Belovs [12] established the tight quantum query lower bound for $k$-distinctness, using methods inspired by Zhandry’s recording query technique and independently of the lifting conjecture discussed above.

To lower and upper bound $Q({\mathrm{𝖧𝖨𝖣𝖤}}_m[{\mathrm{ED}}_d])$, our main observation is that the problem “self-reduces” to a more structured version of itself, ${\mathrm{𝖧𝖨𝖣𝖤}}_m^{\prime }[{\mathrm{ED}}_d]$, whose query complexity is easier to characterize. The inputs to ${\mathrm{𝖧𝖨𝖣𝖤}}_m^{\prime }[{\mathrm{ED}}_d]$ are restricted to have the form of $d$ blocks each of length $m/d$,⁶⁶6We may assume $m/d\in \mathbb{Z}$ without loss of generality. We will not make further remarks like this in the technical overview. where each block contains $(m/d-1)$ $\ast$s and exactly one non-$\ast$ symbol. Remarkably, imposing the block structure causes no decrease in hardness.

Observe that ${\mathrm{𝖧𝖨𝖣𝖤}}_m^{\prime }[{\mathrm{ED}}_d]$ can be viewed as the composition of ${\mathrm{ED}}_d$ with the so-called $\mathrm{pSearch}$ function that extracts the unique non-$\ast$ symbol from $m/d$ symbols. The latter function has query complexity $\mathrm{\Theta }(\sqrt{m/d})$ and a composition theorem [17, Theorem 9] yields $Q({\mathrm{𝖧𝖨𝖣𝖤}}_m[{\mathrm{ED}}_d])\ge Q({\mathrm{𝖧𝖨𝖣𝖤}}_m^{\prime }[{\mathrm{ED}}_d])\ge \mathrm{\Omega }(\sqrt{m/d}\cdot d^{2/3})=\mathrm{\Omega }(\sqrt{m}{d}^{1/6})$. To upper bound $Q({\mathrm{𝖧𝖨𝖣𝖤}}_m[{\mathrm{ED}}_d])$, we consider a quantum algorithm that first randomly permutes the positions of a given input string $x$. A standard probability argument – like that used to bound the maximum load in a balls-into-bins experiment – implies that the resulting string $\tilde{x}$ is highly likely to be in a block form similar to inputs of ${\mathrm{𝖧𝖨𝖣𝖤}}_m^{\prime }[{\mathrm{ED}}_d]$, except each block may contain up to $\log (d)$ non-$\ast$ symbols. Since the number of non-$\ast$ symbols in each block is so small, we simply Grover search for all of them on the fly while running the quantum algorithm for ${\mathrm{ED}}_{d\log (d)}$ on $d\log (d)$ symbols. This algorithm has query complexity $\tilde{O}(\sqrt{m}{d}^{1/6})$.

By considering the block structure, we also see $Q({\mathrm{𝖧𝖨𝖣𝖤}}_m[f])=\mathrm{\Omega }(\sqrt{m/d}\cdot Q(f))$ for every $f:{\mathrm{\Sigma }}^d\to \{0,1\}$. We show $Q({\mathrm{𝖧𝖨𝖣𝖤}}_m[f])=\tilde{O}(\sqrt{m/d}\cdot Q(f))$ for symmetric $f:{\{0,1\}}^d\to \{0,1\}$ using the characterization of the optimal quantum query algorithm for such functions in [8]. We show $R({\mathrm{𝖧𝖨𝖣𝖤}}_m[f])=O((m/d)\cdot R(f))$ for symmetric $f:{\mathrm{\Sigma }}^d\to \{0,1\}$, where $R(\cdot )$ denotes the worst-case (bounded-error) randomized query complexity, using the characterization of the optimal randomized query algorithm for such functions in [7].

To obtain $Q(\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖵𝖾𝗋𝗍𝖾𝗑})\le O(\sqrt{m}{d}^{1/4})$ in Proposition 4.1 of the full version, we use a quantum walk algorithm that walks on the Hamming graph with vertices labeled by $r≔\lceil d^{3/4}\rceil$ positions from part $A$ (the part containing edges incident to the target vertex) of the input. Since we do not a-priori know where part $A$ is, we perform amplitude amplification in both the setup and update steps of the quantum walk to keep the walk on part $A$. Importantly, this uses the fact that the underlying random walk is uniformly random on the Hamming graph. To lower bound $Q(\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖵𝖾𝗋𝗍𝖾𝗑})\ge \mathrm{\Omega }(\sqrt{m/d}\cdot Q(3\text{-}\mathrm{𝖣𝖨𝖲𝖳}))$, we give a reduction from ${\mathrm{𝖧𝖨𝖣𝖤}}_m[3\text{-}\mathrm{𝖣𝖨𝖲𝖳}]$ to $\mathrm{𝖳𝗋𝗂𝖺𝗇𝗀𝗅𝖾𝖵𝖾𝗋𝗍𝖾𝗑}$ in Proposition 4.2 of the full version.

We obtain an exponential separation between $Q(f)$ and $Q(\mathrm{𝖲𝖧𝖴𝖥𝖥𝖫𝖤}[f])$ when $f$ is defined by the graph property $𝒫$ from [16, Section 6] in the adjacency list model as follows. [16] showed that computing $f$ witnesses an exponential separation between randomized and quantum query complexities. But the quantum query complexity of computing $\mathrm{𝖲𝖧𝖴𝖥𝖥𝖫𝖤}[f]$ is polynomially related to its randomized query complexity since the problem is symmetric [20].

If $f$ is defined by a graph property in the adjacency matrix model, the above argument cannot work since [16] showed that the quantum query complexity of computing $f$ is polynomially related to its randomized query complexity. Nonetheless, we found that an unbounded separation between $Q(f)$ and $Q(\mathrm{𝖲𝖧𝖴𝖥𝖥𝖫𝖤}[f])$ can be witnessed by the following Majority-of-Majority function on a restricted partial domain, that we name $\mathrm{\Sigma }\mathrm{MAJ}$:⁷⁷7We chose this name because $\mathrm{\Sigma }$ resembles a rotated M and $\mathrm{\Sigma }{\mathrm{MAJ}}_n$ is (a restriction of) the composition of two ${\mathrm{MAJ}}_n$s.

In other words, inputs in $D_0$ have at least $2n/3$ “dense” rows, i.e., a substring of the form $x_{i,1}{x}_{i,2}\mathrm{\dots }{x}_{i,n}$ for some $i\in [n]$, with at least $2n/3$ ones; and at most $n/3$ “sparse” rows with at most $n/3$ ones. In contrast, inputs in $D_1$ have at most $n/3$ dense rows and at least $2n/3$ sparse rows.

It is not hard to see that $R(\mathrm{\Sigma }{\mathrm{MAJ}}_n)=O(1)$ as follows. For a given row, we can test whether it is dense or sparse using $O(1)$ queries. Since the fractions of dense blocks for inputs in $D_0$ and $D_1$ differ by a constant, we can distinguish between these cases using $O(1)$ queries. Therefore $Q(\mathrm{\Sigma }{\mathrm{MAJ}}_n)\le R(\mathrm{\Sigma }{\mathrm{MAJ}}_n)=O(1)$.

In contrast, computing $\mathrm{𝖲𝖧𝖴𝖥𝖥𝖫𝖤}[\mathrm{\Sigma }{\mathrm{MAJ}}_n]$ seems at least as hard as finding two distinct input symbols $(x_{i_1,j_1},(i_1,j_1))$ and $(x_{i_2,j_2},(i_2,j_2))$ that came from the same row pre-shuffling, i.e., $i_1=i_2$ but $j_1\ne j_2$, which is a collision-type problem. Formally, we prove $R(\mathrm{𝖲𝖧𝖴𝖥𝖥𝖫𝖤}[\mathrm{\Sigma }{\mathrm{MAJ}}_n])=\mathrm{\Omega }(\sqrt{n})$ in Theorem 4.6 of the full version by showing that two particular distributions, one supported on the set $D_0$ and another on $D_1$, are hard to distinguish by any few-query randomized algorithm using a hands-on total variation distance argument. Therefore, $Q(\mathrm{𝖲𝖧𝖴𝖥𝖥𝖫𝖤}[\mathrm{\Sigma }{\mathrm{MAJ}}_n])=\mathrm{\Omega }(R{(\mathrm{𝖲𝖧𝖴𝖥𝖥𝖫𝖤}[\mathrm{\Sigma }{\mathrm{MAJ}}_n])}^{1/3})=\mathrm{\Omega }(n^{1/6})$, where the first equality uses [20], which applies since $\mathrm{𝖲𝖧𝖴𝖥𝖥𝖫𝖤}[\mathrm{\Sigma }{\mathrm{MAJ}}_n]$ is symmetric.

We prove our lower bound on triangle finding (Theorem 6) in Zhandry’s recording query framework [43]. Following the framework, we define a “progress quantity” that tracks the progress the algorithm has made in “recording” the searched-for object in its internal memory. The progress quantity can be roughly thought of as the square root of the probability with which the quantum algorithm can find the searched-for object, where the probability is over randomness in both the input distribution and the algorithm. The progress quantity depends on the number of queries the quantum algorithm makes. If this quantity is small after the last query, then the algorithm cannot find what it is searching for with high probability.

Our proof has two steps:⁸⁸8The arguments here are better understood by considering $n$, which represents the number of vertices in the graph. But recall that Theorem 6 concerns the regime $m=\mathrm{\Theta }(n)$, so all results here can also be expressed in terms of $m$.

1. 1.

   we first show that the progress in recording much more than $r^{\ast }(t)≔t^{3/2}{\log }^2(n)/\sqrt{n}$ wedges in $t$ queries is negligible;

2. 2.

   then we show that, given we record $O(r^{\ast }(t))$ wedges in $t$ queries, the progress of recording a triangle at the $(t+1)$-th query increases by at most $O(\sqrt{r^{\ast }(t)}/n)$, which corresponds to the square root of the probability that a random edge completes one of the $r^{\ast }(t)$ recorded wedges to a triangle.

Therefore, at the $T$-th query, the progress of recording a triangle is ${\sum }_{t=0}^T\sqrt{r^{\ast }(t)}/n$, which equals $O(T^{7/4}\log (n)/n^{5/4})$, and is $o(1)$ unless $T\ge \mathrm{\Omega }(n^{5/7}/{\log }^{4/7}(n))$. The ability to perform this type of step-by-step analysis is a known strength of the recording query framework.⁹⁹9To quantum query lower bound experts: the standard quantum adversary method [2, 24] is not well-suited to performing this type of step-by-step analysis because it gives only weak lower bounds for small success probabilities, and step (ii) needs the progress in step (i) to be inverse-polynomially small to work. If we were forced to redo this analysis using the adversary method, we would have to switch to its multiplicative version, see, e.g., [5, 31, 27]. For example, it was exploited to great effect by Liu and Zhandry [32] in proving their tight lower bound on the quantum query complexity of average-case $k$-distinctness.

What is new to our work is how we perform step (i) above. As previously discussed, the issue is that a newly queried edge could contribute to more than one wedge. Let us now see how this issue manifests itself at a technical level. We begin by following the recording queries framework and define a progress quantity ${\mathrm{\Lambda }}_{t,r}\in [0,1]$ for integer $t,r$ with $t\ge 0$ where ${\mathrm{\Lambda }}_{t,r}^2$ represents the probability a quantum query algorithm has recorded at least $r$ wedges immediately after the $t$-th query. Directly using existing techniques in the framework gives the following recurrence for ${\mathrm{\Lambda }}_{t,r}$:

where the factor $O(\sqrt{t/n})=O(\sqrt{tn/n^2})$ arises as the square root of the probability that a randomly chosen edge is incident to one of the at most $t-1$ edges that can be recorded after the $(t-1)$-th query; the subscript $r-t+1=r-(t-1)$ arises from the possibility of the new edge recorded at the $t$-th query contributing $t-1$ additional wedges. However, solving Equation 11 leads to a trivial lower bound for triangle finding that does not even beat the $\mathrm{\Omega }(m^{2/3})$ lower bound it inherits from element distinctness.

The main problem with Equation 11 is the subscript $r-t+1$ on the second term on the right-hand side. However, the event it corresponds to seems unlikely to happen when the input is a sparse graph and $t$ is large: if the new edge contributes $t-1$ additional wedges, it must be incident to a degree-$\mathrm{\Omega }(t)$ vertex recorded by the quantum query algorithm. Now, our input is a random sparse graph whose maximum degree is at most $O(\log (n)/\log \log (n))\le O(\log (n))$ with high probability, independent of $t$. Does this property also hold for the internal memory of the quantum query algorithm doing the recording? Our first technical contribution, the Mirroring Lemma (Lemma 5.18 of the full version), answers this question affirmatively. Informally, it says that if a structural event is rare under the initial input distribution, then the corresponding event remains rare in the recording register of any quantum query algorithm, up to a controllable leakage term coming from the change of basis between the standard and recording-query pictures.

For each vertex $v$, we apply the Mirroring Lemma by taking the special symbols to be those that are incident to $v$. Since a sparse graph specified by a uniformly random edge list contains a vertex of degree $\mathrm{\Omega }(\log (n))$ with negligible probability, the lemma implies that any quantum algorithm also has negligible probability of recording a vertex with degree $\mathrm{\Omega }({\log }^2(n))$. Thus, even if the algorithm makes $t$ queries with $t$ large, the number of new wedges created by one additional recorded edge can still be bounded by $O({\log }^2(n))$, which is much better than the trivial bound of $t$. Directly using this technique allows us to improve Equation 11 to

where $ϵ>0$ is a small number corresponding to the tail probability of the input graph having a vertex of degree $\mathrm{\Omega }(\log (n))$.

Unfortunately, Equation 12 still does not yield the desired result: to see this, note that the solution to a similar recurrence $A_{t,r}=A_{t-1,r}+p{A}_{t-1,r-1}+ϵ$ (with $p,ϵ\in [0,1]$ and boundary conditions $A_{0,0}=1$ and $A_{0,r}=0$ for all $r>0$) is $A_{t,r}=\left(\genfrac{}{}{0pt}{}{t}{r}\right)p^r+ϵ(1+(1+p)+\mathrm{\cdots }+{(1+p)}^{t-1})$. Even for an exponentially small $ϵ$, the term $ϵ{(1+p)}^{t-1}$ blows up for large $t$. Our second technical contribution, the Exclusion Lemma (Lemma 5.14 of the full version), allows us to overcome this problem. To employ this lemma, we introduce a new progress quantity called ${\mathrm{\Lambda }}_{t,r}^{\prime }$ that is defined like ${\mathrm{\Lambda }}_{t,r}$ except we additionally require the quantum query algorithm to not have recorded a degree-$\mathrm{\Omega }(\log (n))$ vertex at any point before the $t$-th query. By definition, ${\mathrm{\Lambda }}_{t,r}^{\prime }$ satisfies recurrence Equation 12 with $ϵ$ set to $0$, that is,

The Exclusion Lemma allows us to upper bound ${\mathrm{\Lambda }}_{t,r}$ by ${\mathrm{\Lambda }}_{t,r}^{\prime }+O(tϵ)$, where the second term no longer blows up for large $t$ and is easy to make negligible. Therefore, solving Equation 13 first for ${\mathrm{\Lambda }}_{t,r}^{\prime }$ and then using ${\mathrm{\Lambda }}_{t,r}\le {\mathrm{\Lambda }}_{t,r}^{\prime }+O(tϵ)$ yields the claimed result of step (i).

We prove our upper bound on triangle finding (Theorem 6) by adapting Belovs’s learning graph algorithm for $3$-distinctness from [11]. Formally, a “learning graph algorithm” is a directed acyclic graph that encapsulates a solution to a semi-definite program that characterizes quantum query complexity [37, 38]. Our main adaptation of Belovs’s algorithm pertains to its handling of so-called faults in [11, Section 6].

The notion of a fault is easier to explain in Jeffery and Zur’s interpretation of Belovs’s algorithm as a quantum walk [26].¹⁰¹⁰10[26] goes much beyond merely interpreting Belovs’s algorithm. However, in this paper, we will only use [26] to aid our explanation of Belovs’s algorithm. The following explanation is based on [26, Section 1.3]. The quantum walk first creates a uniform superposition over subsets $R_1$ of indices of some size $r_1$, and queries all $r_1$ indices. Then, for each $R_1$ in the superposition, the algorithm creates a uniform superposition over all subsets $R_2$ (disjoint from $R_1$) of indices of some size $r_2$. But rather than querying every index in $R_2$, the algorithm only queries those $i_2\in R_2$ that have a match in $R_1$, i.e., $x_{i_2}=x_{i_1}$ for some $i_1\in R_1$, where $x$ is the input. This significantly reduces query complexity by exploiting the structure of $3$-distinctness: any two unequal symbols could not be part of a $1$-certificate. Unfortunately, it also leads to the aforementioned faults. The issue is that when performing the update step of the quantum walk by adding a new index $j_1$ to $R_1$, we cannot afford the queries needed to update a corresponding $R_2$ by searching for a $j_2\in R_2$ such that $x_{j_2}=x_{j_1}$ because $R_2$ was not fully queried. But if we do not search and there does exist $j_2\in R_2$ with $x_{j_2}=x_{j_1}$, then the set of queried indices in $R_2$ becomes incorrect, introducing a fault.

In our setting, there can be more faults because “matching” in our case naturally needs to be redefined to mean: $i_2\in R_2$ matches with $i_1\in R_1$ if and only if $x_{i_2}$ (which is an edge in our case) is incident to $x_{i_1}$. In particular, $i_2$ could match $i_1$ even if $x_{i_2}\ne x_{i_1}$. However, the number of faults introduced is bounded above by using the maximum degree $d$ of the input, which for a random sparse graph satisfies $d\le O(\log (n)/\log \log (n))$. Then we adapt the “error-correcting” technique of [11] to correct $O(d)$ faults by paying a multiplicative factor of $2^{O(d)}=n^{o(1)}$ on the quantum query complexity, which leads to the theorem. Along the way, we construct a learning graph algorithm that may be easier to understand than that in [11]; for example, our algorithm genuinely corresponds to a graph, unlike that in [11].

We prove our lower and upper bounds on $k$-cycle finding by generalizing our proofs in the $k=3$ (triangle) case.¹¹¹¹11While these generalized proofs fully generalize those in the case $k=3$, we encourage the interested reader to read the proofs in the $k=3$ case first as they contain most of the key ideas and should make the generalized proofs easier to follow. Here is a sketch of how this works.

To prove the lower bound, we consider a uniformly random length-$m$ edge list on $n$ vertices such that $n=\mathrm{\Theta }(m)$. Our proof proceeds in $(k-1)$ steps. We use the Mirroring Lemma in the first step for the same reason it was used in the triangle case. On the other hand, the role of the Exclusion Lemma is expanded “by a factor of order $k$” as it serves to “glue” together the $(k-1)$ steps. For $i\in \{1,\mathrm{\dots },k-2\}$, we show in the $i$-th step that it is hard for a $t$-query algorithm to record much more than $r_{i+1}(t)$ length-$(i+1)$ paths without having recorded at least $r_j(t)$ length-$j$ paths for some $1\le j\le i$. Here, the $r_l(t)$s are certain positive integers essentially defined by the relation $r_l(t)=t\sqrt{r_{l-1}(t)/n}$ and boundary condition $r_1(t)=t+1$. The term $\sqrt{r_{l-1}(t)/n}$ corresponds to the square root of the probability that a single uniformly random edge $e$ extends one of the $r_{l-1}(t)$ length-$(l-1)$ paths to a length-$l$ path. (Note that the precise expression of this probability is $r_{l-1}(t)\cdot 2(n-l)/(n(n-1)/2)$, which is $\mathrm{\Theta }(r_{l-1}(t)/n)$.) One technical challenge here (that was not present in the triangle case) is the need to account for the scenario of edge $e$ creating a length-$l$ path by joining together a length-$a$ path with a length-$b$ path such that $a,b$ are non-negative integers and $a+b+1=l$ but neither $a$ nor $b$ equals $0$. However, we find that this scenario can be neglected as its effect is dominated by that of the extension scenario, i.e., the scenario where $a$ or $b$ is $0$. After concluding the first $(k-2)$ steps, we show in the $(k-1)$-th step that it is hard for a $t$-query algorithm to record a $k$-cycle without having recorded at least $r_{k-1}(t)$ length-$(k-1)$ paths. Finally, we use the Exclusion Lemma $(k-1)$ times to glue together the results of all steps and show that it is hard for a few-query algorithm to record a $k$-cycle.

On the upper bound side, our algorithm for $k$-cycle remains an adaptation of Belovs’s algorithm for $k$-distinctness. The adaptation again pertains to the handling of faults due to a natural redefinition of what matching means. By the degree bound, the maximum number of faults that can occur is fewer than $2d$ where $d$ is the maximum degree of the input edge list. We again adapt Belovs’s error correcting technique to handle them by paying a multiplicative factor of $2^{O(dk)}$, which is $m^{o(1)}$ when $d\le O(\log (m)/\log \log (m))$.

Interestingly, the exact same $r_l(t)$s mentioned in the lower bound overview play a “dual” role in both Belovs’s learning graph algorithm for $k$-distinctness and our adaptation of it to $k$-cycle: given $t$ queries, the learning graph can be thought of as “recording” $r_j(t)$ number of $j$-collisions (in the case of $k$-distinctness) or length-$j$ paths (in the case of $k$-cycle) at the $j$-th step, or “stage” as Belovs calls it. Therefore, our lower bound can be interpreted as saying that the learning graph algorithm for $k$-cycle is tight at every stage.