1 Introduction↩︎

The study of graph problems forms a cornerstone of research in theoretical computer science. These problems have been studied when the input data structure is the adjacency matrix or adjacency list of the graph. In the adjacency matrix model of an \(n\)-vertex undirected simple graph, one is given the presence or absence status of every one of the \(\binom{n}{2}\) edges in an \(n\times n\) binary matrix. In the adjacency list model, the input is given as \(n\) lists of neighbors, one for each of the \(n\) vertices. Both models build structural cues into the input: an adjacency matrix assigns each vertex a given row and column, while an adjacency list uses vertices to order edges. These cues allow for fast computation but are arguably not intrinsic to the underlying graph.

In this work, we study graph problems in the edge list model, a minimalist model where the graph is given as an unordered multiset of edges. When computing on edge lists, algorithms must build the graph’s structure for themselves and not rely on any input cues. Thus, studying computation on edge lists offers a new window into the relationship between a graph problem’s structure and complexity.

We study the edge list model in the context of quantum query complexity. In quantum query complexity, we assume access to a quantum computer and characterize the complexity of a problem by the number of times the computer queries an input edge list.

Quantum algorithms on edge lists has previously been studied in the area of streaming algorithms. For example, [4] showed that triangle counting can be solved by a quantum streaming algorithm using less space than any classical rival. However, the quantum computational model employed differs significantly from the quantum query model that we study. In the former case, the edge list is still queried classically — only the memory is quantum — whereas we assume the edge list can be queried in quantum superposition. As we will see in this work, this change of model leads to new and interesting questions.

Inspired by the fact that the triangle problem in the adjacency matrix model has driven innovations in quantum query complexity [5]–[10] over many years, we were driven to study the same problem but in the edge list model. Specifically, we study three variants of the triangle problem.

• \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\) asks whether there exists a triangle containing a target edge and raises general questions about how a problem’s complexity increases if its input is hidden among irrelevant data. For the specific problem, the irrelevant data consists of those edges in the input that are not incident to the target edge.

• \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\) asks whether there exists a triangle containing a target vertex and raises general questions about how a problem’s complexity increases if its input is shuffled. For the specific problem, two parts of the input are shuffled: one part containing edges incident to the target vertex and the other part containing the remaining edges. The notion of shuffling is also inherent in the comparison between the edge list and adjacency list models.

• \(\mathop{\mathrm{\mathsf{Triangle}}}\) asks whether a triangle exists and bridges the \(3\)-distinctness and \(3\)-sum problems. The latter two problems have been extensively studied, both in the worst-case setting by complexity theorists seeking to connect problem structure with algorithmic complexity [3], [11]–[14] and in the average-case setting by cryptographers seeking to understand the security of cryptosystems [15], [16].

We provide tight or nearly tight results for these problems as well as some first answers to the general questions they raise. Furthermore, we generalize our results for \(\mathop{\mathrm{\mathsf{Triangle}}}\) to \(k\)-cycle finding, a problem motivated by its close ties to the well-studied problem of \(k\)-distinctness.

1.1 Our results↩︎

In the following, we write \(Q(\cdot)\) for the worst-case (bounded-error) quantum query complexity, \(\mathbb{N}\) for the set of positive integers, and \([n]\mathrel{\vcenter{:}}= \{1,\dots,n\}\) for every \(n\in \mathbb{N}\).

1.1.0.1 \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\) and Hiding.

In \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\), when searching for a triangle containing a target edge \(\{u,v\}\), any edge in the input of the form \(\{u',v'\}\) such that \(\{u',v'\} \cap \{u,v\} = \varnothing\) can be viewed as irrelevant data that hides the relevant part of the input. This observation motivates a general definition of hiding.

Then \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\) can be seen as \(\mathop{\mathrm{\mathsf{HIDE}}}_m[\mathop{\mathrm{\mathrm{ED}}}_d]\), where \(\mathop{\mathrm{\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.⁶

The study of \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\) naturally led us to investigate how \(Q(f)\) relates to \(Q(\mathop{\mathrm{\mathsf{HIDE}}}_b[f])\) for arbitrary \(f\colon \Sigma^a \to \{0,1\}\). As a first step in this direction, we show \(Q(\mathop{\mathrm{\mathsf{HIDE}}}_b[f]) = \widetilde{\Theta}(\sqrt{b/a} \cdot Q(f))\) for every symmetric \(f\colon \{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 \(\mathop{\mathrm{\mathsf{HIDE}}}_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 \(\mathop{\mathrm{\mathsf{HIDE}}}_b[f]\) contains unstructured search on \(b-a+1\) items as a subproblem. Hence \[Q(\mathop{\mathrm{\mathsf{HIDE}}}_b[f])=\Omega(\sqrt{b-a+1}),\] 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\colon \Sigma^a \to \{0,1\}\), even if \(\mathopen{}\mathclose{\left|\Sigma}\right|>2\). We support this conjecture by showing that its randomized analogue is true in 13.

1.1.0.2 \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\) and Shuffling.

We show in 14 15 that the quantum query complexity of \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\), when the input is a length-\(m\) edge list and the target vertex \(u\) has degree \(d\) satisfies \[\Omega(\sqrt{m/d} \cdot Q(3\mathsf{\text{-}DIST}_d)) \leq Q(\mathop{\mathrm{\mathsf{TriangleVertex}}}) \leq O(\sqrt{m}d^{1/4}),\] where \(3\mathsf{\text{-}DIST}_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\mathsf{\text{-}DIST}_d)\) is between \(\Omega(d^{2/3})\) – because it is no easier than \(\mathop{\mathrm{\mathrm{ED}}}_d\) (which could be also called \(2\mathsf{\text{-}DIST}_d\)) – and \(O(d^{5/7})\) [3].

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 \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\).

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.

(I) Shuffled functions. As discussed, the edge list can be seen as a “shuffled version” of the adjacency list. We now formalize this notion.

In other words, the inputs to \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\) are shuffled versions of the inputs to \(f\) such that each symbol of the input to \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\) additionally contains its position pre-shuffling. Of course, every (worst-case) query complexity measure of \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\) is at least that of \(f\), since \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\) contains a copy of \(f\) under the restriction of the domain \(D\) to those inputs of the form \((x_1,1),\dots, (x_n,n)\), where \(x = x_1 \dots x_n \in \widetilde{D}\). If \(f\) is symmetric, then every query complexity measure on \(f\) is the same as that measure on \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\) since the algorithm computing \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\) could simply ignore the second coordinates of the input. If \(f\) is not symmetric, then \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f])\) could be much larger than \(Q(f)\): the dictator function witnesses a \(\Omega(\sqrt{n})\) versus \(1\) separation.

Given the above discussion, the interesting question becomes: how does the separation between \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f])\) and \(Q(f)\) depend on “how symmetric” \(f\) is? Natural (partially) symmetric \(f\) arises from graph properties. We show that there can be massive separations between \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f])\) and \(Q(f)\) even if \(f\) has significant symmetry by being defined as a graph property in either (i) the adjacency list model (exponential separation) or (ii) adjacency matrix model (unbounded separation).

Since an edge list can be interpreted as a shuffled adjacency list, result (i) can be interpreted as “quantum computers can compute some graph property exponentially faster given an adjacency list instead of an edge list”; the proof of result (ii) can also be adapted to show “quantum computers can compute some graph property unboundedly faster given an adjacency matrix instead of an edge list”.

(II) Shuffled direct sum. In \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\), the hardness arising from shuffling is intuitively not due to shuffling within parts \(A\) and \(B\) but rather between them. We formalize a toy version of this type of shuffling in the context of direct sum as follows.

We have \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}^k[f]) \geq \Omega(kQ(f))\), since computing \(\mathop{\mathrm{\mathsf{SHUFFLE}}}^k[f]\) is at least as hard as computing \(k\) independent copies of \(f\), which costs \(\Omega(kQ(f))\) queries by a well-known direct-sum theorem for quantum query complexity [17], [18]. This direct sum lower bound can be far from tight for \(\mathop{\mathrm{\mathsf{SHUFFLE}}}^k[f]\): again consider \(f\) being the dictator function. At first sight, computing \(\mathop{\mathrm{\mathsf{SHUFFLE}}}^k[f]\) seems harder than computing the \(k\) independent copies of \(f\) even if \(f\) is symmetric. Perhaps counterintuitively, we show in 22 that this is not the case if \(f\) is symmetric and has Boolean domain \(\{0,1\}^n\): for such \(f\), we show \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}^k[f]) \leq O(kQ(f))\). In 23, we conjecture that the same holds for symmetric \(f\) with non-Boolean domain.

1.1.0.3 Triangle Finding.

Having discussed \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\) and \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\), we now turn to \(\mathop{\mathrm{\mathsf{Triangle}}}\), where we simply ask whether a triangle exists⁸ without placing any constraints. In the edge list model, we find that \(\mathop{\mathrm{\mathsf{Triangle}}}\) bridges the \(3\mathsf{\text{-}DIST}\) and \(3\mathsf{\text{-}SUM}\) problems since its structure lies between theirs. Recall that in \(3\mathsf{\text{-}DIST}\), the goal is to decide whether the input contains three repetitions of the same symbol. In \(3\mathsf{\text{-}SUM}\), 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, \(\mathop{\mathrm{\mathsf{Triangle}}}\) should be no easier than \(3\mathsf{\text{-}DIST}\) and no harder than \(3\mathsf{\text{-}SUM}\) by considering its “certificate structure” [13]. In \(3\mathsf{\text{-}DIST}\), once we have found one symbol of a \(1\)-certificate, the next symbol for completing the certificate is determined. In \(3\mathsf{\text{-}SUM}\), once we have found one symbol of a \(1\)-certificate, the next symbol can be arbitrary. In comparison, in \(\mathop{\mathrm{\mathsf{Triangle}}}\), 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 24, we show that this intuition is formally correct by reducing \(3\mathsf{\text{-}DIST}\) to \(\mathop{\mathrm{\mathsf{Triangle}}}\) and \(\mathop{\mathrm{\mathsf{Triangle}}}\) to \(3\mathsf{\text{-}SUM}\).

Our first main result is stated informally below.

We find 3 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 [1] 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 [2], [16], [19]–[23]. Of particular relevance to our work is [2] 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, \(\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.

3 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\mathsf{\text{-}DIST}_m) \leq O(m^{5/7})\), up to logarithmic factors. This upper bound was first proven by Belovs [3] over a decade ago using a ground-breaking learning graph algorithm [6]. There have been no improvements since. On the other hand, the best-known lower bound on \(Q(3\mathsf{\text{-}DIST}_m)\) is still \(\Omega(m^{2/3})\), which is simply inherited from the element distinctness lower bound of Aaronson and Shi [24] proven over two decades ago. This is despite many attempts at raising the lower bound using the polynomial method [25], [26], adversary method [27], [28], and even recording queries (equivalently, compressed oracle) method [16]. In 1, we summarize these results together with those to be discussed later. Note that \(3\mathsf{\text{-}CYCLE}\) is equivalent to \(\mathop{\mathrm{\mathsf{Triangle}}}\).

We strongly believe that the matching of the lower bound in 3 and the best-known upper bound on \(Q(3\mathsf{\text{-}DIST}_m)\) is not a coincidence. This is because the “collision structure” of a uniformly random edge list on \(n\) vertices containing \(m = \Theta(n)\) edges resembles that of a candidate worst-case distribution on inputs to \(3\mathsf{\text{-}DIST}_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 3. As our second main result, we answer this question affirmatively.

Taken together, 3 4 give the first example of a problem for which Belovs’s learning graph algorithm in [3] is provably optimal, up to an \(m^{o(1)}\) factor.⁹ 3 also suggests that any quantum algorithm that polynomially improves the best-known \(O(m^{5/7})\) upper bound on \(Q(3\mathsf{\text{-}DIST}_m)\) must exploit more than just the collision structure of the problem, which seems improbable to us.

1.1.0.4 Cycle Finding.

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\geq 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\mathsf{\text{-}DIST}_m\) denote the function computing \(k\)-distinctness on length-\(m\) inputs. A candidate worst-case distribution on inputs to \(k\mathsf{\text{-}DIST}_m\) is the uniform distribution over inputs containing exactly one \(k\)-collision and \(\Omega(m)\) many \((k-1)\)-collisions, cf. [29] and [12]. 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)\mathrel{\vcenter{:}}= n!/(n-k)!\), a uniformly random length-\(m\) edge list on \(n=\Theta(m)\) vertices contains \[\begin{align} {3} &\Theta(P(n,k)\cdot (m/n^2)^{k-1}) &&= \Theta(m) \;&&\text{length-(k-1) paths} \\ \text{and} \quad &\Theta(P(n,k)\cdot (m/n^2)^k) &&= \Theta(1) \;&&\text{length-k cycles}. \end{align}\]

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 [16], 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 [3]. We have summarized the state of affairs in 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 38, stating that the quantum query complexity of \(k\)-cycle should not decrease too much under a restriction of the input edges, and prove in 40 that it enables such lifting.

1.1.0.5 Note added.

Subsequent to this work, Belovs [30] proved a tight quantum query lower bound for \(k\)-distinctness, using a framework inspired by Zhandry’s compressed oracle technique and independently of the lifting conjecture discussed above.

1.2 Technical overview↩︎

We now highlight some of our work’s main technical contributions. We inherit the notation above.

1.2.0.1 \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\) and Hiding.

To lower and upper bound \(Q(\mathop{\mathrm{\mathsf{HIDE}}}_m[\mathop{\mathrm{\mathrm{ED}}}_d])\), our main observation is that the problem “self-reduces” to a more structured version of itself, \(\mathop{\mathrm{\mathsf{HIDE}}}_m'[\mathop{\mathrm{\mathrm{ED}}}_d]\), whose query complexity is easier to characterize. The inputs to \(\mathop{\mathrm{\mathsf{HIDE}}}_m'[\mathop{\mathrm{\mathrm{ED}}}_d]\) are restricted to have the form of \(d\) blocks each of length \(m/d\),¹⁰ where each block contains \((m/d -1)\) \(*\)s and exactly one non-\(*\) symbol. Remarkably, imposing the block structure causes no decrease in hardness.

Observe that \(\mathop{\mathrm{\mathsf{HIDE}}}_m'[\mathop{\mathrm{\mathrm{ED}}}_d]\) can be viewed as the composition of \(\mathop{\mathrm{\mathrm{ED}}}_d\) with the so-called \(\mathrm{pSearch}\) function that extracts the unique non-\(*\) symbol from \(m/d\) symbols. The latter function has query complexity \(\Theta(\sqrt{m/d})\) and a composition theorem [31] yields \(Q(\mathop{\mathrm{\mathsf{HIDE}}}_m[\mathop{\mathrm{\mathrm{ED}}}_d]) \geq Q(\mathop{\mathrm{\mathsf{HIDE}}}_m'[\mathop{\mathrm{\mathrm{ED}}}_d]) \geq \Omega(\sqrt{m/d} \cdot d^{2/3}) = \Omega(\sqrt{m}d^{1/6})\). To upper bound \(Q(\mathop{\mathrm{\mathsf{HIDE}}}_m[\mathop{\mathrm{\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 \(\mathop{\mathrm{\mathsf{HIDE}}}_m'[\mathop{\mathrm{\mathrm{ED}}}_d]\), except each block may contain up to \(\log(d)\) non-\(*\) symbols. Since the number of non-\(*\) symbols in each block is so small, we simply Grover search for all of them on the fly while running the quantum algorithm for \(\mathop{\mathrm{\mathrm{ED}}}_{d\log(d)}\) on \(d\log(d)\) symbols. This algorithm has query complexity \(\widetilde{O}(\sqrt{m} d^{1/6})\).

By considering the block structure, we also see \(Q(\mathop{\mathrm{\mathsf{HIDE}}}_m[f]) = \Omega(\sqrt{m/d} \cdot Q(f))\) for every \(f\colon \Sigma^d \to \{0,1\}\). We show \(Q(\mathop{\mathrm{\mathsf{HIDE}}}_m[f]) =\widetilde{O}(\sqrt{m/d} \cdot Q(f))\) for symmetric \(f\colon \{0,1\}^d \to \{0,1\}\) using the characterization of the optimal quantum query algorithm for such functions in [32]. We show \(R(\mathop{\mathrm{\mathsf{HIDE}}}_m[f]) = O((m/d)\cdot R(f))\) for symmetric \(f\colon \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 [33].

1.2.0.2 \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\) and Shuffling.

To obtain \(Q(\mathop{\mathrm{\mathsf{TriangleVertex}}}) \leq O(\sqrt{m} d^{1/4})\) in 14, we use a quantum walk algorithm that walks on the Hamming graph with vertices labeled by \(r \mathrel{\vcenter{:}}= \ceil{d^{3/4}}\) 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(\mathop{\mathrm{\mathsf{TriangleVertex}}}) \geq \Omega(\sqrt{m/d} \cdot Q(3\mathsf{\text{-}DIST}))\), we give a reduction from \(\mathop{\mathrm{\mathsf{HIDE}}}_m[3\mathsf{\text{-}DIST}]\) to \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\) in 15.

We obtain an exponential separation between \(Q(f)\) and \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f])\) when \(f\) is defined by the graph property \(\mathcal{P}\) from [34] in the adjacency list model as follows. [34] showed that computing \(f\) witnesses an exponential separation between randomized and quantum query complexities. But the quantum query complexity of computing \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\) is polynomially related to its randomized query complexity since the problem is symmetric [35].

If \(f\) is defined by a graph property in the adjacency matrix model, the above argument cannot work since [34] 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(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f])\) can be witnessed by the following Majority-of-Majority function on a restricted partial domain, that we name \(\mathrm{\Sigma MAJ}\):¹¹

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}\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 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 MAJ}_n) \leq R(\mathrm{\Sigma MAJ}_n) = O(1)\).

In contrast, computing \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[\mathrm{\Sigma 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\neq j_2\), which is a collision-type problem. Formally, we prove \(R(\mathop{\mathrm{\mathsf{SHUFFLE}}}[\mathrm{\Sigma MAJ}_n]) = \Omega(\sqrt{n})\) in 19 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(\mathop{\mathrm{\mathsf{SHUFFLE}}}[\mathrm{\Sigma MAJ}_n]) = \Omega(R(\mathop{\mathrm{\mathsf{SHUFFLE}}}[\mathrm{\Sigma MAJ}_n])^{1/3}) = \Omega(n^{1/6})\), where the first equality uses [35], which applies since \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[\mathrm{\Sigma MAJ}_n]\) is symmetric.

1.2.0.3 Triangle Finding (lower bound).

We prove our lower bound on triangle finding (3) in Zhandry’s recording query framework [1]. 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:¹²

1. we first show that the progress in recording much more than \(r^*(t)\mathrel{\vcenter{:}}= t^{3/2}\log^2(n)/\sqrt{n}\) wedges in \(t\) queries is negligible;

2. then we show that, given we record \(O(r^*(t))\) wedges in \(t\) queries, the progress of recording a triangle at the \((t+1)\)-th query increases by at most \(O(\sqrt{r^*(t)}/n)\), which corresponds to the square root of the probability that a random edge completes one of the \(r^*(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^*(t)}/n\), which equals \(O(T^{7/4}\log(n)/n^{5/4})\), and is \(o(1)\) unless \(T \geq \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.¹³ For example, it was exploited to great effect by Liu and Zhandry [16] 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 \(\Lambda_{t,r} \in [0,1]\) for integer \(t,r\) with \(t\geq 0\) where \(\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 \(\Lambda_{t,r}\): \[\label{eq:naive95recurrence} \Lambda_{t,r} \leq \Lambda_{t-1,r} + O(\sqrt{t/n}) \cdot \Lambda_{t-1,r-t+1},\tag{2}\] 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 2 leads to a trivial lower bound for triangle finding that does not even beat the \(\Omega(m^{2/3})\) lower bound it inherits from element distinctness.

The main problem with 2 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-\(\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)) \leq 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 (5), answers this question affirmatively. This lemma allows us to transfer, or mirror, properties of the initial input distribution onto the internal memory of the quantum algorithm, independently of the value of \(t\). Directly using this technique allows us to improve 2 to \[\label{eq:intermediate95recurrence} \Lambda_{t,r} \leq \Lambda_{t-1,r} + O(\sqrt{t/n}) \cdot \Lambda_{t-1,r-O(\log^2(n))} + \varepsilon,\tag{3}\] where \(\varepsilon>0\) is a small number corresponding to the tail probability of the input graph having a vertex of degree \(\Omega(\log(n))\).

Unfortunately, 3 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} + \varepsilon\) (with \(p,\varepsilon\in [0,1]\) and boundary conditions \(A_{0,0} = 1\) and \(A_{0,r} = 0\) for all \(r>0\)) is \(A_{t,r} = \binom{t}{r}p^r + \varepsilon(1 + (1+p) + \dots + (1+p)^{t-1})\). Even for an exponentially small \(\varepsilon\), the term \(\varepsilon(1+p)^{t-1}\) blows up for large \(t\). Our second technical contribution, the Exclusion Lemma (2), allows us to overcome this problem. To employ this lemma, we introduce a new progress quantity called \(\Lambda_{t,r}'\) that is defined like \(\Lambda_{t,r}\) except we additionally require the quantum query algorithm to not have recorded a degree-\(\Omega(\log(n))\) vertex at any point before the \(t\)-th query. By definition, \(\Lambda_{t,r}'\) satisfies recurrence 3 with \(\varepsilon\) set to \(0\), that is, \[\label{eq:final95recurrence} \Lambda_{t,r}' \leq \Lambda_{t-1,r}' + O(\sqrt{t/n}) \cdot \Lambda_{t-1,r-O(\log^2(n))}'.\tag{4}\] The Exclusion Lemma allows us to upper bound \(\Lambda_{t,r}\) by \(\Lambda_{t,r}' + O(t \varepsilon)\), where the second term no longer blows up for large \(t\) and is easy to make negligible. Therefore, solving 4 first for \(\Lambda_{t,r}'\) and then using \(\Lambda_{t,r} \leq \Lambda_{t,r}' + O(t \varepsilon)\) yields the claimed result of step (i).

1.2.0.4 Triangle Finding (upper bound).

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

The notion of a fault is easier to explain in Jeffery and Zur’s interpretation of Belovs’s algorithm as a quantum walk [42].¹⁴ The following explanation is based on [42]. 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} \neq 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\leq O(\log(n)/\log\log(n))\). Then we adapt the “error-correcting” technique of [3] 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 [3]; for example, our algorithm genuinely corresponds to a graph, unlike that in [3].

1.2.0.5 Cycle Finding.

We prove our lower and upper bounds on \(k\)-cycle finding by generalizing our proofs in the \(k=3\) (triangle) case.¹⁵ 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=\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,\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\leq j \leq 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 \(\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\leq 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.

2 Preliminaries↩︎

2.0.0.1 Notation.

\(\mathbb{N}\) denotes the set of positive integers. Notation such as \(\mathbb{Z}_{\geq 0}\) denotes the set of non-negative integers, \(\mathbb{R}_{>0}\) denotes the set of positive reals, for \(a\geq 0\), \(\mathbb{Z}_{[0,a]}\) denotes the set \(\mathbb{Z}\cap[0,a]\), and so on. For \(n\in \mathbb{N}\), \([n]\) denotes the set \(\{1,\dots,n\}\). For two complex square matrices \(X,Y\) of the same dimension, we write \(X\leq Y\) to mean \(Y-X\) is positive semidefinite, and \(X\geq Y\) to mean \(X-Y\) is positive semidefinite. We use \(\mathop{\mathrm{\mathbb{I}}}\) to denote an identity matrix of a context-appropriate dimension.

An alphabet is a finite non-empty set. For an alphabet \(A\) and \(k\in \mathbb{Z}_{\geq 0}\), \(\binom{A}{k}\) denotes the set of all size-\(k\) subsets of \(A\). For \(n\in \mathbb{N}\) and \(\gamma \geq 0\), we write \(\binom{n}{<\gamma}\) for the sum \(\sum_{i \in \{0,1,\dots, n\} \cap [0,\gamma)} \binom{n}{i}\). Given two disjoint sets \(A,B\), we sometimes write \(A\dot{\cup}B\) for their union, where the dot emphasizes that \(A\) and \(B\) are disjoint. (If we write \(A\cup B\) instead, \(A\) and \(B\) could still be disjoint.) For an alphabet \(\Sigma\), we write \(x\leftarrow \Sigma\) for sampling \(x\) uniformly at random from \(\Sigma\). For \(x\in \Sigma^n\) and \(a,b\in \mathbb{N}\), \(x[a\mathop{\mathrm{..}}b]\) denotes the substring of \(x\) from index \(a\) to \(b\) inclusive; if \(b<a\), then this denotes the empty string. For \(k, n\in \mathbb{N}\) with \(k\geq 3\), we say \(\{u_1,v_1\}, \dots, \{u_k,v_k\} \in \binom{[n]}{2}\) form a \(k\)-cycle if there exists distinct \(w_1,\dots,w_k\in [n]\) such that \(\{u_1,v_1\} = \{w_1,w_2\}\), \(\dots\), \(\{u_{k-1},v_{k-1}\} = \{w_{k-1},w_k\}\), and \(\{u_k,v_k\} = \{w_k,w_1\}\). For \(k,n,m\in \mathbb{N}\) with \(k\geq 3\), we say \(x\in \binom{[n]}{2}^m\) contains a \(k\)-cycle if there exist distinct \(i_1,\dots,i_k \in [m]\) such that \(x_{i_1},\dots,x_{i_k}\) form a \(k\)-cycle. The word “triangle” formally refers to a \(3\)-cycle.

For an alphabet \(U\), we denote the symmetric group acting on \(U\) by \(\mathfrak S_U\). For \(n\in \mathbb{N}\), we also use \(\mathfrak S_n\) to denote the symmetric group acting on \([n]\). We say a function \(f\colon E \subseteq \Sigma^n \to \{0,1\}\) is symmetric if \(x_1,\dots,x_n \in E \implies x_{\sigma(1)},\dots, x_{\sigma(n)} \in E\) and \(f(x_1,\dots,x_n) = f(x_{\sigma(1)},\dots, x_{\sigma(n)})\) for all \(x\in \Sigma^n\) and for all permutations \(\sigma \in \mathfrak S_n\). Note that we do not require a symmetric \(f\) to be invariant under permutations of the alphabet \(\Sigma\).

The abbreviation “wlog” stands for “without loss of generality”; “s.t.” stands for “such that”; “with high probability” stands for “with probability at least \(1-10^{-10}\)” unless stated otherwise. The symbol \(\log\) stands for the base-\(2\) logarithm.

For a function \(f\colon D \subseteq \Sigma^n \to \Gamma\), where \(D,\Sigma,\Gamma\) are alphabets and \(n\in \mathbb{N}\), and \(\varepsilon\in (0,1/2)\), we write \(Q_\varepsilon(f)\) and \(R_\varepsilon(f)\) for the quantum and randomized query complexities for \(f\) with two-sided failure probability at most \(\varepsilon\), respectively. We write \(Q(f)\) and \(R(f)\) for \(Q_{1/3}(f)\) and \(R_{1/3}(f)\), respectively.

2.0.0.2 Function definitions.

For \(m,d,n,s,k\in \mathbb{N}\), \(u,v\in [n]\) with \(u\neq v\), \(G\) a finite abelian group with identity element \(0\), we define the following functions of interest in this work.

1. \(k\mathsf{\text{-}DIST}_m\colon [s]^m \to \{0,1\}\) denotes the \(k\)-distinctness function which is defined by \(k\mathsf{\text{-}DIST}_m(x) = 1\) if and only if there exist \(k\) distinct indices \(1\leq i_1<i_2<\dots<i_k \leq m\) such that \(x_{i_1} = x_{i_2} = \dots = x_{i_k}\). We also write \(\mathop{\mathrm{\mathrm{ED}}}_m\) for \(2\mathsf{\text{-}DIST}_m\), commonly known as the element distinctness function.

2. \(k\mathsf{\text{-}SUM}_m\colon G^m \to \{0,1\}\) denotes the \(k\)-sum function which is defined by \(k\mathsf{\text{-}SUM}_m(x) = 1\) if and only if there exist \(k\) distinct indices \(1\leq i_1<i_2<\dots<i_k \leq m\) such that \(x_{i_1} + x_{i_2} + \dots + x_{i_k} = 0\).

3. \(\mathop{\mathrm{\mathsf{TriangleEdge}}}^{\{u,v\}}_m \colon D\subseteq \binom{[n]}{2}^m \to \{0,1\}\) denotes the triangle edge function which is defined by \(x\in D\) if and only if \(x_i\neq x_j\) for all \(i\neq j\), and \(\mathop{\mathrm{\mathsf{TriangleEdge}}}_m^{\{u,v\}}(x) = 1\) if and only if there exist distinct \(i,j\in [m]\) such that \(x_i\), \(x_j\) and \(\{u,v\}\) form a triangle.

4. \(\mathop{\mathrm{\mathsf{TriangleEdge}}}^{\{u,v\}}_{m,d} \colon D_d\subseteq \binom{[n]}{2}^m \to \{0,1\}\) is the restriction of \(\mathop{\mathrm{\mathsf{TriangleEdge}}}^{\{u,v\}}_m\) such that \(x \in D_d\) if and only if \(x_i\neq x_j\) for all \(i\neq j\) and \(\mathopen{}\mathclose{\left|\{i\in [m] \mid \mathopen{}\mathclose{\left|x_i \cap \{u,v\}}\right| = 1\}}\right| = d\).

5. \(\mathop{\mathrm{\mathsf{TriangleVertex}}}^{u}_m \colon \binom{[n]}{2}^m \to \{0,1\}\) denotes the triangle vertex function which is defined by \(\mathop{\mathrm{\mathsf{TriangleVertex}}}^{u}_m(x) = 1\) if and only if there exist distinct \(i,j,k\in [m]\) such that \(x_i\), \(x_j\) and \(x_k\) form a triangle containing vertex \(u\).

6. \(\mathop{\mathrm{\mathsf{TriangleVertex}}}^{u}_{m,d} \colon D_d\subseteq \binom{[n]}{2}^m \to \{0,1\}\) is the restriction of \(\mathop{\mathrm{\mathsf{TriangleVertex}}}^{u}_{m,d}\) such that \(x\in D_d\) if and only if \(\mathopen{}\mathclose{\left|\{i\in [m] \mid \mathopen{}\mathclose{\left|x_i \cap \{u\}}\right| = 1\}}\right| \leq d\).

7. \(k\mathsf{\text{-}CYCLE}_m \colon \binom{[n]}{2}^m \to \{0,1\}\) denotes the \(k\)-cycle function which is defined by \(k\mathsf{\text{-}CYCLE}_m(x) = 1\) if and only if there exist \(k\) distinct indices \(1\leq i_1<i_2<\dots<i_k \leq m\) such that \(x_{i_1}, \dots, x_{i_k}\) form a \(k\)-cycle. We also write \(\mathop{\mathrm{\mathsf{Triangle}}}_m\) for \(3\mathsf{\text{-}CYCLE}_m\).

8. \(k\mathsf{\text{-}CYCLE}_{m,d} \colon D_d \subseteq \binom{[n]}{2}^m \to \{0,1\}\) denotes the restriction of \(k\mathsf{\text{-}CYCLE}_m\) such that \(x\in D_{d}\) if and only if for all \(u\in [n]\), \(\mathopen{}\mathclose{\left|\{i\in [m] \mid \mathopen{}\mathclose{\left|x_i \cap \{u\}}\right| = 1\}}\right| \leq d\). (That is, the maximum degree of the graph represented by \(x\) is at most \(d\).) We also write \(\mathop{\mathrm{\mathsf{Triangle}}}_{m,d}\) for \(3\mathsf{\text{-}CYCLE}_{m,d}\).

For \(\mathop{\mathrm{\mathsf{TriangleEdge}}}_m^{\{u,v\}}\), \(\mathop{\mathrm{\mathsf{TriangleEdge}}}_{m,d}^{\{u,v\}}\), \(\mathop{\mathrm{\mathsf{TriangleVertex}}}_{m}^{u}\), and \(\mathop{\mathrm{\mathsf{TriangleVertex}}}_{m,d}^{u}\), we refer to their superscripts as their target edge and target vertex respectively. We will often omit these superscripts since the (quantum) query complexity of these problems does not depend on them.

We note that the definitions of \(\mathop{\mathrm{\mathsf{TriangleEdge}}}_m\) and \(\mathop{\mathrm{\mathsf{TriangleEdge}}}_{m,d}\) appear more restrictive than that of the other triangle problems: the input cannot have duplicate edges and the number of input edges incident (but not equal) to the target edge is exactly \(d\). These restrictions allow us to more directly relate them to the hiding transform of element distinctness.

2.0.0.3 Search-to-decision reduction.

Let \(k\in \mathbb{N}_{\geq 3}\) be a constant. We construct a search algorithm for finding a \(k\)-cycle in a length-\(m\) edge list, or deciding that none exists, that is correct with high probability using \(O(\log^2(m))\) calls to a bounded error decision algorithm for \(k\mathsf{\text{-}CYCLE}_m\). The details are as follows.

Using standard probability amplification techniques, we reduce the error of the bounded-error \(k\mathsf{\text{-}CYCLE}_m\) algorithm to \(O(1/m)\) by repeating it \(O(\log (m))\) times and taking the majority vote.

Given that each positive instance of \(k\mathsf{\text{-}CYCLE}_m\) contains a size-\(k\) certificate, we can divide the input into \(k+1\) parts. Among these, there exist \(k\) parts that together contain the certificate. Identifying these \(k\) parts requires \(\binom{k}{k-1}=O(1)\) calls to the \(k\mathsf{\text{-}CYCLE}_m\) algorithm, and in each call, we pad the input with a disjoint cycle-free graph to maintain the input size. By doing this, we reduce the search range by a factor of \(k/(k+1)\). Repeating this process \(O(\log(m))\) times shrinks the search range to \(O(1)\), at which point the certificate can be directly identified. By applying the union bound over all calls, the probability of any error occurring remains at most \(O(\log(m)/m)\), thus ensuring correctness with high probability.

In the other direction, a search algorithm can be directly used as a decision algorithm. Therefore, we typically do not distinguish between the search and decision versions of the \(k\)-cycle problem.

2.0.0.4 A convention.

Technically, all of the above functions should also be parametrized by their input alphabet size, especially since their (quantum) query complexity can strictly increase as a function of this size.¹⁶ In this work, we often omit this parametrization under the convention that the input alphabet size is sufficiently large. For example, consider \(\mathop{\mathrm{\mathrm{ED}}}_m\colon [s] \to \{0,1\}\) as defined above. We write \(Q(\mathop{\mathrm{\mathrm{ED}}}_m) = \Omega(m^{2/3})\) to mean: for all sufficiently large \(s\in \mathbb{N}\), \(Q(\mathop{\mathrm{\mathrm{ED}}}_m) = \Omega(m^{2/3})\). We write \(Q(\mathop{\mathrm{\mathrm{ED}}}_m) = O(m^{2/3})\) to mean: for all \(s\in \mathbb{N}\), \(Q(\mathop{\mathrm{\mathrm{ED}}}_m) = O(m^{2/3})\). Note that we do not need “sufficiently large” \(s\) here since the (quantum) query complexity is always non-decreasing with respect to \(s\). We write \(Q(\mathop{\mathrm{\mathrm{ED}}}_m) = \Theta(m^{2/3})\) to mean: \(Q(\mathop{\mathrm{\mathrm{ED}}}_m) = O(m^{2/3})\) and \(Q(\mathop{\mathrm{\mathrm{ED}}}_m) = \Omega(m^{2/3})\) in the aforementioned senses.

3 \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\) and Hiding↩︎

As discussed in the introduction, \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\) can be seen as an instantiation of the general hiding phenomenon. We recall the formal definition of hiding from the introduction, 1.

Let \(a,b\) be integers with \(b\geq a\geq 1\). Let \(\widetilde{D},\Sigma\) be finite non-empty sets with \(\widetilde{D}\subseteq \Sigma^a\). For \(f\colon \widetilde{D}\to \{0,1\}\), the hiding transform of \(f\) is defined to be \[\mathop{\mathrm{\mathsf{HIDE}}}_b[f] \colon D \subseteq (\Sigma \cup \{*\})^b \to \{0,1\},\] where \(*\) is a symbol outside of \(\Sigma\), the set \(D\) consists of all strings \(y \in (\Sigma \cup \{*\})^b\) with exactly \(a\) non-\(*\) symbols such that the length-\(a\) subsequence¹⁷ \(\tilde{y}\) formed by those non-\(*\) symbols is an element of \(\widetilde{D}\), and \(\mathop{\mathrm{\mathsf{HIDE}}}_b[f](y)\) is defined to be \(f(\tilde{y})\).

By hiding the input in a more structured way, one can get a composition-like problem, for which it is easier to show lower bounds.

We begin with a general result on hiding.

Now, \(\mathop{\mathrm{\mathsf{TriangleEdge}}}\) can be seen as the hiding transform of the element distinctness function. Intuitively, having no triangle that contains the target edge \(\{u,v\}\) is equivalent to the neighbors of \(u\) and the neighbors of \(v\) being distinct.

We now formally show that \(\mathop{\mathrm{\mathsf{TriangleEdge}}}_{m,d}\) has the same quantum query complexity as \(\mathop{\mathrm{\mathsf{HIDE}}}_m(\mathop{\mathrm{\mathrm{ED}}}_d)\) by reducing these problems to each other. Our reduction also works in non-quantum query models.

The results of this section naturally raise the following conjecture.

We proved this conjecture (up to logarithmic factors) when the domain of \(f\) is Boolean using the structure of the optimal quantum query algorithm for such \(f\). On the other hand, we proved this conjecture when \(f=\mathop{\mathrm{\mathrm{ED}}}_d\) using the structure of the function itself. We believe that attacking this conjecture for arbitrary \(f\) would yield further insights into the structure of symmetric functions and their optimal quantum query algorithms.

Towards the above conjecture, we show the following proposition.

4 \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\) and Shuffling↩︎

In this section, we consider the \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\) problem of deciding whether an input edge list of length \(m\) has a triangle containing a target vertex of degree \(d \leq m\).

We take this opportunity to study the shuffling transformation as well. As mentioned in the introduction, the edge list itself can be viewed as a shuffled adjacency list. In \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\), there is an additional “block-wise” notion of shuffling, where the blocks consist of edges incident and not incident to the target vertex, respectively. This latter notion motivates our definition of shuffled direct sum.

4.1 \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\)↩︎

We first build intuition by directly working out some upper and lower bounds on the quantum query complexity of \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\). The upper bound uses a quantum walk algorithm, and the lower bound uses a reduction from the hiding transform of \(3\mathsf{\text{-}DIST}\).

Observe that in the proof of 14 above, the algorithm does not a priori know which part of the input \(x\) is in \(A\) and which part is in \(B\). It appears that the shuffling of these parts adds to the complexity of the problem. To investigate how generic this phenomenon is, we consider two types of questions motivated by shuffling.

1. How does shuffling a function change its complexity?

2. How does shuffling affect direct sum theorems?

We formalize these questions in the next two sections and prove some first results.

4.2 Shuffled functions↩︎

We recall 2 of shuffling from the introduction. Let \(n\in \mathbb{N}\). Let \(\widetilde{D},\Sigma\) be finite non-empty sets with \(\widetilde{D}\subseteq \Sigma^n\). For a function \(f\colon \widetilde{D} \to \{0,1\}\), the shuffling transform of \(f\) is defined to be \[\mathop{\mathrm{\mathsf{SHUFFLE}}}[f] \colon D \subseteq (\Sigma\times [n])^n \to \{0,1\}, \quad \text{where}\]

1. the set \(D\) consists of all elements \(x\in (\Sigma\times [n])^n\) satisfying \(x = ((v_1,\pi(1)),\dots,(v_n,\pi(n)))\) for some bijection \(\pi\colon [n]\to [n]\) such that \((v_{\pi^{-1}(1)},v_{\pi^{-1}(2)},\dots,v_{\pi^{-1}(n)})\in \widetilde{D}\).

2. \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f](x)\mathrel{\vcenter{:}}= f(v_{\pi^{-1}(1)},v_{\pi^{-1}(2)},\dots,v_{\pi^{-1}(n)})\).

Next, we collect some simple facts about \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\).

We record one more fact that relates the quantum and randomized query complexities for \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\).

The importance of the above fact is that it provides a generic lower bound method for the quantum query complexity for problems in the edge list model, since analyzing the randomized query complexity is often easier. The proof of this fact is based on the simple observation that \(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]\) transforms every function \(f\) into a symmetric function. The beautiful work of Chailloux [35] shows that the quantum query complexity of every symmetric function is at least big-\(\Omega\) of its randomized query complexity raised to the power \(1/3\).

As we have observed, for general \(f\), \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f])\) can be unboundedly larger than \(Q(f)\) while for symmetric \(f\), \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}[f]) = Q(f)\). Therefore, the interesting question becomes what happens when \(f\) is partially symmetric, for example, by being defined via graph properties? This question can be used to understand how the complexity of a graph property changes in the edge list model versus the adjacency list and adjacency matrix models.

Can there be a large separation between the quantum query complexity of a graph property in the edge list model versus the adjacency list model?

We show there can be an exponential separation.

As the edge list model is the shuffled version of the adjacency list model, we find it natural to also consider the shuffled version of the adjacency matrix model and ask the following question.

Can there be a large separation between the quantum query complexity of a graph property in the adjacency matrix model versus the shuffled adjacency matrix model?

We can no longer appeal to the previous argument because [34] shows that the quantum query complexity of every graph property in the adjacency matrix model is at least that of its randomized query complexity raised to the \(1/6\) power. Nonetheless, we can answer the question with “yes” by considering a function \(\mathrm{\Sigma MAJ}_n\) defined in 4. \(\mathrm{\Sigma MAJ}_n\) can be seen as a (directed) graph property computed in the adjacency matrix model.

Recall that \(\mathrm{\Sigma MAJ}_n\colon D_0\dot{\cup} D_1 \subseteq \{0,1\}^{n^2} \to \{0,1\}\) is defined to be the following restriction of \(\mathrm{MAJ}_n\circ \mathrm{MAJ}_n\) on \(n^2\) bits. \[\label{eq:maj95circ95maj} \mathrm{\Sigma MAJ}_n : x \mapsto \begin{cases} 0, &x\in D_0,\\ 1, &x\in D_1, \end{cases}\tag{6}\] where \(D_0\) consists of all \(x = (x_{1,1},x_{1,2},\dots, x_{n,n}) \in \{0,1\}^{n^2}\) such that there exists a subset \(S\subseteq[n]\) of size at least \(2n/3\) such that for all \(i\in S\), \(x^i \mathrel{\vcenter{:}}= (x_{i,1},\dots,x_{i,n})\) has Hamming weight \(\mathopen{}\mathclose{\left|x^i}\right| \ge 2n/3\) and for all \(i\in [n]-S\), \(\mathopen{}\mathclose{\left|x^i}\right| \le n/3\); while \(x = (x_{1,1},x_{1,2},\dots, x_{n,n}) \in \{0,1\}^{n^2}\) is in \(D_1\) if and only if there exists a subset \(S\subseteq[n]\) of size at most \(n/3\) such that for all \(i\in S\), \(x^i \mathrel{\vcenter{:}}= (x_{i,1},\dots,x_{i,n})\) has Hamming weight \(\mathopen{}\mathclose{\left|x^i}\right| \ge 2n/3\) and for all \(i\in [n]-S\), \(\mathopen{}\mathclose{\left|x^i}\right| \le n/3\).

4.3 Shuffled direct sum↩︎

In the \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\) problem, the shuffling can be seen as arising from a two-step process. The first step shuffles among edges incident to the target vertex \(v\) (or not incident to \(v\)), and the second step shuffles between edges incident or not incident to \(v\). The latter type of shuffling motivates the notion of shuffled direct sum in 3, which we now recall.

Let \(n,k\in \mathbb{N}\). Let \(\Sigma\) be a finite non-empty set. For a function \(f \colon \Sigma^n \to \{0,1\}\), the \(k\)-shuffled direct sum of \(f\) is defined to be \[\mathop{\mathrm{\mathsf{SHUFFLE}}}^k[f]\colon D \subseteq (\Sigma\times [k])^{kn} \to \{0,1\}^k, \quad \text{where}\]

1. the set \(D\) consists of all elements \(x\in (\Sigma\times [k])^{kn}\) satisfying \(x = ((v_1,c_1),\dots, (v_{kn},c_{kn}))\) such that, for all \(j\in [k]\), there are exactly \(n\) indices \(i\in [kn]\) with \(c_i = j\).

2. \(\mathop{\mathrm{\mathsf{SHUFFLE}}}^k[f](x)\) is defined to equal \((f(v^{(1)}),\dots,f(v^{(k)}))\), where \(v^{(j)}\) is the subsequence of \(v\mathrel{\vcenter{:}}= v_1\dots v_{kn}\) indexed by those \(i\in [kn]\) such that \(c_i = j\).

Naturally, the question is how \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}^k(f))\) relates to \(Q(\mathop{\mathrm{\mathsf{SHUFFLE}}}(f))\). Since \(\mathop{\mathrm{\mathsf{SHUFFLE}}}^k(f)\) restricts to the \(k\)-fold direct sum of \(f\), the direct sum theorem for the quantum query complexity [17], [18] immediately gives the following.

The following result shows that the above lower bound is tight when the domain of \(f\) is \(\{0,1\}^n\).

We conjecture that 22 still holds for symmetric \(f\colon \Sigma^n\to \{0,1\}\) even if \(\Sigma\) is non-Boolean.

We remark that this conjecture holds for randomized query complexity, i.e., with \(Q(\cdot)\) replaced by \(R(\cdot)\): the upper bound follows by a similar argument to the proof of 13, while the lower bound follows by [47].

None

5 Triangle Finding↩︎

In this section, we study the triangle problem, \(\mathop{\mathrm{\mathsf{Triangle}}}\). We first show that this problem bridges \(3\mathsf{\text{-}DIST}\) and \(3\mathsf{\text{-}SUM}\). Then, we give a nearly tight characterization of the problem’s quantum query complexity when the input has low maximum degree, for example, if it is a random sparse graph.

5.1 Bridging \(3\mathsf{\text{-}DIST}\) and \(3\mathsf{\text{-}SUM}\)↩︎

We formalize the aforementioned connection of \(\mathop{\mathrm{\mathsf{Triangle}}}\) to \(3\mathsf{\text{-}DIST}\) and \(3\mathsf{\text{-}SUM}\) in the following proposition.

For comparison, we note that the “trivial” lower bound on \(Q(\mathop{\mathrm{\mathsf{Triangle}}}_m)\) by reducing from \(\mathop{\mathrm{\mathrm{OR}}}_{m-2}\) is \(Q(\mathop{\mathrm{\mathsf{Triangle}}}_m)=\Omega(\sqrt{m})\) while the above proposition gives \(Q(\mathop{\mathrm{\mathsf{Triangle}}}_m)=\Omega(m^{2/3})\) as the latter is the best-known lower bound on \(3\mathsf{\text{-}DIST}_m\) [24].

5.2 The uniformly random edge list↩︎

We now turn to the average-case analysis of \(\mathop{\mathrm{\mathsf{Triangle}}}\). In particular, we consider the random graph model with \(m\) (multi-)edges, such that the \(m\) edges are each sampled independently and uniformly from \(\binom{[n]}{2}\). In other words, we consider the sample-with-replacement model. In this model, the input edge list \(x\) can be written succinctly as \(x\leftarrow \binom{[n]}{2}^m\).

Denote the graph on \(n\) vertices formed by the edges in \(x\) by \(\mathop{\mathrm{\mathcal{G}}}(x)\). We use \(\mathop{\mathrm{\mathrm{maxdeg}}}(\mathop{\mathrm{\mathcal{G}}}(x))\) or simply \(\mathop{\mathrm{\mathrm{maxdeg}}}(x)\) to denote the max vertex degree of \(\mathop{\mathrm{\mathcal{G}}}(x)\). A wedge in \(\mathop{\mathrm{\mathcal{G}}}(x)\) is a length-two path. Since \(x\) could contain repeated edges, \(\mathop{\mathrm{\mathcal{G}}}(x)\) could be non-simple. In particular, the degree and wedge counts of \(\mathop{\mathrm{\mathcal{G}}}(x)\) account for the multiplicities of repeated edges. Later, we will also consider strings \(x\in (\binom{[n]}{2}\cup \{\bot\})^m\), where \(\bot\) means the input edge has not yet been revealed.

Our focus will be the \(m=\Theta(n)\) regime of sparse graphs. In this regime, we obtain near-matching upper and lower bounds for the quantum query complexity of triangle finding. The following basic facts about sparse random graphs will be useful. We defer the proof to 7.

For a technical reason, we also need the following simple fact.

Note that \(\{v\in [n]\mid \mathrm{v\in x_i for some i\in S}\}\) is formal notation for the set of vertices involved in the edges in \(x\) at positions in \(S\).

We call a graph \(x \in \binom{[n]}{2}^m\) good if \(\mathop{\mathrm{\mathrm{maxdeg}}}(\mathop{\mathrm{\mathcal{G}}}(x)) = O( \log(n) / \log\log(n) )\) and \(x\) contains a triangle. Our quantum lower and upper bounds will hold for good graphs. By 26, a random graph \(x\leftarrow\binom{[n]}{2}^m\) is good with probability \(\Omega(1)\) for \(m = \Theta(n)\).

27 states that a small subgraph of a good graph \(x\) does not touch any vertex from some small subset \(T\) with high probability. The vertex set \(T\) that the subgraph wants to avoid will be a triangle, and \(s\) will be of size \(o(m)\). Thus, the avoidance property holds almost surely.

5.3 Triangle finding lower bound↩︎

Our lower bound result reads:

A simple corollary of 28 is that \(Q(\mathop{\mathrm{\mathsf{Triangle}}}_m)\geq \widetilde{\Omega}(m^{5/7})\). In fact, the lower bound holds even if we are promised the maximum degree of the input graph is low.

For the rest of this section, we prove 28.

5.3.1 Setting up↩︎

5.3.1.1 Recording query framework.

We start by reviewing the recording query framework [1], [2]. For convenience of notation, we write \(N \mathrel{\vcenter{:}}= \binom{n}{2}\) and identify \([N]\) with \(\binom{[n]}{2}\) for the rest of this section. A projector refers to a complex square matrix \(P\) of some context-appropriate dimension such that \(P^\dagger = P\) and \(P^2 = P\).

Let \(m, T\in \mathbb{N}\) and \(\Sigma\) be an alphabet. Given a relation \(R\subseteq [N]^m \times \Sigma\), a \(T\)-query quantum query algorithm for computing \(R\) is specified by a sequence of unitary matrices \(U_0,\dots,U_T\) acting on \(\mathbb{C}^m\otimes \mathbb{C}^N \otimes \mathbb{C}^K\) for some \(K\in \mathbb{N}\). \(\mathbb{C}^K\) is referred to as a workspace register.

For \(t\in \{0,1,\dots,T\}\), the state of the algorithm at the \(t\)-th step given input \(x\in [N]^m\) is defined by \[\ket{\psi_t^x} \mathrel{\vcenter{:}}= U_t\mathcal{O}_xU_{t-1}\mathcal{O}_x\cdots U_1\mathcal{O}_xU_0\ket{0}.\] Here, \(\mathcal{O}_x\) is the quantum oracle of \(x\), i.e., the unitary matrix acting on \(\mathbb{C}^m\otimes \mathbb{C}^N \otimes \mathbb{C}^K\) defined by \[\forall (i,u,w)\in [m]\times [N]\times [K]\colon \mathcal{O}_x\ket{i,u,w} \mathrel{\vcenter{:}}= \omega_N^{ux_i}\ket{i,u,w},\] where the \(\ket{i,u,w}\)s form the computational basis of \(\mathbb{C}^m\otimes \mathbb{C}^N \otimes \mathbb{C}^K\) and \(\omega_N \mathrel{\vcenter{:}}= \exp(2\pi\mathrm{i}/N)\) is the \(N\)-th root of unity.

The algorithm finishes by measuring \(\mathbb{C}^K\) in the computational basis, parses the output \(w\in [K]\) as a string, and outputs a substring of \(w\) at a fixed location.²¹ For \(x\in [N]^m\), let \(W_x \mathrel{\vcenter{:}}= \{s\in \Sigma \mid (x,s)\in R\}\) denote the set of all desired outputs associated with \(x\), and let \(\Pi_{\mathop{\mathrm{\mathrm{succ}}}}^x\) be the projector onto all basis states \(\ket{i,u,w}\) such that the substring \(w'\) of \(w\) at the fixed location satisfies \(w' \in W_x\). The success probability of the quantum algorithm on input \(x\in [N]^m\) is then defined by \(\mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}^x\ket{\phi_T}}\right\|^2\).

Following [36], a quantum query algorithm can be viewed as acting on basis states \(\ket{i,u,w}\ket{x}\), where \(x\in [N]^m\) and \(\ket{x} \mathrel{\vcenter{:}}= \bigotimes_{i\in[m]} \ket{x_i}\) is the state on an additional input register. Suppose \(\mathop{\mathrm{\mathcal{D}}}\) is a probability distribution over \([N]^m\), the state of the algorithm at the \(t\)-th step given an input sampled according to \(\mathop{\mathrm{\mathcal{D}}}\) can be represented by \[\label{eq:standard95model95state} \ket{\psi_t^{\mathop{\mathrm{\mathcal{D}}}}} \mathrel{\vcenter{:}}= (U_t\otimes\mathop{\mathrm{\mathbb{I}}})\mathcal{O}(U_{t-1}\otimes\mathop{\mathrm{\mathbb{I}}})\mathcal{O}\cdots (U_1\otimes\mathop{\mathrm{\mathbb{I}}})\mathcal{O}(U_0\otimes\mathop{\mathrm{\mathbb{I}}})(\ket{0}\ket{\mathop{\mathrm{\mathcal{D}}}}),\tag{12}\] where \(\mathcal{O}\) is the standard query operator that maps each basis state \(\ket{i,u,w}\ket{x}\) to \((\mathcal{O}_x\ket{i,u,w})\ket{x}\), and \[\ket{\mathop{\mathrm{\mathcal{D}}}} \mathrel{\vcenter{:}}= \sum_{x\in[N]^m}\sqrt{\mathrm{Pr}[x\leftarrow\mathop{\mathrm{\mathcal{D}}}]}\ket{x}.\]

Let \(\Pi_{\mathop{\mathrm{\mathrm{succ}}}} \mathrel{\vcenter{:}}= \sum_{x\in[N]^m}\Pi_{\mathop{\mathrm{\mathrm{succ}}}}^x\otimes|x\rangle\langle x|\). The success probability of the algorithm on \(\mathop{\mathrm{\mathcal{D}}}\) is defined to be \(\mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\ket{\psi^{\mathop{\mathrm{\mathcal{D}}}}_T}}\right\|\). It is not hard to see that \[\mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\ket{\psi_T^{\mathop{\mathrm{\mathcal{D}}}}}}\right\|^2 = \sum_{x\in[N]^m} \mathrm{Pr}[x\leftarrow\mathop{\mathrm{\mathcal{D}}}]\mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}^x\ket{\psi^x_T}}\right\|^2.\] which shows that \(\mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\ket{\psi_T^{\mathop{\mathrm{\mathcal{D}}}}}}\right\|^2\) equals the expected success probability of the quantum query algorithm when the input is sampled from the distribution \(\mathop{\mathrm{\mathcal{D}}}\).

The recording query framework works with an alternative view of 12 . We follow the prescription of this method described by Hamoudi and Magniez in [2] that specializes to the case where \[\mathop{\mathrm{\mathcal{D}}}= \mathop{\mathrm{\mathcal{D}}}_1 \times \mathop{\mathrm{\mathcal{D}}}_2 \times \dots \times \mathop{\mathrm{\mathcal{D}}}_m\] is a product distribution on \([N]^m\). To reach this alternative view, we first augment the alphabet \([N]\) by an additional character \(\bot\), and extend the action of \(\mathcal{O}\) by defining \[\mathcal{O}\ket{i,u,w}\ket{x} \mathrel{\vcenter{:}}= \ket{i,u,w}\ket{x},\] whenever \(x_i = \bot\). (The lack of change in the above equation explains why \(x_i=\bot\) can be thought of as the algorithm’s lack of knowledge of the value of \(x_i\).)

Now, define \(\ket{\mathop{\mathrm{\mathcal{D}}}_i} \mathrel{\vcenter{:}}= \sum_{y\in[N]}\sqrt{\mathrm{Pr}[y\leftarrow \mathop{\mathrm{\mathcal{D}}}_i]}\ket{y}\) so that the initial state of the input register in the standard query model can be written as \(\ket{\mathop{\mathrm{\mathcal{D}}}} = \bigotimes_{i\in[m]}\ket{\mathop{\mathrm{\mathcal{D}}}_i}\). In the recording query model, the corresponding initial state of the input register in the recording query model is defined to be \(\bigotimes_{i\in[m]}\ket{\bot} = \ket{\bot^m}\).

Then, we define the recording query operator, which is \(\mathop{\mathrm{\mathcal{O}}}\) under a change of basis defined using \(\cal{D}\).

In the recording query model, the state of the quantum query algorithm after the \(t\)-th recording query is defined by \[\label{eq:recording95model95state} \ket{\phi_t^{\mathop{\mathrm{\mathcal{D}}}}} \mathrel{\vcenter{:}}= (U_t\otimes\mathop{\mathrm{\mathbb{I}}}_I)\mathop{\mathrm{\mathcal{R}}}_{\mathop{\mathrm{\mathcal{D}}}}(U_{t-1}\otimes\mathop{\mathrm{\mathbb{I}}}_I)\mathop{\mathrm{\mathcal{R}}}_{\mathop{\mathrm{\mathcal{D}}}}\cdots (U_1\otimes\mathop{\mathrm{\mathbb{I}}}_I)\mathop{\mathrm{\mathcal{R}}}_{\mathop{\mathrm{\mathcal{D}}}}(U_0\otimes\mathop{\mathrm{\mathbb{I}}}_I)(\ket{0}\ket{\bot^m}).\tag{14}\] For convenience, we will often abuse notation and write \(U_i\) for the \(U_i \otimes \mathop{\mathrm{\mathbb{I}}}_I\) in 14 .

The recording query model is particularly useful due to the following facts established in the previous works. First, the recording query model is essentially the same as the standard average-case query model up to a rotation on the input register at the end of the algorithm. Consequently, a measurement on the other registers sees no difference at all. Formally, we have

A crucial but easy-to-see fact in the recording query framework is²²

Moreover, the effect of the recording query operator can be exactly calculated as

30 is due to the “reveal-on-demand” or “lazy-sampling” nature of the recording query operator. 1 formally grounds the intuition that once a value of \(x_i\) has been recorded, later queries should not significantly alter it (note the coefficient on \(\ket{x_i}\) has a large norm).

As we are proving 28, we will henceforth specialize \(\mathop{\mathrm{\mathcal{D}}}\) to be the uniform (product) distribution on \([N]^m = \binom{[n]}{2}^m\). We abbreviate \[\ket{\phi_t},\ket{\psi_t}, \mathop{\mathrm{\mathcal{T}}},\mathop{\mathrm{\mathcal{S}}},\mathop{\mathrm{\mathcal{R}}}\quad \text{to} \quad \ket{\phi_t^{\mathop{\mathrm{\mathcal{D}}}}}, \ket{\psi_t^{\mathop{\mathrm{\mathcal{D}}}}}, \mathop{\mathrm{\mathcal{T}}}_{\mathop{\mathrm{\mathcal{D}}}}, \mathop{\mathrm{\mathcal{S}}}_{\mathop{\mathrm{\mathcal{D}}}}, \mathop{\mathrm{\mathcal{R}}}_{\mathop{\mathrm{\mathcal{D}}}},\] respectively. These states and operators depend on the \(m\) and \(n\) that parametrize \(\mathop{\mathrm{\mathcal{D}}}\), but we leave these parameters implicit for notational convenience.

5.3.1.2 Roadmap for the proof of 28.

Recall that \(x\in \binom{[n]}{2}^m\), we write \(\mathop{\mathrm{\mathcal{G}}}(x)\) for the graph on \(n\) vertices formed by the edges in \(x\). The notation trivially generalizes to \(x\in (\binom{[n]}{2}\cup \{\bot\})^m\). We say \(x\) (or \(\ket{x}\)) records a triangle if \(\mathop{\mathrm{\mathcal{G}}}(x)\) contains a triangle; we say \(x\) (or \(\ket{x}\)) records \(k\) wedges if \(\mathop{\mathrm{\mathcal{G}}}(x)\) contains \(k\) wedges; and so on. Since there is a trivial bijection between \(N= \binom{n}{2}\) and \(\binom{[n]}{2}\), we do not distinguish \([N]\) and \(\binom{[n]}{2}\), as for the recording query framework, the notation \([N]^m\) is arguably more natural. We will assume that \(m = n\). This is without loss of generality since the only property of the regime \(m = \Theta(n)\) that we use in the proof is \(\mathop{\mathrm{\mathrm{maxdeg}}}(x) \leq O(\log(n))\), which is promised with high probability by 26. Nonetheless, we will keep the notation \(m\) and \(n\) separate until we need to use \(m=n\). This is for clarity as most parts of the proof do not use \(m=n\). Indeed, the only places that do are 3 and the few results invoking it, which includes 28.

Our analysis revolves around bounding the norm of the projection of \(\ket{\phi_t}\) onto computational basis states \(\ket{i,u,w}\ket{x}\) where \(x\) records properties key to finding triangles, such as: \(\mathop{\mathrm{\mathcal{G}}}(x)\) contains a large number of high-degree vertices; \(\mathop{\mathrm{\mathcal{G}}}(x)\) contains a large number of wedges; and, of course, \(\mathop{\mathrm{\mathcal{G}}}(x)\) contains a triangle. 1 allows us to carry out our analysis on a query-by-query basis. This discussion motivates the following definitions.

Thus, \(\Lambda_{t,r}\) measures the progress of recording \(r\) wedges in \(t\) queries; while \(\Delta_t\) measures the progress of recording a triangle in \(t\) queries. Our strategy is to first show that a large investment of queries is needed to record many wedges. That is, \(\Lambda_{t,r}\) is negligible when \(t\) is small and \(r\) large. Then, we show that, to record a triangle, a large number of wedges must have been recorded during the execution of the algorithm. That is, \(\Delta_t\) will be negligible as long as \(\Lambda_{t,r}\) remains negligible for a somewhat large \(r\).

A naive implementation of the above strategy falls short of giving the tight bound. One technical challenge is that the \(t\)-th query can, in principle, lead to as many as \(\Omega(t)\) extra wedges being recorded. This result in an overestimate on the wedge progress in each step and therefore an underestimate on the final query lower bound. However, as the input is drawn from the distribution \(\mathop{\mathrm{\mathcal{D}}}\), the underlying graph has a maximum degree of \(O(\log(n))\) with high probability. By excluding graphs with a maximum degree of \(\Omega(\log^2(n))\), we ensure that each query records at most \(\widetilde{O}(1)\) wedges. This motivates

In the next three subsections, we discuss the above three pieces in detail, starting from controlling the high-degree vertices, and then analyzing \(\Lambda_{t,r}\) and \(\Delta_t\).

5.3.2 Excluding high-degree graphs↩︎

A random sparse graph is rarely a high-degree graph. We show how we can exclude these graphs in the recording query framework so that the wedge count does not jump by a large amount at each query. While some aspects of our presentation are tailored to our specific problem, we have made an effort to generalize our proofs so that they can be applied in other contexts.

We start with a generic treatment stated in 2 that enables us to exclude unfavorable events from consideration during the analysis of recording progress, deferring their accounting to the final recording probability. 5 establishes that when the input is sampled from \(\mathop{\mathrm{\mathcal{D}}}\), if a certain event occurs with negligible probability, then no quantum algorithm can reliably record that event. (As mentioned above, we have dropped \(\mathop{\mathrm{\mathcal{D}}}\)-superscripts, \(\mathop{\mathrm{\mathcal{D}}}\)-subscripts, and the identities tensored to the \(U_i\)s for notational convenience.)

5.3.2.1 The Hamming events.

Now we study a rather general situation using the Exclusion Lemma. Consider the product distribution \(\mathop{\mathrm{\mathcal{D}}}= \mathop{\mathrm{\mathcal{D}}}_1 \times \dots \times \mathop{\mathrm{\mathcal{D}}}_m\), where each \(\mathop{\mathrm{\mathcal{D}}}_i\) is over the finite domain \([N]\).

For each \(i\in [m]\), fix some partition \[[N] = \Sigma_0^{(i)}\dot{\cup}\Sigma_1^{(i)}.\] Symbols from \(\Sigma_1^{(i)}\) can be interpreted as a “logical 1” and correspond to the symbols of interest for the \(i\)-th index. We abuse the Hamming weight notation \(|\cdot|\) to apply to \(x\in \Sigma_1^{(1)}\times\cdots\times\Sigma^{(m)}_1\), such that \[\mathopen{}\mathclose{\left|x}\right| \mathrel{\vcenter{:}}= \Bigl|\bigl\{i\in[m] \mid x_i \in \Sigma_1^{(i)}\bigr\}\Bigr|.\] Then we have the natural probability distribution in the form of the product of independent Bernoulli distributions, where the probability \(p_i\) of the \(i\)-th symbol being a logical 1 is \[p_i\mathrel{\vcenter{:}}= \mathrm{Pr}[e\in\Sigma_1^{(i)}\mid e\leftarrow\mathop{\mathrm{\mathcal{D}}}_i].\] We also write \[p\mathrel{\vcenter{:}}=\max_{i\in[m]}p_i.\] The above definition hints at the events that we are going to focus on: \(\mathopen{}\mathclose{\left|x}\right|\) being large. Define the binary-valued logical 0-1 measurement on the \(i\)-th index as \[\Bigl\{\Pi_0^{(i)} = \textstyle\sum_{c\in\Sigma_0^{(i)}}|c\rangle\langle c|, \;\Pi_1^{(i)} = \textstyle\sum_{c\in\Sigma_1^{(i)}}|c\rangle\langle c| \Bigr\}.\]

We first show the operator \(\mathop{\mathrm{\mathcal{S}}}_i\) causes little “leakage" from the logical-\(0\) subspace to the logical-\(1\) subspace by defining the following leakage operator and bounding its norm.

The Chernoff bound tells us that the probability that \(\mathopen{}\mathclose{\left|x}\right|\) is large decays exponentially. We will use the following version of Chernoff bound specialized to i.i.d. Bernoulli random variables.

Now we instantiate the Exclusion Lemma to handle the kind of rare events arising from the large deviation property of i.i.d. random variables. To formally state the result, define the following projectors:

• For \(r\geq0\), let \(\Pi_{\geq r}\) be the projector onto those \(\ket{g}\)s such that \(g\in([N]\cup\{\bot\})^m\) and \(\mathopen{}\mathclose{\left|g}\right|\geq r\).

• For \(r\geq 0\), let \(P_{\geq r}\) be the projector onto those \(\ket{f}\)s such that \(f\in[N]^m\) and \(\mathopen{}\mathclose{\left|f}\right|\geq r\); let \(P_{< r}\) be the projector that projects onto those \(\ket{f}\)s such that \(f\in[N]^m\) and \(\mathopen{}\mathclose{\left|f}\right|< r\).

These projectors look similar but will serve different purposes. The projector \(\Pi_{\geq r}\) will be applied to the input register of the recording query model; while projectors \(P_{\geq r}\) and \(P_{<r}\) will be applied to the input register of the standard query model.

With the above preparation, we are now ready to state the key technical result of this part that allows us to exclude high Hamming-weight inputs (which form the “Hamming event”) during the quantum query algorithm’s execution:

The Mirroring Lemma is intuitive in view of 29 and 1: \(\ket{\phi_t}\) and \(\ket{\psi_t}\) are “mirror images” of each other up to the change of \(\mathop{\mathrm{\mathcal{T}}}\) whose effect is controllable, and \(\ket{\psi_t}\) clearly cannot record a rare event with a probability larger than that of the event happening. Now we instantiate the lemma into the following quantitative statement that is useful in our setting.

5.3.2.2 Excluding high-degree graphs.

Recall that \(\ket{\phi_t}\) depends on the \(m\) and \(n\) that specify the distribution \(\mathop{\mathrm{\mathcal{D}}}\). When \(m=n\), the previous lemma implies that only a tiny fraction of basis states \(\ket{i,u,w}\ket{x}\) in the support \(\ket{\phi_t}\) can have \(x\) recording a high-degree vertex, irrespective of the value of \(t\). More formally, we have the following corollary.

5.3.3 Progress in recording wedges↩︎

To reliably record a triangle, there must be many wedges recorded along the way. In this part, we bound the progress of a quantum query algorithm in recording wedges. Recall the measure of progress of recording at least \(r\) wedges in \(t\) queries is defined as \[\Lambda_{t,r} \mathrel{\vcenter{:}}= \mathopen{}\mathclose{\left\|\Pi^{ \begin{tikzpicture}[scale=0.1,baseline=(current bounding box.center)] \draw (0,0) -- (1,2) -- (2,0); \end{tikzpicture}}_{[r,\infty)}\ket{\phi_t}}\right\|.\]

As mentioned previously, high-degree vertices can potentially cause an overestimate of the power of quantum algorithms to record wedges. We apply the Exclusion Lemma to suppress these high-degree vertices. In particular, invoking 2 with \(\Pi_i\mathrel{\vcenter{:}}= 0\), \(\Pi_i'\mathrel{\vcenter{:}}= \Pi_{\mathrm{Bad}}\) for all \(i\in [t-1]\) and \(\Pi_{\mathop{\mathrm{\mathrm{rec}}}} \mathrel{\vcenter{:}}= \Pi^{ \begin{tikzpicture}[scale=0.1,baseline=(current bounding box.center)] \draw (0,0) -- (1,2) -- (2,0); \end{tikzpicture}}_{[r,\infty)}\) gives \[\label{eq:vtr95good95bad} \Lambda_{t,r} \leq \mathopen{}\mathclose{\left\|\Pi^{ \begin{tikzpicture}[scale=0.1,baseline=(current bounding box.center)] \draw (0,0) -- (1,2) -- (2,0); \end{tikzpicture}}_{[r,\infty)}\ket{\phi'_t}}\right\| + \sum_{i=1}^{t-1}\mathopen{}\mathclose{\left\|\Pi_{\mathrm{Bad}}\ket{\phi_i}}\right\|,\tag{24}\] where \(\ket{\phi'_t}\) is the (possibly unnormalized) state defined by \[\ket{\phi'_t} \mathrel{\vcenter{:}}= U_t\mathop{\mathrm{\mathcal{R}}}(\mathop{\mathrm{\mathbb{I}}}-\Pi_{t-1}')U_{t-1}\mathop{\mathrm{\mathcal{R}}}(\mathop{\mathrm{\mathbb{I}}}-\Pi_{t-2}')U_{t-2}\mathop{\mathrm{\mathcal{R}}}\cdots (\mathop{\mathrm{\mathbb{I}}}-\Pi_1')U_1\mathop{\mathrm{\mathcal{R}}}U_0(\ket{0}\ket{\bot^m}).\] The term \(\sum_{i=1}^{t-1}\mathopen{}\mathclose{\left\|\Pi_{\mathrm{Bad}}\ket{\phi_i}}\right\|\) in 24 can be bounded using 3. Therefore, to bound \(\Lambda_{t,r}\), it suffices to bound \[\Lambda'_{t,r} \mathrel{\vcenter{:}}= \mathopen{}\mathclose{\left\|\Pi^{ \begin{tikzpicture}[scale=0.1,baseline=(current bounding box.center)] \draw (0,0) -- (1,2) -- (2,0); \end{tikzpicture}}_{[r,\infty)}\ket{\phi'_t}}\right\|.\]

Solving the wedges progress recurrence, we obtain

5.3.4 Progress in recording a triangle↩︎

We move on to bounding the progress of a quantum query algorithm in recording a triangle. Recall that we defined the progress measure of finding a triangle within \(t\) queries \[\Delta_t\mathrel{\vcenter{:}}= \mathopen{}\mathclose{\left\|\Pi^\triangle\ket{\phi_t}}\right\|.\]

Let \[r^* \mathrel{\vcenter{:}}= \biggl\lceil \frac{n^{4/7}}{\log^{6/7}(n)}\biggr\rceil \cdot 2\ceil{\log(n)}^2.\] and for \(t\in \mathbb{Z}_{[0,T]}\), define \[\label{eq:phit95star} \ket{\phi_t^*}\mathrel{\vcenter{:}}= U_t\mathop{\mathrm{\mathcal{R}}}(\mathop{\mathrm{\mathbb{I}}}-\Pi^*)U_{t-1}\mathop{\mathrm{\mathcal{R}}}(\mathop{\mathrm{\mathbb{I}}}-\Pi^*)U_{t-2}\mathop{\mathrm{\mathcal{R}}}\cdots (\mathop{\mathrm{\mathbb{I}}}-\Pi^*)U_1\mathop{\mathrm{\mathcal{R}}}U_0(\ket{0}\ket{\bot^m}),\tag{30}\] where \(\Pi^*\) denotes the projector onto every basis state \(\ket{i,u,w}\ket{x}\) such that \(\mathop{\mathrm{\mathcal{G}}}(x)\) contains at least \(r^*\) wedges. Then, define \[\label{eq:triangleprogress95star} \Delta_t^*\mathrel{\vcenter{:}}= \mathopen{}\mathclose{\left\|\Pi^\triangle\ket{\phi_t^*}}\right\|.\tag{31}\]

We can bound \(\Delta_t\) by bounding \(\Delta_t^*\) due to the next lemma.

5.3.5 Completing the proof of 28↩︎

To finish the proof, we use the next lemma, which bounds the probability of the algorithm succeeding even if it does not record a triangle. Intuitively, if the algorithm does not record a triangle, it should not be significantly better at finding a triangle than guessing at random. The lemma is standard in the recording query framework — indeed, our proof is based on [2] — but we include it for completeness.

Let \(\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\) denote the projector onto basis states \(\ket{i,u,w}\ket{x}\) such that \(w\) contains an output substring (i.e., a substring located at some fixed output register) of the form \((a_1,a_2,a_3,b_1,b_2,b_3) \in [m]^3 \times \binom{[n]}{2}^3\) where the \(a_i\)s are distinct, the \(b_i\)s form a triangle, and \(x_{a_i} = b_i\) for all \(i\).

With the above lemma, 28 becomes a simple corollary. If \(T = o(n^{5/7}/\log^{4/7}(n))\), we have \[\label{eq:final95step} \mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\ket{\psi_T}}\right\| = \mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\mathop{\mathrm{\mathcal{T}}}\ket{\phi_T}}\right\|\leq \mathopen{}\mathclose{\left\|\Pi^\triangle \ket{\phi_T}}\right\| + \mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\mathop{\mathrm{\mathcal{T}}}(\mathop{\mathrm{\mathbb{I}}}-\Pi^\triangle)\ket{\phi_T}}\right\| = o(1),\tag{35}\] where we used 11 to bound the first term and 12 to bound the second term.

5.4 Triangle finding upper bound↩︎

In this section, we prove the following theorem.

We prove 31 by adapting Belovs’s learning graph algorithm for \(3\)-distinctness [3]. A key challenge in Belovs’s work is the presence of faults, as intuitively described in the introduction. At a technical level, faults are violations of the feasibility conditions in the semi-definite program characterizing quantum query complexity. Belovs found that directly using a learning graph algorithm of the type in his earlier work [6] led to faults. In [3], for \(k\)-distinctness, Belovs devised a technique based on the inclusion-exclusion principle to “error-correct” these faults at the cost of an exponential-in-\(k\) factor, which is constant for constant \(k\).

Technically speaking, in \(3\)-distinctness, at most one fault can occur because negative instances are limited to having \(2\)-collisions, and once one index of a \(2\)-collision is fixed, only its second index could possibly contribute a fault. In our problem, however, a single edge can belong to up to \(2(d - 1)\) wedges, where \(d\) is the maximum degree of the graph, introducing the possibility of multiple faults. Fortunately, Belovs’s learning graph algorithm for \(k\)-distinctness for general \(k\) shows how inclusion-exclusion can be used to handle multiple faults. We adapt this technique to our problem and it represents the main change we make to his \(3\)-distinctness algorithm. The additional changes we make, such as explicitly defining the graph, replacing the concept of “arcs taken” with “active arcs,” and elaborating on somewhat opaque definitions, are primarily for improved clarity and accessibility. These adjustments do not alter the underlying algorithm and are not strictly necessary.

In summary, our algorithm for triangle finding is closely aligned with Belovs’s original learning graph algorithm for \(3\)-distinctness, which highlights the deep structural similarities between \(3\)-distinctness and triangle finding.

5.4.1 Setting up proof of 31↩︎

When \(d\geq \log(m)\), the trivial bound \(Q(\mathop{\mathrm{\mathsf{Triangle}}}_m)\leq m\) applies, ensuring 31 is satisfied. When \(d\leq \log(m)\), we employ the learning graph method along with 27 to confirm the validity of 31.

5.4.1.1 Adversary bound and learning graphs.

In [3], Belovs used a learning graph approach to construct matrices for the adversary bound. For every function \(g:\mathcal{D}\subseteq \Sigma^m\to\{0,1\}\), the adversary bound \(\mathrm{Adv}^{\pm}(g)\) satisfies the following theorem.

\(\mathrm{Adv}^{\pm}(g)\) can be formulated as the following semi-definite program [41]: \[\begin{align} {2} &\text{minimize}\qquad && \max_{x \in \mathcal{D}} \sum_{j \in [m]} X_j[x,x],\tag{39}\\ &\text{subject to}\qquad && \sum_{j \in [m] \colon x_j \neq y_j} X_j[x,y] = 1\qquad \text{if } g(x) \neq g(y);\tag{40}\\ & &&0 \leq X_j \in \mathbb{C}^{\mathop{\mathrm{\mathcal{D}}}\times \mathop{\mathrm{\mathcal{D}}}} \quad \text{for all j \in [m]}. \end{align}\]

Every valid construction of \(\{X_j\}_{j\in[m]}\) provides an upper bound for \(\mathrm{Adv}^\pm(g)\) and, consequently, an upper bound for \(Q(g)\) up to constant factors. We construct \(\{X_j\}_{j\in[m]}\) using the learning graph framework, following a similar approach to that in [3]. Specifically, for each arc \(A_j^{R,S}\) in the learning graph from vertex \(R\) and to vertex \(S\) where \(R\) and \(S\) uniquely determines \(j\) (to be shown in detail later), we associate a positive semi-definite matrix \(X_j^{R,S}\), and define \[X_j \mathrel{\vcenter{:}}= \sum_{R,S} X_j^{R,S}.\]

5.4.2 Learning graph construction↩︎

We first describe the construction of the learning graph. For simplicity, we use \(f\) to denote \(\mathop{\mathrm{\mathsf{Triangle}}}_{m,d}\). The vertices of the learning graph are \[\dot{\bigcup}_{i\in\{0,1,2,3,4\}} V^{(i)},\] where a vertex \(S^{(i)}\) in \(V^{(i)}\) is (labelled by) an array of length \((2^{2d} - 1) + 2d\) containing pairwise-disjoint subsets of \([m]\); we refer to entries of \(S^{(i)}\) by \[S^{(i)} = (S_1^{(i)}(\Gamma),S_2^{(i)}(\gamma))_{\varnothing\neq \Gamma \subseteq [2d],\, \gamma\in [2d]} = (S_1^{(i)}(\{1\}),\dots, S_1^{(i)}([2d]), S_2^{(i)}(1), \dots, S_2^{(i)}(2d)).\] We further impose conditions on the sizes of these sets using some \(r_1,r_2\in \mathbb{N}\) that will be chosen later, at the end of 5.4.5. To describe these conditions, it is convenient to write \(\mu(A)\) for the minimum element of a finite non-empty subset \(A \subset \mathbb{Z}\).

First, \(V^{(1)}\) consists of all vertices \(S^{(1)}\) such that \[\forall \varnothing\neq \Gamma\subseteq[2d], \gamma\in[2d], \quad \mathopen{}\mathclose{\left|S_1^{(1)}(\Gamma)}\right| = r_1 \quad \text{and} \quad \mathopen{}\mathclose{\left|S_2^{(1)}(\gamma)}\right| = r_2.\] Then, for \(i\in \{2,3,4\}\), we impose that the set \(V^{(i)}\) can be partitioned as \(V^{(i)} = \dot{\cup}_{\varnothing\neq \Gamma \subseteq[2d]} V^{(i)}(\Gamma)\) such that

• \(V^{(2)}(\Gamma)\) consists of all vertices \(S^{(2)}\) with \[\mathopen{}\mathclose{\left|S_1^{(2)}(\Gamma)}\right| = r_1+1, \qquad \forall \Gamma'\neq \Gamma,\mathopen{}\mathclose{\left|S_1^{(2)}(\Gamma')}\right| = r_1,\qquad \forall \gamma\in[2d], \mathopen{}\mathclose{\left|S_2^{(2)}(\gamma)}\right| = r_2.\]

• \(V^{(3)}(\Gamma)\) consists of all vertices \(S^{(3)}\) such that \[\mathopen{}\mathclose{\left|S_1^{(3)}(\Gamma)}\right| = r_1+1, \qquad \forall \Gamma'\neq \Gamma,\mathopen{}\mathclose{\left|S_1^{(3)}(\Gamma')}\right| = r_1,\] and \[\mathopen{}\mathclose{\left|S_2^{(3)}(\mu(\Gamma))}\right| = r_2+1,\qquad \forall \gamma\neq \mu(\Gamma),\mathopen{}\mathclose{\left|S_2^{(3)}(\gamma)}\right| = r_2.\]

• \(V^{(4)}(\Gamma)\) consists of all vertices \(S^{(4)}\) such that \[\mathopen{}\mathclose{\left|S_1^{(4)}(\Gamma)}\right| = r_1+1, \qquad \forall \Gamma'\neq \Gamma,\mathopen{}\mathclose{\left|S_1^{(4)}(\Gamma')}\right| = r_1,\] and \[\mathopen{}\mathclose{\left|S_2^{(4)}(\mu(\Gamma))}\right| = r_2+2,\qquad \forall \gamma\neq \mu(\Gamma),\mathopen{}\mathclose{\left|S_2^{(4)}(\gamma)}\right| = r_2.\]

For each vertex \(R\) in the learning graph, define \[\bigcup R_1\mathrel{\vcenter{:}}= \bigcup_{\varnothing\neq \Gamma\subseteq[2d]}R_1(\Gamma), \quad \bigcup R_2\mathrel{\vcenter{:}}= \bigcup_{\gamma\in[2d]}R_2(\gamma), \quad \text{and} \quad \bigcup R\mathrel{\vcenter{:}}= \bigcup R_1 \cup \bigcup R_2.\] We refer to indices contained in the first, second, and third sets as having been loaded in \(R_1\), \(R_2\), and \(R\), respectively. If there is an arc from vertex \(R\) to vertex \(S\) in the learning graph, by the construction in the following paragraphs, it must satisfy \(\bigcup S = \bigcup R \cup \{j\}\). We denote the arc as \(A^{R,S}_j\), and accordingly, we say \(A^{R,S}_j\) is associated with the loading of \(j\).

There exists a unique vertex \(R^{(0)}\in V^{(0)}\) such that \(\bigcup R^{(0)} = \varnothing\). We refer to this vertex as the source, denoted by \(\varnothing\). Each vertex \(R^{(1)}\in V^{(1)}\) loads exactly \(r \mathrel{\vcenter{:}}= r_1\cdot (2^{2d}-1) + r_2\cdot(2d)\) indices. We fix an arbitrary ordering \(t_1,\dots, t_r\) of indices in \(\bigcup R^{(1)}\) such that all indices in \(\bigcup R^{(1)}_1\) precede those in \(\bigcup R^{(1)}_2\). There exists a length-\(r\) path from the source \(\varnothing\) to \(R^{(1)}\), with all intermediate vertices lying in \(V^{(0)}\). Along this path, the element \(t_i\) is loaded on the \(i\)-th arc for \(i\in[r]\) in stages I.1 and I.2. Specifically,

• If \(t_i\in \bigcup R_1^{(1)}\), it is loaded in stage I.1,

• If \(t_i\in \bigcup R_2^{(1)}\), it is loaded in stage I.2.

All such paths are disjoint except at the source \(\varnothing\). Therefore, there are \(r\bigl|V^{(1)}\bigr|\) arcs in stages I.1 and I.2 in total.

In stage II.1, for each \(R^{(1)}\in V^{(1)}\), \(j\not\in\bigcup R^{(1)}\) and \(\varnothing\neq \Gamma\subseteq[2d]\), there is an arc, denoted \(A^{R^{(1)}, R^{(2)}}_j\), from \(R^{(1)}\) to \(R^{(2)} \in V^{(2)}(\Gamma)\) defined by \[\mathopen{}\mathclose{\left\{\begin{alignedat}{3} &R^{(2)}_1(\Gamma) &&= R^{(1)}_1(\Gamma)\cup\{j\},&&\\ &R^{(2)}_1(\Gamma') &&= R^{(1)}_1(\Gamma'),&& \text{for all \varnothing\neq \Gamma'\subseteq [2d] s.t. \Gamma'\neq \Gamma},\\ &R^{(2)}_2(\gamma) &&= R^{(1)}_2(\gamma),&&\text{for all \gamma\in[2d].} \end{alignedat}}\right.\]

In stage II.2, for each \(\varnothing\neq \Gamma\subseteq[2d]\), \(R^{(2)}\in V^{(2)}(\Gamma)\), and \(j\not\in\bigcup R^{(2)}\), there is an arc, denoted \(A^{R^{(2)},R^{(3)}}_j\), from \(R^{(2)}\) to \(R^{(3)} \in V^{(3)}(\Gamma)\) defined by \[\mathopen{}\mathclose{\left\{\begin{alignedat}{3} & R^{(3)}_1(\Gamma') &&= R^{(2)}_1(\Gamma'),\qquad &&\text{for all \varnothing\neq \Gamma'\subseteq[2d]},\\ &R^{(3)}_2(\gamma) &&= R^{(2)}_2(\gamma),&& \text{for all \gamma \neq \mu(\Gamma)},\\ &R^{(3)}_2(\mu(\Gamma)) &&= R^{(2)}_2(\mu(\Gamma))\cup\{j\}.&& \end{alignedat}}\right.\]

In stage II.3, for each \(\varnothing\neq \Gamma\subseteq[2d]\), \(R^{(3)}\in V^{(3)}(\Gamma)\), and \(j\not\in\bigcup R^{(3)}\), there is an arc, denoted \(A^{R^{(3)},R^{(4)}}_j\), from \(R^{(3)}\) to \(R^{(4)} \in V^{(4)}(\Gamma)\) defined by \[\mathopen{}\mathclose{\left\{\begin{alignedat}{3} & R^{(4)}_1(\Gamma') &&= R^{(3)}_1(\Gamma'),\qquad &&\text{for all \varnothing\neq \Gamma'\subseteq[2d]},\\ &R^{(4)}_2(\gamma) &&= R^{(3)}_2(\gamma),&& \text{for all \gamma \neq \mu(\Gamma)},\\ &R^{(4)}_2(\mu(\Gamma)) &&= R^{(3)}_2(\mu(\Gamma))\cup\{j\}.&& \end{alignedat}}\right.\]

5.4.3 Active arcs↩︎

For every \(x\in f^{-1}(1)\), let \(\mathcal{C}(x) = \{a_1, a_2, a_3\}\subseteq[m]\) be a specific certificate for \(x\) such that \(a_1<a_2<a_3\) and \(x_{a_1}\), \(x_{a_2}\), and \(x_{a_3}\) form a triangle.

We say \(R^{(1)}\in V^{(1)}\) is consistent with \(x\in f^{-1}(1)\) if edges indexed by \(\mathcal{C}(x)\) are vertex disjoint from edges indexed by \(\bigcup R^{(1)}\). Let \(n_x\) be the number of \(R^{(1)}\in V^{(1)}\) that are consistent with \(x\), and define \[q\mathrel{\vcenter{:}}= \bigl(\min_{x\in f^{-1}(1)}\{n_x\}\bigr)^{-1},\] so that for all \(x\in f^{-1}(1)\), there exist at least \(q^{-1}\) vertices in \(V^{(1)}\) that are consistent with \(x\). By 27, when \(rd\leq o(m)\) — a condition satisfied since we only need to consider \(d\leq\log_2(m)\) and use the \(r\) specified in 5.4.5 — it follows that \(q^{-1}\geq\Omega(\bigl|V^{(1)}\bigr|)\).

Let \(\mathrm{Cst}(x)\) denote a fixed but arbitrary set of \(q^{-1}\) vertices \(R^{(1)}\in V^{(1)}\) that are consistent with \(x\). For each \(R^{(1)}\in \mathrm{Cst}(x)\), \(\mathrm{Act}(x,R^{(1)})\) is a set of active arcs consisting of the following arcs:

• In stage I.1 and I.2, all arcs along the unique shortest length \(r\) path from source \(\varnothing\) to \(R^{(1)}\).

• In stage II.1, all arcs from \(R^{(1)}\) that loads \(a_1\) into \(R^{(1)}\). Notice that there are \(2^{2d}-1\) such arcs, one for each choice of \(\varnothing\neq \Gamma\subseteq [2d]\).

• In stage II.2, for each vertex \(R^{(2)}\in V^{(2)}\) that has an incoming active arc from \(\mathrm{Act}(x,R^{(1)})\), the arc that loads \(a_2\) into \(R^{(2)}\).

• In stage II.3, for each vertex \(R^{(3)}\in V^{(3)}\) that has an incoming active arc from \(\mathrm{Act}(x,R^{(1)})\), the arc that loads \(a_3\) into \(R^{(3)}\).

Notice that in stage II.2 and II.3, for each vertex that has an incoming active arc, there is only one outgoing active arc, so the total number of active arcs in stages II.2 and II.3 is \(2(2^{2d}-1)\).

Lastly, the set of all active arcs of \(x\) is defined by \[\mathrm{Act}(x)\mathrel{\vcenter{:}}= \dot{\bigcup}_{R^{(1)}\in \mathrm{Cst}(x)}\mathrm{Act}(x,R^{(1)}).\]

5.4.4 Matrices for the adversary bound↩︎

For every vertex \(R\) in the learning graph, an assignment on \(R\) refers to a function \(\alpha_R: \bigcup R\to \binom{[n]}{2}\cup\{*\}\) such that:

1. for all \(j\in \bigcup R_1\), \[\alpha_R(j)\neq *;\]

2. for all \(\gamma\in [2d]\) and \(j\in R_2(\gamma)\), \[\alpha_R(j)\in\{*\}\cup\Bigl\{e\in \textstyle\binom{[n]}{2}\Bigm| \exists k\in \bigcup_{\Gamma\ni \gamma}R_1(\Gamma)\text{ s.t. e is incident to \alpha_R(k)} \Bigr\}.\] Note that the special symbol \(*\) is not incident to any edge.

We say an input \(z\in \binom{[n]}{2}^m\) satisfies assignment \(\alpha_{R}\) if, for all \(t\in \bigcup R\), \[\label{eq:alpha95def} \alpha_{R}(t) = \begin{cases} z_t, &\text{if t\in \bigcup R_1},\\ z_t, &\text{if t\in R_2(\gamma) and \exists k\in \bigcup_{\Gamma\ni \gamma}R_1(\Gamma) s.t. z_t is incident to z_k},\\ *, &\text{otherwise}. \end{cases}\tag{41}\] For each vertex \(R\) in the learning graph, we write \(\alpha_R^x\) for the unique assignment on \(R\) that \(x\) satisfies. We say arc \(A^{R,S}_j\) uncovers \(j\) if \(\alpha_S^x(j)\neq *\). We say inputs \(x,y\in \binom{[n]}{2}^m\) agree on \(R\) if they satisfy \(\alpha_R^x = \alpha_R^y\); we also say they agree on a subset of \(\bigcup R\) if the restrictions of \(\alpha_R^x\) and \(\alpha_R^y\) to that subset equal.

Define \[X_j^{R,S}\mathrel{\vcenter{:}}= \sum_{\alpha_R} Y_{\alpha_R},\] where the summation is over all assignments \(\alpha_R\) on \(R\).

For each arc \(A_j^{R,S}\) in stage I.1, define \(Y_{\alpha_R}\mathrel{\vcenter{:}}= q\psi_{\alpha_R}\psi_{\alpha_R}^\dagger\), where \(\psi_{\alpha_R}\) is a real vector indexed by \(\binom{[n]}{2}^m\) and defined entry-wise by \[\psi_{\alpha_R}[z] \mathrel{\vcenter{:}}= \begin{cases} 1/\sqrt{w}, & \text{if f(z)=1, z satisfies \alpha_R, and A^{R,S}_j\in \mathrm{Act}(z)},\\ \sqrt{w}, & \text{if f(z)=0, and z satisfies \alpha_R},\\ 0,&\text{otherwise.} \end{cases}\] Here, \(w\) is a positive real number that will be specified later. With the above definition, we see that \(X_j^{R,S}\) consists of blocks of the form: \[\label{X95block95form95I461} \renewcommand{\arraystretch}{1.25} \begin{array}{c|c|c} & x & y \\ \hline x & q/w & q \\ \hline y & q & qw \end{array}\tag{42}\] where \(x\in f^{-1}(1)\), \(y\in f^{-1}(0)\), \(A^{R,S}_j\in \mathrm{Act}(x)\), and both \(x\) and \(y\) agree on \(R\).

For arcs \(A_j^{R,S}\) in stage I.2, define \(Y_{\alpha_R}\mathrel{\vcenter{:}}= q(\psi_{\alpha_R}\psi_{\alpha_R}^\dagger+\phi_{\alpha_R}\phi_{\alpha_R}^\dagger)\) where \(\psi_{\alpha_R}\) and \(\phi_{\alpha_R}\) are real vectors indexed by \(\binom{[n]}{2}^m\) and defined entry-wise by \[\psi_{\alpha_R}[z] \mathrel{\vcenter{:}}= \begin{cases} 1/\sqrt{w_1}, & \text{if f(z)=1, \alpha_S^z(j)\neq*, z satisfies \alpha_R, and A^{R,S}_j\in \mathrm{Act}(z)},\\ \sqrt{w_1}, & \text{if f(z)=0, and z satisfies \alpha_R},\\ 0,&\text{otherwise;} \end{cases}\] and \[\phi_{\alpha_R}[z] \mathrel{\vcenter{:}}= \begin{cases} 1/\sqrt{w_0}, & \text{if f(z)=1, \alpha_S^z(j)=*, z satisfies \alpha_R, and A^{R,S}_j\in \mathrm{Act}(z)},\\ \sqrt{w_0}, & \text{if f(z)=0, \alpha_S^z(j)\neq*, and z satisfies \alpha_R},\\ 0, & \text{otherwise.} \end{cases}\] Here, \(w_0\) and \(w_1\) are positive real numbers that will be specified later. With the above definition, we see that \(X_j^{R,S}\) consists of blocks of the form: \[\label{X95block95form95I462} \begin{array}{l|c|c|c|c} & x: x_j =\alpha_S^x(j)\neq * & x: \alpha_S^x(j)= * & y: y_j =\alpha_S^y(j)\neq * & y: \alpha_S^y(j)= * \\ \hline x: x_j =\alpha_S^x(j)\neq * & q/w_1 & 0 & q & q \\ \hline x: \alpha_S^x(j)= * & 0 & q/w_0 & q & 0 \\ \hline y: y_j =\alpha_S^y(j)\neq * & q & q & q(w_0 + w_1) & qw_1 \\ \hline y: \alpha_S^y(j)= * & q & 0 & qw_1 & qw_1 \\ \end{array}\tag{43}\] where \(x\in f^{-1}(1)\), \(y\in f^{-1}(0)\), \(A^{R,S}_j\in \mathrm{Act}(x)\), and both \(x\) and \(y\) agree on \(R\).

For arcs \(A_j^{R,S}\) in stage II.\(s\) where \(s\in[3]\), there exists a unique \(\varnothing\neq \Gamma\subseteq[2d]\) such that \(S\in V^{(s+1)}(\Gamma)\). Define \(Y_{\alpha_R}\mathrel{\vcenter{:}}= q\psi_{\alpha_R}\psi_{\alpha_R}^\dagger\) where \[\psi_{\alpha_R}[z] \mathrel{\vcenter{:}}= \begin{cases} 1/\sqrt{w_2},& \text{if f(z)=1, z satisfies \alpha_R, and A_j^{R,S}\in \mathrm{Act}(z)},\\ (-1)^{1+\mathopen{}\mathclose{\left|\Gamma}\right|}\sqrt{w_2}, & \text{if f(z)=0, and z satisfies \alpha_R},\\ 0,&\text{otherwise.} \end{cases}\] \(X_j^{R,S}\) consists of blocks of the form: \[\label{X95block95form95II} \renewcommand{\arraystretch}{1.25} \begin{array}{c|c|c} & x & y \\ \hline x & q/w_2 & (-1)^{1+\mathopen{}\mathclose{\left|\Gamma}\right|}q \\ \hline y & (-1)^{1+\mathopen{}\mathclose{\left|\Gamma}\right|}q & qw_2 \end{array}\tag{44}\] where \(x\in f^{-1}(1)\), \(y\in f^{-1}(0)\), \(A^{R,S}_j\in \mathrm{Act}(x)\), and both \(x\) and \(y\) agree on \(R\).

5.4.5 Complexity↩︎

We show \(Q(\mathop{\mathrm{\mathsf{Triangle}}}_{m,d}) = O(2^{(12/7)d}d^{3/7}m^{5/7})\) by computing 39 . Define \(W\) as the maximum number of wedges in any input to \(\mathop{\mathrm{\mathsf{Triangle}}}_{m,d}\). Since the graph has maximum degree \(d\), and each edge in the graph contributes to at most \(2(d-1)\) wedges, we have \(W\leq O(md)\).

1. For stage I.1, we set the weight \(w=1\) for all arcs in this stage. There are \(r_1(2^{2d}-1)\bigl|V^{(1)}\bigr|\) arcs in this stage. By 42 , each of them contributes \(\max\{qw, q/w\} = q\) to the complexity, so the complexity of this stage is \(r_1(2^{2d}-1)\bigl|V^{(1)}\bigr|q = O(2^{2d}r_1)\).

2. For stage I.2, there are \(2dr_2\bigl|V^{(1)}\bigr|\) arcs in this stage. For each input \(z\), we need to bound the number of arcs that can uncover an element, so we get a refined bound on the contribution from 43 . Suppose such an arc in this stage is on the shortest length-\(r\) path from source \(\varnothing\) to \(R^{(1)}\in V^{(1)}\), and is uncovering \(j\) in \(R_2^{(1)}(\gamma)\) for some \(\gamma\in[2d]\), then, \(z_j\) must form a wedge with \(z_i\) for some \(i\in R^{(1)}_1(\Gamma)\) and \(\gamma\in \Gamma\subseteq[2d]\). The number of such ordered tuples \((i,j)\) is at most \(2W\), and the number of vertices in stage I.2 that loads \(j\) in its outgoing arc and has loaded \(i\) in stage I.1 is upper bounded by \[(2^{2d}-1)(2d)\binom{m-2}{r_1-1,\underbrace{r_1,\cdots,r_1}_{2^{2d}-2},r_2-1,\underbrace{r_2,\cdots,r_2}_{2d-1}} = O\Bigl(\frac{r_1r_2d2^{2d}}{m^2}\bigl|V^{(1)}\bigr|\Bigr).\]

   Therefore, for a negative input, by 43 , stage I.2’s contribution to the complexity is \[O\Bigl(qw_0W\frac{r_1r_2d2^{2d}}{m^2}\bigl|V^{(1)}\bigr|+qw_12dr_2\bigl|V^{(1)}\bigr|\Bigr)=O\Bigl(\frac{r_1r_2d^22^{2d}}{m}w_0+r_2dw_1\Bigr);\] and for a positive input, by 43 , stage I.2’s contribution to the complexity is \[O\Bigl(\frac{q}{w_1}W\frac{r_1r_2d2^{2d}}{m^2}\bigl|V^{(1)}\bigr|+\frac{q}{w_0}2dr_2\bigl|V^{(1)}\bigr|\Bigr)=O\Bigl(\frac{r_1r_2d^22^{2d}}{mw_1}+\frac{r_2d}{w_0}\Bigr).\] If we set \(w_0=\frac{1}{2^d}\sqrt{\frac{m}{r_1d}}\), and \(w_1 = 1/w_0\), the total contribution to the complexity is \(O(r_2d^{3/2}2^d\sqrt{\frac{r_1}{m}})\).

3. For stage II,

   • The total number of arcs in stage II.1 is \[(m-r)(2^{2d}-1)\bigl|V^{(1)}\bigr|\leq O\bigl(2^{2d}m\bigl|V^{(1)}\bigr|\bigr).\]

   • The total number of arcs in stage II.2 is \[(m-r-1)\bigl|V^{(2)}\bigr| = \frac{(m-r-1)(m-r)(2^{2d}-1)\bigl|V^{(1)}\bigr|}{r_1+1},\] since each vertex in \(V^{(1)}\) has \((m-r)(2^{2d}-1)\) outgoing arcs into \(V^{(2)}\), and each vertex in \(V^{(2)}\) has \(r_1+1\) incoming arcs from \(V^{(1)}\). There are \(O\mathopen{}\mathclose{\left(2^{2d}m^2\bigl|V^{(1)}\bigr|/r_1}\right)\) arcs in this stage.

   • The total number of arcs in stage II.3 is \[(m-r-2)\bigl|V^{(3)}\bigr| = \frac{(m-r-2)(m-r-1)(m-r)(2^{2d}-1)\bigl|V^{(1)}\bigr|}{(r_1+1)(r_2+1)},\] since each vertex in \(V^{(2)}\) has \(m-r-1\) outgoing arcs into \(V^{(3)}\), and each vertex in \(V^{(3)}\) has \(r_2+1\) incoming arcs from \(V^{(2)}\). There are \(O(2^{2d}m^3\bigl|V^{(1)}\bigr|/(r_1r_2))\) arcs in this stage.

   For every negative input, by 44 , each arc contributes \(qw_2\) to the complexity, so the total contribution is \[O\biggl(\frac{2^{2d}m^3\bigl|V^{(1)}\bigr|}{r_1r_2}qw_2\biggr) = O\biggl(\frac{2^{2d}m^3w_2}{r_1r_2}\biggr).\]

   For every positive input, there are exactly \(3q^{-1}(2^{2d}-1)\) active arcs in stage II, by 44 , each of them contributes \(q/w_2\) to the complexity, so the total contribution is \[\frac{3(2^{2d}-1)}{q}\cdot \frac{q}{w_2} = \frac{3(2^{2d} -1)}{w_2} \leq O\mathopen{}\mathclose{\left(\frac{2^{2d}}{w_2}}\right).\]

   To balance the contribution from negative inputs and positive inputs, we can set \(w_2=\sqrt{r_1r_2/m^3}\) so that the total contribution in stage II is \[O\bigl(2^{2d}\sqrt{m^3/(r_1r_2)}\bigr).\]

The total complexity of all stages is \[O\biggl(2^{2d}r_1 + r_2d^{3/2} \, 2^d\sqrt{\frac{r_1}{m}} + 2^{2d}\sqrt{\frac{m^3}{r_1r_2}}\biggr).\] To balance the summands, we set \(r_1 = \ceil{m^{5/7}d^{3/7}/2^{(2/7)d}}\) and \(r_2 = \ceil{2^{(6/7)d}m^{6/7}/d^{9/7}}\), which leads to a complexity of \(O(2^{(12/7)d}d^{3/7}m^{5/7})\).

5.4.6 Feasibility↩︎

Fix two inputs \(x\in f^{-1}(1)\) and \(y\in f^{-1}(0)\), to prove 40 holds, it is equivalent to show \[\sum_{A_j^{R,S} \in \mathrm{Act}(x) \colon x_j \neq y_j} X_j^{R,S}[x,y] = 1.\] Since \(\mathrm{Act}(x)= \dot{\bigcup}_{R^{(1)}\in \mathrm{Cst}(x)}\mathrm{Act}(x,R^{(1)})\), it suffices to prove \[\label{eq:feasibility} \sum_{A_j^{R,S} \in \mathrm{Act}(x,R^{(1)}) \colon x_j \neq y_j} X_j^{R,S}[x,y] = \frac{1}{\mathopen{}\mathclose{\left|\mathrm{Cst}(x)}\right|} = q,\tag{45}\] for each \(R^{(1)}\in \mathrm{Cst}(x)\).

Recall \(\mathcal{C}(x) = \{a_1,a_2,a_3\}\) is a specific certificate for \(x\) we choose. Let \(t_1, t_2,\cdots,t_r\in[m]\) be the order of elements in \(\bigcup R^{(1)}\) get loaded in \(R^{(1)}\). Let \(T_i, i\in\mathbb{Z}_{[0,r]}\), be the vertex that has loaded \(i\) elements on the unique shortest length-\(r\) path from source \(\varnothing\) to \(R^{(1)}\) (\(\mathopen{}\mathclose{\left|\bigcup T_i}\right| = i\), \(T_0 = \varnothing\) and \(T_r= R^{(1)}\)), so that arcs from \(\varnothing\) to \(R^{(1)}\) is in the form of \(A_{t_i}^{T_{i-1},T_i}\in \mathrm{Act}(x, R^{(1)})\). Depending on if \(x\) and \(y\) agree on \(R^{(1)}\),

• If \(x\) and \(y\) disagree on \(R^{(1)}\), there exists \(i^* \in [r]\) such that \(x\) and \(y\) disagree on \(T_i\) if and only if \(i\geq i^*\). This follows from the fact that, for each arc \(A_j^{R,S}\) in stage I, the following holds by 41 : \[\forall k\in \bigcup R, \alpha_S^x(k) = \alpha_R^x(k) \text{ and } \alpha_S^y(k) = \alpha_R^y(k),\] so if \(x\) and \(y\) disagree on \(R\), then they disagree on \(S\).

  We show that \(X_{t_{i^*}}^{T_{i^*-1}, T_{i^*}}[x,y] = q\), and for each \(A_j^{R,S}\in \mathrm{Act}(x,R^{(1)})\backslash\{A_{t_{i^*}}^{T_{i^*-1}, T_{i^*}}\}\), either \(x_j = y_j\) or \(X_j^{R,S}[x,y] = 0\).

  • When we load \(t_{i^*}\) into \(T_{i^*-1}\), \(x\) and \(y\) agree on \(T_{i^*-1}\) but not \(T_{i^*}\). Since \(x\) and \(y\) agree on \(T_{i^*-1}\), for all \(i\in \bigcup T_{i^*-1}\), we have \[\alpha_{T_{i^*}}^x(i) = \alpha_{T_{i^*-1}}^x(i) = \alpha_{T_{i^*-1}}^y(i) = \alpha_{T_{i^*}}^y(i),\] so we must have \(\alpha_{T_{i^*}}^x(t_{i^*}) \neq \alpha_{T_{i^*}}^y(t_{i^*})\) as \(x\) and \(y\) disagree on \(T_{i^*}\). Therefore, \(x_{t_{i^*}} \neq y_{t_{i^*}}\) as otherwise \(\alpha_{T_{i^*}}^x(t_{i^*}) = \alpha_{T_{i^*}}^y(t_{i^*})\). Hence, the term \(X_{t_{i^*}}^{T_{i^*-1}, T_{i^*}}[x,y]\) is included in the summation in 45 . Depending on which stage \(A_{t_{i^*}}^{T_{i^*-1},T_{i^*}}\) is in, either by 42 or by 43 , \[X_{t_{i^*}}^{T_{i^*-1}, T_{i^*}}[x,y] = q.\]

  • When we load \(t_i\) into \(T_{i-1}\) such that \(i\in[i^*-1]\), \(x\) and \(y\) agree on both \(T_{i-1}\) and \(T_{i}\). Then, either \(x_{t_i} = \alpha_{T_i}^x(t_i) = \alpha_{T_i}^y(t_i) = y_{t_i} \neq *\), or \(\alpha_{T_i}^x(t_i) = \alpha_{T_i}^y(t_i) = *\) so that by 43 , \(X^{T_{i-1},T_i}_{t_i}[x,y] = 0\). Therefore, arc \(A_{t_{i}}^{T_{i-1}, T_{i}}\) does not contribute to 45 .

  • Every other arc \(A^{R,S}_j\in \mathrm{Act}(x,R^{(1)})\) is either in stage I and of the form \(A_{t_i}^{T_{i-1},T_i}\) for some \(i>i^*\), \(i\in[r]\), or the arc is in stage II. If the arc is in stage I, then \(x\) and \(y\) disagree on \(R\). Depending on which stage \(A_{t_i}^{T_{i-1},T_i}\) is in, either by 42 or by 43 , \(X_j^{R,S}[x,y]=0\).

    If \(A^{R,S}_j\) is in stage II, it suffices to show that if \(x\) and \(y\) disagree on \(R\), then they also disagree on \(S\). If this holds, a short induction establishes that \(x\) and \(y\) disagree on \(R\) for all \(A^{R,S}_j\in \mathrm{Act}(x, R^{(1)})\) in stage II. By 44 , it then follows that \(X_j^{R,S}[x,y]=0\).

    By the definition of consistency, after loading \(j\in\mathcal{C}(x)\), \[\forall i\in \bigcup R, \alpha_S^x(i) = \alpha_R^x(i).\] If \(x\) and \(y\) agree on \(S\), we must have \[\label{eq:feasibility95contradiciton95agree95on95S} \forall i\in \bigcup R, \alpha_S^y(i) = \alpha_S^x(i) = \alpha_R^x(i).\tag{46}\] However, there exists \(k\in\bigcup R\) such that \(\alpha_R^y(k) \neq \alpha_R^x(k) = \alpha_S^y(k)\) because \(x\) and \(y\) disagree on \(R\). Since \(\{\alpha_R^y(k),\alpha_S^y(k)\} \subseteq \{*, y_k\}\), if 46 holds, it follows that \(\alpha_R^y(k) = *\) and \(y_k = \alpha_S^y(k) = \alpha_S^x(k) = x_k\). Consequently, we must have \(k\in \bigcup S_2\) and \(j\in \bigcup S_1\), implying \(j=a_1\), and \(y_k = x_k\) is incident to \(y_{a_1} = x_{a_1}\). This contradicts the definition of consistency. Therefore, \(x\) and \(y\) must disagree on \(S\).

• If \(x\) and \(y\) agree on \(R^{(1)}\), we first show the contribution from arcs in \(\mathrm{Act}(x,R^{(1)})\) in stage I to 45 is 0. For each \(i\in[r]\), when we load \(t_i\) into \(T_{i-1}\) , \(x\) and \(y\) agree on both \(T_{i-1}\) and \(T_{i}\). An identical argument as in a previous case when \(i\in[i^*-1]\) shows arc \(A_{t_{i}}^{T_{i-1}, T_{i}}\) does not contribute to 45 .

  For stage II, let \(k\) be the smallest number in \([3]\) that \(x_{a_k} \neq y_{a_k}\). \(k\) must exist because \(y\) is a negative instance. For active arcs in stage II.\(k'\) such that \(k' < k\), those arcs are loading \(a_{k'}\) but \(x_{a_{k'}}=y_{a_{k'}}\), so those arcs’ \(X\) are not included in the summation in 45 .

  For arcs in stage II.\(k'\) such that \(k' > k\), \(x\) and \(y\) disagree on the vertices before loading \(a_{k'}\). This is because \(a_{k}\) gets uncovered in \(x\), so \(y_{a_{k}}\) must be equal to \(x_{a_k}\) for \(x\) and \(y\) to agree, which leads a contradiction. Then, by 44 , those active arcs’ contribution to 45 is also 0.

  Next, we show the contribution from arcs in \(\mathrm{Act}(x,R^{(1)})\) in stage II.\(k\) to 45 is exactly \(q\).

  • If \(k=1\), there are \(2^{2d}-1\) arcs in \(\mathrm{Act}(x,R^{(1)})\) in stage II.1. They are of the form \(A^{R^{(1)}, R_\Gamma^{(2)}}_{a_1}\) where \(R_\Gamma^{(2)}\in V^{(2)}(\Gamma)\), one for each \(\varnothing\neq \Gamma\subseteq[2d]\). Since \(x\) and \(y\) agree on \(R^{(1)}\) (and \(x_{a_1}\neq y_{a_1}\)), 44 gives \(X^{R^{(1)}, R_\Gamma^{(2)}}_{a_1}[x,y] = (-1)^{1+\mathopen{}\mathclose{\left|\Gamma}\right|}q\). Therefore, the total contribution of stage II.1 to 45 is \[\sum_{\varnothing\neq \Gamma \subseteq [2d]} (-1)^{1+\mathopen{}\mathclose{\left|\Gamma}\right|}q = q.\]

  • If \(k=2\), there are \(2^{2d}-1\) arcs in \(\mathrm{Act}(x,R^{(1)})\) in stage II.2. They are of the form \(A^{R_\Gamma^{(2)}, R_\Gamma^{(3)}}_{a_2}\) where \(R_\Gamma^{(2)}\in V^{(2)}(\Gamma)\) and \(R_\Gamma^{(3)}\in V^{(3)}(\Gamma)\), one for each \(\varnothing\neq \Gamma\subseteq[2d]\). In this case, \(x\) and \(y\) may not agree on \(R_\Gamma^{(2)}\) due to what are known as faults.

    We say that an index \(i\in \bigcup (R_\Gamma^{(2)})_2\) is faulty if \(y_i\) is incident to \(y_{a_1}\). For \(\gamma\in [2d]\), we say the subset \((R_\Gamma^{(2)})_2(\gamma)\) is faulty if \((R_\Gamma^{(2)})_2(\gamma)\) contains a faulty index. Let \(I\) denote the set of all \(\gamma\in [2d]\) such that \((R_\Gamma^{(2)})_2(\gamma)\) is not faulty.

    We now show \[\text{x,y agree on R^{(2)}_\Gamma} \iff \varnothing\neq \Gamma \subseteq I.\]

    1. “\(\implies\)”: consider the contrapositive. Let \(\gamma \in \Gamma-I\). Suppose \(j\in (R^{(2)}_\Gamma)_2(\gamma)\) is faulty. Then by our definition of assignment, \(\alpha_{R^{(2)}_\Gamma}^y(j) = y_j\). On the other hand, \(\alpha_{R^{(2)}_\Gamma}^x(j)\) cannot be equal to \(y_j\) since \(y_j\) is incident to \(y_{a_1} = x_{a_1}\) and \(R^{(1)}\) is consistent with \(x\).

    2. “\(\impliedby\)”: note that \(x\) and \(y\) certainly agree on \(\bigcup (R^{(2)}_\Gamma)_1\) since \(x_{a_1} = y_{a_1}\) and \(x\) and \(y\) agreed on \(\bigcup R^{(1)}_1\). But since \(\Gamma \subseteq I\), and \(x\) and \(y\) agreed on \(\bigcup R^{(1)}_2\) the definition of \(I\) implies that \(x\) and \(y\) must agree on \(\bigcup (R^{(2)}_\Gamma)_2\) as well.

    Since \(\mathop{\mathrm{\mathrm{maxdeg}}}(\mathop{\mathrm{\mathcal{G}}}(y))\leq d\), \(y_{a_1}\) can be part of at most \(2(d-1)\) wedges. Therefore, the set \(I\) defined above has size \(\mathopen{}\mathclose{\left|I}\right| \geq 2d - 2(d-1) = 2>0\). Therefore, by 44 , the total contribution of stage II.2 to 45 is \[\sum_{\varnothing\neq \Gamma \subseteq I} X^{R^{(2)}_\Gamma,R^{(3)}_\Gamma}_{a_2}[x,y] = \sum_{\varnothing\neq \Gamma \subseteq I} (-1)^{1+\mathopen{}\mathclose{\left|\Gamma}\right|}q = q.\]

  • If \(k=3\), arcs in \(\mathrm{Act}(x,R^{(1)})\) in stage II.3 are of the form \(A^{R_\Gamma^{(3)}, R_\Gamma^{(4)}}_{a_3}\) where \(R_\Gamma^{(3)}\in V^{(3)}(\Gamma)\) and \(R_\Gamma^{(4)}\in V^{(4)}(\Gamma)\), one for each \(\varnothing\neq \Gamma\subseteq[2d]\).

    For each arc \(A^{R_\Gamma^{(2)}, R_\Gamma^{(3)}}_{a_2}\) in stage II.2, since \(x_{a_2} = y_{a_2}\), and loading \(a_2\) does not uncover additional elements by the definition 41 , it follows that \(x\) and \(y\) agree on \(R^{(3)}_\Gamma\) if and only if \(x\) and \(y\) agree on \(R^{(2)}_\Gamma\).

    Therefore, using the same \(I\) as defined in the previous case, the total contribution of stage II.3 to 45 is \[\sum_{\varnothing\neq \Gamma \subseteq I} X^{R^{(3)}_\Gamma,R^{(4)}_\Gamma}_{a_3}[x,y] = \sum_{\varnothing\neq \Gamma \subseteq I} (-1)^{1+\mathopen{}\mathclose{\left|\Gamma}\right|}q = q.\]

6 Cycle Finding↩︎

In this section, we study the \(k\mathsf{\text{-}CYCLE}\) problem, which is a natural generalization of \(\mathop{\mathrm{\mathsf{Triangle}}}\). We give a nearly tight characterization of the quantum query complexity of \(k\mathsf{\text{-}CYCLE}\) for graphs with low maximum degree such as random sparse graphs. We note that the proof of 24 can be straightforwardly extended to any \(k \geq 3\) to show that \(k\mathsf{\text{-}CYCLE}\) is harder than \(k\mathsf{\text{-}DIST}\) but easier than \(k\mathsf{\text{-}SUM}\).

6.1 Cycle finding lower bound↩︎

The most general form of our lower bound reads:

From 33 and the standard fact that random graphs with \(m=\Omega(n)\) edges contain at least one \(k\)-cycle with constant probability, as formally stated in 41, we deduce that the search problem of finding \(k\)-cycle in a random graph is hard in the average case for \(m=\Theta(n)\). It follows that the decision version of \(k\)-cycle is also hard on average, based on the search-to-decision reduction in the edge list model discussed in the preliminaries section. Formally, 33 gives

In the subsequent subsections, we prove 33.

6.1.1 Setting up↩︎

Let \(k,m,\varepsilon,n,T,\Delta\) be as given in the statement of 33. For convenience, we write \[\label{eq:constant95factor} N\mathrel{\vcenter{:}}= \scalebox{1.25}{\binom{n}{2}} \quad \text{and} \quad c \mathrel{\vcenter{:}}= 32e \cdot k\Delta^{k/2}.\tag{50}\] We also identify the symbol \([N]\) with \(\binom{[n]}{2}\) for convenience.

We follow the overall proof strategy as in the triangle case, except there are now more sub-graph structures to keep track of, including length-\(l\) paths for \(l=2,3,\ldots, k-1\), to measure progress in the algorithm. We will argue that to find a \(k\)-cycle, a lot of queries should be spent to find many \((k-1)\)-paths first, which in turn requires a large investment of queries to find many \((k-2)\)-paths and so on. Thus, we define the following projectors to measure the progress of recording edges, paths, and cycles, etc.

We define formally \(\boldsymbol{\square}_t\) to measure the progress of recording a \(k\)-cycle in \(t\) queries as below

In the triangle case, a technical obstacle is that high-degree vertices can distort our analysis by overestimating the increase in the number of new wedges recorded per query. To address this, we developed the Exclusion Lemma to filter out high-degree vertices. In the \(k\)-cycle case, an unexpectedly large number of \((l-1)\)-paths becomes a new source of overestimating the increase of \(l\)-paths recorded per query. This issue, in principle, can be addressed by excluding these unexpected cases; which, however, introduces some extra technical nuances. In particular, we define the following family of functions \(r_j:\mathbb{N}\to\mathbb{N}\), for \(j\in \mathbb{N}\), \[\label{eq:rjt95definition} r_j(t) \mathrel{\vcenter{:}}= \max\mathopen{}\mathclose{\left\{\biggl\lceil \Bigl(\frac{ct}{\sqrt{n}}\Bigr)^{2-4/2^j} (t+1)^{2/2^j}\biggr\rceil, \ceil{\log n}}\right\}\cdot(j\Delta^{j-1}).\tag{51}\] A routine calculation reveals the following analytical property of \(r_j(t)\).

The mysterious-looking family of functions \(r_j(t)\) corresponds to upper bounds on the number of \(j\)-paths that we can record with \(t\) queries, and is calculated from an optimization that only becomes clear after the analysis is carried out: we will show that it is difficult to record more than \(r_j(t)\) number of \(j\)-paths with \(t\) queries. The above discussion motivates the following excluding projectors.

\(\Pi_{\ge r}^{\deg}\) is the same operator we used to exclude high-degree vertices. By the same argument as in the triangle case we can exclude high-degree graphs with the degree threshold set to \(\Delta\).

\(\Pi^{(l)}_{\mathrm{Bad}, t}\) is the new operator that in addition excludes the case that there are unexpectedly many (i.e. at least \(r_j(t)\)) \(j\)-paths for some \(1\le j \le l\) with \(t\) queries. By our definition, for every \(t\in \mathbb{Z}_{[0,T]}\) and \(l\in \mathbb{N}\), \[\label{eq:bad95recurrence} \mathbb{I}- \Pi^{(l)}_{\mathrm{Bad}, t} = \bigl(\mathbb{I}- \Pi^{\{l\}}_{[r_l(t),\infty)}\bigr) \bigl(\mathbb{I}- \Pi^{(l-1)}_{\mathrm{Bad}, t}\bigr).\tag{52}\]

Recall that, for \(t\in \mathbb{Z}_{[0,T]}\), \[\ket{\phi_t} \mathrel{\vcenter{:}}= U_t \mathop{\mathrm{\mathcal{R}}}U_{t-1}\mathop{\mathrm{\mathcal{R}}}\dots U_1 \mathop{\mathrm{\mathcal{R}}}U_0 (\ket{0}\ket{\bot^m}).\]

For \(t\in \mathbb{Z}_{[0,T]}\) and \(l\in \mathbb{Z}_{\geq 0}\), let \[\label{eq:phi95i94l} \ket{\phi_t^{(l)}} \mathrel{\vcenter{:}}= U_t \mathop{\mathrm{\mathcal{R}}}(\mathbb{I}-\Pi_{\mathrm{Bad},t-1}^{(l)}) U_{t-1} \mathop{\mathrm{\mathcal{R}}}(\mathbb{I}-\Pi_{\mathrm{Bad},t-2}^{(l)}) \dots (\mathbb{I}-\Pi_{\mathrm{Bad},1}^{(l)})U_1 \mathop{\mathrm{\mathcal{R}}}U_0 (\ket{0}\ket{\bot^m}).\tag{53}\] The above definition implies: \[\label{eq:phi95i94l95properties} \begin{align} &\ket{\phi_t^{(0)}} = \ket{\phi_t} \quad \text{and} \\ &\ket{\phi_{t+1}^{(l)}} =U_{t+1} \mathop{\mathrm{\mathcal{R}}}(\mathbb{I}- \Pi^{(l)}_{\mathrm{Bad},t})\ket{\phi_t^{(l)}} \quad \text{for all integers 0\leq t \leq T-1.} \end{align}\tag{54}\]

Now, to measure progress in recording length-\(l\) paths, we use the following somewhat technical but convenient definition, that excludes unlikely events in advance.

In the next two subsections, we analyze our progress measures \({\Lambda}_{t,r}^{\{l\}}\) and \(\boldsymbol{\square}_t\) in detail.

6.1.2 Progress in recording paths↩︎

In this part, we analyze the progress of recording \(l\)-paths. We start with the base case \(l=1\), the progress of recording \(1\)-paths, i.e., edges, or a vertex of degree at least \(\Delta\). Recall that the definition of \(\Pi^{\{1\}}_R\) involves a degree condition that is not present in the definitions of \(\Pi^{\{l\}}_R\) for \(l\in \mathbb{N}_{\geq 2}\). The degree condition is crucial for carrying out the induction.

Next, we analyze the progress recording \(l\)-paths for \(l\ge 2\), relying on the following recurrence.

Solving the recurrence, we deduce

6.1.3 Progress in recording a \(k\)-cycle↩︎

For \(t\in \mathbb{Z}_{[0,T]}\), define \[\label{eq:def95cycleprogress} \boldsymbol{\square}'_t \mathrel{\vcenter{:}}= \mathopen{}\mathclose{\left\|\Pi^{\square}\ket{\phi_t^{(k-1)}}}\right\|,\tag{60}\] which corresponds to the progress of recording a \(k\)-cycle given that not many length-\((k-1)\) paths have ever been recorded, and serves as a good estimator of the actual progress.

We can bound \(\boldsymbol{\square}_T'\) by first showing that it satisfies a recurrence in the next lemma and then solving it in the following corollary.

Solving this recurrence gives

Combining the previous two lemmas gives:

6.1.4 Completing the proof of 33↩︎

We finally bound the probability of the quantum query algorithm succeeding even if it does not record a \(k\)-cycle. Let \(\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\) denote the projector onto basis states \(\ket{i,u,w}\ket{x}\) such that \(w\) contains an output substring (i.e., a substring located at some fixed output register) of the form \((a_1,\dots,a_k,b_1,\dots,b_k) \in [m]^k \times \binom{[n]}{2}^k\) where the \(a_i\)s are distinct, the \(b_i\)s form a \(k\)-cycle, and \(x_{a_i} = b_i\) for all \(i\).

With the above lemma, 33 becomes a simple corollary: we have \[\begin{align} \mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\ket{\psi_T}}\right\|=& \mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\mathop{\mathrm{\mathcal{T}}}\ket{\phi_T}}\right\| \notag \\ \leq& \mathopen{}\mathclose{\left\|\Pi^\square \ket{\phi_T}}\right\| + \mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\mathop{\mathrm{\mathcal{T}}}(\mathop{\mathrm{\mathbb{I}}}-\Pi^\square)\ket{\phi_T}}\right\| \notag \\ \leq& O\Bigl(\Delta^k \Bigl(\frac{T}{n^{3/4-1/(2^{k+2}-4)}} \Bigr)^{2-2/2^k} + \Delta^{k/2}T\frac{\sqrt{\log n}}{n} + Tn\Bigl(\frac{2em}{n\ceil{\log(n)}}\Bigr)^{\ceil{\log(n)}}\\ &\qquad\qquad+Tn\mathopen{}\mathclose{\left(\frac{2em}{n\Delta}}\right)^{\Delta}\Bigl(\frac{emn}{2\ceil{\log(n)}}\Bigr)^{\ceil{\log(n)}}\Bigr), \end{align}\] where, in the second inequality, we used 36 to bound \(\Pi^\square \ket{\phi_T}\) and 17 to bound \(\mathopen{}\mathclose{\left\|\Pi_{\mathop{\mathrm{\mathrm{succ}}}}\mathop{\mathrm{\mathcal{T}}}(\mathop{\mathrm{\mathbb{I}}}-\Pi^\square)\ket{\phi_T}}\right\|\), and observed that \(\Delta^{k/2}\cdot T\frac{\sqrt{\log n}}{n}\geq \frac{1}{n}\) for \(T,\Delta\in \mathbb{N}\) and \(n\geq 2\).

6.2 Cycle finding upper bound↩︎

In this section, we prove the following theorem.

To prove 37, when \(d\geq \log_2(m)\), the trivial bound \(Q(k\mathsf{\text{-}CYCLE}_{m,d})\leq m\) applies, ensuring 37 is satisfied. When \(d\leq \log_2(m)\), we employ the learning graph method to confirm the validity of 37.

Unlike the triangle-finding variant, where some problem-specific simplifications and improvements naturally emerged, our generic \(k\)-cycle algorithm retains a nearly identical structure to Belovs’s original learning graph algorithm for \(k\)-distinctness [3]. In fact, by simply setting \(d\) equal to \(k\) and replacing occurrences of the notion of “incident to” by “equal to”, our algorithm essentially solves \(k\)-distinctness itself with a complexity of \(O(m^{3/4-1/(2^{k+2}-4)})\).

Although the proof closely resembles those of our triangle-finding algorithm and Belovs’s \(k\)-distinctness algorithm, we give the proof in full for completeness and clarity.

6.2.1 Learning graph construction↩︎

We first describe the construction of the learning graph. For simplicity, we use \(f\) to denote \(k\mathsf{\text{-}CYCLE}_{m,d}\). The vertices of the learning graph are partitioned by \[\dot{\bigcup}_{i\in\mathbb{Z}_{[0,k+1]}}V^{(i)}.\] A vertex \(S^{(i)}\) in \(V^{(i)}\) is (labeled by) an array containing pairwise-disjoint subsets of \([m]\); we refer to entries of \(S^{(i)}\) by \[S^{(i)} = \dot{\bigoplus}_{j=1}^{k}\mathopen{}\mathclose{\left(\dot{\bigoplus}_{d_1,\dots,d_{j-1}\in[2d],\varnothing\neq D\subseteq [2d]}S_j^{(i)}(d_1,\dots,d_{j-1},D)}\right)\in\mathcal{P}([m])^{\sum_{l=1}^{k}(2d)^{l-1}(2^{2d}-1)},\] where \(\oplus\) means array concatenation, \(\dot{\oplus}\) means the subsets being concatenated are pairwise disjoint, and \(\mathcal{P}([m])\) denotes the power set of \([m]\).

We further impose conditions on the sizes of these sets using some \(r_1,\dots,r_{k} \in \mathbb{N}\) that will be chosen later, at the end of 6.2.4. To describe these conditions, it is convenient to write \(\mu(A)\) for the minimum element of a finite non-empty subset \(A \subset \mathbb{Z}\).

Then, for every \(i\geq 1\), we impose that \(V^{(i)}\) can be partitioned by labels consisting of a length-\((i-1)\) sequence of non-empty subsets of \([2d]\), \(D_1,D_2,\dots,D_{i-1}\), such that \(V^{(i)}(D_1,\dots,D_{i-1})\) consists of all vertices \(S^{(i)}\) such that the size of \(S^{(i)}_j(\cdot)\) satisfies \[\mathopen{}\mathclose{\left|S^{(i)}_j(d_1,\dots,d_{j-1},D)}\right| = \begin{cases} r_j+1, & j < i, d_1 = \mu(D_1),\dots,d_{j-1}=\mu(D_{j-1}), D = D_j,\\ r_j, & \text{otherwise}. \end{cases}\]

For each vertex \(R\) in the learning graph, define \[\bigcup R_i\mathrel{\vcenter{:}}= \bigcup_{d_1,\dots,d_{i-1}\in[2d],\varnothing\neq D\subseteq [2d]} R_i(d_1,\dots,d_{i-1},D), \quad\text{and}\quad \bigcup R\mathrel{\vcenter{:}}= \bigcup_{i\in[k]}\mathopen{}\mathclose{\left(\bigcup R_i}\right).\] We refer to indices contained in \(\bigcup R_i\) and \(\bigcup R\) as having been loaded in \(R_i\) and \(R\), respectively. If there is an arc from vertex \(R\) to vertex \(S\) in the learning graph, by the construction in the following paragraphs, it must satisfy \(\bigcup S = \bigcup R \cup \{j\}\). We denote the arc as \(A^{R,S}_j\), and accordingly, we say \(A^{R,S}_j\) is associated with the loading of \(j\).

There exists a unique vertex \(R^{(0)}\in V^{(0)}\) such that \(\bigcup R^{(0)} = \varnothing\). We refer to this vertex as the source, denoted by \(\varnothing\). Each vertex \(R^{(1)}\in V^{(1)}\) loads exactly \[r \mathrel{\vcenter{:}}= \sum_{i=1}^{k}r_i(2d)^{i-1}(2^{2d}-1)\] indices. We fix an arbitrary ordering \(t_1,\dots, t_r\) of indices in \(\bigcup R^{(1)}\) such that all indices in \(\bigcup R^{(1)}_i\) precede those in \(\bigcup R^{(1)}_j\) if \(i<j\). There exists a length \(r\) path from the source \(\varnothing\) to \(R^{(1)}\), with all intermediate vertices lying in \(V^{(0)}\). Along this path, the element \(t_i\) is loaded on the \(i\)-th arc for \(i\in[r]\) in stage I, and specifically, if \(t_i\in \bigcup R_s^{(1)}\), it is loaded in stage I.\(s\). All such paths are disjoint except at the source \(\varnothing\). Therefore, there are \(r\bigl|V^{(1)}\bigr|\) arcs in stage I.

In stage II.\(s\) for \(s\in[k]\), for each \(R^{(s)}\in V^{(s)}(D_1,\dots,D_{s-1})\), \(j\not\in\bigcup R^{(s)}\) and \(\varnothing\neq D_s\subseteq[2d]\), there is an arc loading \(j\), denoted \(A^{R^{(s)}, R^{(s+1)}}_j\), from \(R^{(s)}\) to \(R^{(s+1)} \in V^{(s+1)}(D_1,\dots,D_s)\) defined by \[\begin{cases} R^{(s+1)}_s(\mu(D_1),\dots,\mu(D_{s-1}),D_s) = R^{(s)}_s(\mu(D_1),\dots,\mu(D_{s-1}),D_s)\cup\{j\},\\ R^{(s+1)}_i(d_1,\dots,d_{i-1},D) = R^{(s)}_i(d_1,\dots,d_{i-1},D) \quad\text{if }(i,d_1,\dots,d_{i-1},D)\neq (s,\mu(D_1),\dots,\mu(D_{s-1}),D_s). \end{cases}\]

6.2.2 Active arcs↩︎

For every \(x\in f^{-1}(1)\), let \(\mathcal{C}(x) = \{a_1, a_2, \dots, a_k\}\subseteq[m]\) be a specific certificate for \(x\) such that \(x_{a_1}, \dots, x_{a_k}\) form a \(k\)-cycle, and \(x_{a_i}\) is incident to \(x_{a_{i+1}}\) for all \(i\in[k-1]\).

We say \(R^{(1)}\in V^{(1)}\) is consistent with \(x\in f^{-1}(1)\) if edges indexed by \(\mathcal{C}(x)\) are vertex disjoint from edges indexed by \(\bigcup R^{(1)}\). Let \(n_x\) be the number of \(R^{(1)}\in V^{(1)}\) that are consistent with \(x\), and define \[q\mathrel{\vcenter{:}}= \Bigl(\min_{x\in f^{-1}(1)}\{n_x\}\Bigr)^{-1}.\] so that for all \(x\in f^{-1}(1)\), there exist at least \(q^{-1}\) vertices in \(V^{(1)}\) that are consistent with \(x\). By 27, when \(kdr\leq o(m)\) — a condition satisfied since we only need to consider \(k\in O(1)\), \(d\in\log_2(m)\), and use the \(r\) specified in 6.2.4 — it follows that \(q^{-1}\geq\Omega(\bigl|V^{(1)}\bigr|)\).

Let \(\mathrm{Cst}(x)\) denote a fixed but arbitrary set of \(q^{-1}\) vertices \(R^{(1)}\in V^{(1)}\) that are consistent with \(x\). For each \(R^{(1)}\in \mathrm{Cst}(x)\), \(\mathrm{Act}(x,R^{(1)})\) is a set of active arcs consisting of the following arcs:

• In stage I, all arcs along the unique shortest length \(r\) path from source \(\varnothing\) to \(R^{(1)}\).

• In stage II.\(s\), we define recursively so that if \(R^{(s)}\in V^{(s)}\) has an incoming arc from \(\mathrm{Act}(x, R^{(1)})\), all arcs \(A_{a_s}^{R^{(s)},R^{(s+1)}}\) in the learning graph such that \(R^{(s+1)} \in V^{(s+1)}\) are in \(\mathrm{Act}(x, R^{(1)})\).

Lastly, the set of all active arcs of \(x\) is defined by \[\mathrm{Act}(x)\mathrel{\vcenter{:}}= \dot{\bigcup}_{R^{(1)}\in \mathrm{Cst}(x)}\mathrm{Act}(x,R^{(1)}).\]

6.2.3 Matrices for the adversary bound↩︎

For every vertex \(R\) in the learning graph, an assignment on \(R\) refers to a function \(\alpha_R: \bigcup R\to \binom{[n]}{2}\cup\{*\}\) such that:

1. for all \(j\in \bigcup R_1\), \[\alpha_R(j)\neq *;\]

2. for all \(j \in R_i(d_1,\dots,d_{i-1},D)\) such that \(i>1\), define \[N(R, d_1,\dots,d_{i-1})\mathrel{\vcenter{:}}= \bigcup_{d_{i-1}\in D'\subseteq[2d]}R_{i-1}(d_1, \dots, d_{i-2}, D'),\] then \(\alpha_R(j)\) must satisfy \[\alpha_R(j)\in\{*\}\cup \Bigl\{e\in \scalebox{1.25}{\binom{[n]}{2}} \Bigm| \exists k\in N(R, d_1,\dots,d_{i-1})\text{ s.t. e is incident to \alpha_R(k)} \Bigr\}.\] Note that the special symbol \(*\) is not incident to any edge.

We say an input \(z\in \binom{[n]}{2}^m\) satisfies assignment \(\alpha_{R}\) if, for all \(t\in \bigcup R\), \[\label{eq:alpha95def95for95k} \alpha_{R}(t) = \begin{cases} z_t, & \text{if t \in \bigcup R_1}, \\[1ex] z_t, & \begin{align}[t] &\text{if i>1, t \in R_i(d_1,\dots,d_{i-1},D) and}\\ &\text{\exists k\in N(R,d_1,\dots,d_{i-1}) s.t. z_t is incident to \alpha_R(k)}, \end{align}\\[1ex] *, &\text{otherwise}. \end{cases}\tag{71}\] For each vertex \(R\) in the learning graph, we write \(\alpha_R^x\) for the unique assignment on \(R\) that \(x\) satisfies. We say arc \(A^{R,S}_j\) uncovers \(j\) if \(\alpha_S^x(j)\neq *\). We say inputs \(x,y\in \binom{[n]}{2}^m\) agree on \(R\) if they satisfy \(\alpha_R^x = \alpha_R^y\); we also say they agree on a subset of \(\bigcup R\) if the restriction of \(\alpha_R^x\) and \(\alpha_R^y\) to that subset equal.

Define \[X_j^{R,S}\mathrel{\vcenter{:}}= \sum_{\alpha_R} Y_{\alpha_R},\] where the summation is over all assignments \(\alpha_R\) on \(R\).

For each arc \(A_j^{R,S}\) in stage I.1, define \(Y_{\alpha_R}\mathrel{\vcenter{:}}= q\psi_{\alpha_R}\psi_{\alpha_R}^\dagger\), where \(\psi_{\alpha_R}\) is a real vector indexed by \(\binom{[n]}{2}^m\) and defined entry-wise by \[\psi_{\alpha_R}[z] \mathrel{\vcenter{:}}= \begin{cases} 1, & \text{if f(z)=1, z satisfies \alpha_R, and A^{R,S}_j\in \mathrm{Act}(z)},\\ 1, & \text{if f(z)=0 and z satisfies \alpha_R},\\ 0,&\text{otherwise}. \end{cases}\] With the above definition, we see that \(X_j^{R,S}\) consists of blocks of the form: \[\label{X95block95form95I46195for95k} \renewcommand{\arraystretch}{1.25} \begin{array}{c|c|c} & x & y \\ \hline x & q & q \\ \hline y & q & q \end{array}\tag{72}\] where \(x\in f^{-1}(1)\), \(y\in f^{-1}(0)\), \(A^{R,S}_j\in \mathrm{Act}(x)\), and both \(x\) and \(y\) agree on \(R\).

For arcs \(A_j^{R,S}\) in stage I.\(s\) where \(s>1\), define \(Y_{\alpha_R}\mathrel{\vcenter{:}}= q(\psi_{\alpha_R}\psi_{\alpha_R}^\dagger+\phi_{\alpha_R}\phi_{\alpha_R}^\dagger)\) where \(\psi_{\alpha_R}\) and \(\phi_{\alpha_R}\) are real vectors indexed by \(\binom{[n]}{2}^m\) and defined entry-wise by \[\psi_{\alpha_R}[z] \mathrel{\vcenter{:}}= \begin{cases} 1/\sqrt{w_1}, & \text{if f(z)=1, \alpha_S^z(j)\neq*, z satisfies \alpha_R, and A^{R,S}_j\in \mathrm{Act}(z)},\\ \sqrt{w_1}, & \text{if f(z)=0, and z satisfies \alpha_R},\\ 0,&\text{otherwise;} \end{cases}\] and \[\phi_{\alpha_R}[z] \mathrel{\vcenter{:}}= \begin{cases} 1/\sqrt{w_0}, & \text{if f(z)=1, \alpha_S^z(j)=*, z satisfies \alpha_R, and A^{R,S}_j\in \mathrm{Act}(z)},\\ \sqrt{w_0}, & \text{if f(z)=0, \alpha_S^z(j)\neq*, and z satisfies \alpha_R},\\ 0, & \text{otherwise.} \end{cases}\] Here, \(w_0\) and \(w_1\) are positive real numbers that will be specified later. With the above definition, we see that \(X_j^{R,S}\) consists of blocks of the form: \[\label{X95block95form95I46295for95k} \begin{array}{l|c|c|c|c} & x: x_j =\alpha_S^x(j)\neq * & x: \alpha_S^x(j)= * & y: y_j =\alpha_S^y(j)\neq * & y: \alpha_S^y(j)= * \\ \hline x: x_j =\alpha_S^x(j)\neq * & q/w_1 & 0 & q & q \\ \hline x: \alpha_S^x(j)= * & 0 & q/w_0 & q & 0 \\ \hline y: y_j =\alpha_S^y(j)\neq * & q & q & q(w_0 + w_1) & qw_1 \\ \hline y: \alpha_S^y(j)= * & q & 0 & qw_1 & qw_1 \\ \end{array}\tag{73}\] where \(x\in f^{-1}(1)\), \(y\in f^{-1}(0)\), \(A^{R,S}_j\in \mathrm{Act}(x)\), and both \(x\) and \(y\) agree on \(R\).

For arcs \(A_j^{R,S}\) in stage II.\(s\) where \(s\in[k]\), suppose \(R\in V^{(s)}(D_1,\dots,D_{s-1})\) and \(S\in V^{(s+1)}(D_1,\dots, D_s)\), define \(Y_{\alpha_R}\mathrel{\vcenter{:}}= q\psi_{\alpha_R}\psi_{\alpha_R}^\dagger\) where \[\psi_{\alpha_R}[z] \mathrel{\vcenter{:}}= \begin{cases} 1/\sqrt{w_2},& \text{if f(z)=1, z satisfies \alpha_R, and A_j^{R,S}\in \mathrm{Act}(z)},\\ (-1)^{s+\sum_{i=1}^{s}\mathopen{}\mathclose{\left|D_i}\right|}\sqrt{w_2}, & \text{if f(z)=0, and z satisfies \alpha_R},\\ 0,&\text{otherwise.} \end{cases}\] \(X_j^{R,S}\) consists of blocks of the form: \[\label{X95block95form95II95for95k} \renewcommand{\arraystretch}{1.25} \begin{array}{c|c|c} & x & y \\ \hline x & q/w_2 & (-1)^{s+\sum_{i=1}^{s}\mathopen{}\mathclose{\left|D_i}\right|}q \\ \hline y & (-1)^{s+\sum_{i=1}^{s}\mathopen{}\mathclose{\left|D_i}\right|}q & qw_2 \end{array}\tag{74}\] where \(x\in f^{-1}(1)\), \(y\in f^{-1}(0)\), \(A^{R,S}_j\in \mathrm{Act}(x)\), and both \(x\) and \(y\) agree on \(R\).

6.2.4 Complexity↩︎

Assume constant \(k\in \mathbb{N}_{\geq 3}\), we show \(Q(k\mathsf{\text{-}CYCLE}_{m,d}) \leq O((2d)^{(k^2+k-6)/4}\, 2^{2dk} \, m^{3/4-1/(2^{k+2}-4)})\) by computing 39 . Furthermore, if \(d\leq O(\log(m)/\log\log(m))\), we have \(Q(k\mathsf{\text{-}CYCLE}_{m,d}) \leq O(m^{3/4-1/(2^{k+2}-4)+o(1)})\).

1. For stage I.1, there are \(r_1(2^{2d}-1)\bigl|V^{(1)}\bigr|\) arcs in this stage. By 72 , each of them contributes \(q\) to the complexity, so the complexity of this stage is \(r_1(2^{2d}-1)\bigl|V^{(1)}\bigr|q = O(2^{2d}r_1)\).

2. For stage I.\(s\) with \(s>1\), there are \(r_s(2d)^{s-1}(2^{2d}-1)\bigl|V^{(1)}\bigr|\) arcs in this stage. For each input \(z\), we need to bound the number of arcs that can uncover an element, so we get a refined bound on the contribution from 73 . Suppose such an arc in this stage is on the shortest length-\(r\) path from source \(\varnothing\) to \(R^{(1)}\in V^{(1)}\), and is uncovering \(b_s\) in \(\bigcup R_s^{(1)}\), then, there must exist a length-\(s\) sequence \((z_{b_1}, z_{b_2}, \dots, z_{b_s})\) such that \(b_i\in \bigcup R^{(1)}_i\) and \(z_{b_i}\) is incident to \(z_{b_{i+1}}\) for all \(i\in[s-1]\). The number of such sequences \((b_1,\dots,b_s)\) is at most \(m(2d)^{s-1}\), and the number of choices of \(R^{(1)}\) loads \(b_i\) in stage I.\(i\) for all \(i\in[s]\) is upper bounded by \[\begin{align} &(2d)^{s(s-1)/2}(2^{2d}-1)^s\binom{m-s}{r_1-1,\underbrace{r_1,\cdots,r_1}_{(2^{2d}-1)-1},r_2-1,\underbrace{r_2,\cdots,r_2}_{(2d)(2^{2d}-1)-1},\dots, r_s-1,\underbrace{r_s,\cdots,r_s}_{(2d)^{s-1}(2^{2d}-1)-1}}\\ =& O\Bigl(\frac{r_1r_2\cdots r_s(2d)^{\frac{s(s-1)}{2}} 2^{2ds}}{m^s}\bigl|V^{(1)}\bigr|\Bigr). \end{align}\] Therefore, for a negative input, by 73 , stage I.\(s\)’s contribution to the complexity is \[\begin{align} &O\Bigl(qw_0(m(2d)^{s-1})\Bigl(\frac{r_1\cdots r_s(2d)^{s(s-1)/2} 2^{2ds}}{m^s}\bigl|V^{(1)}\bigr|\Bigr)+qw_1\Bigl(r_s(2d)^{s-1}(2^{2d}-1)\bigl|V^{(1)}\bigr|\Bigr)\Bigr)\\ =&O\Bigl(\frac{r_1\cdots r_s(2d)^{(s^2+s-2)/2}2^{2ds}}{m^{s-1}}w_0+r_s(2d)^{s-1}2^{2d}w_1\Bigr); \end{align}\] and for a positive input, by 73 , stage I.\(s\)’s contribution to the complexity is \[\begin{align} &O\Bigl(\frac{q}{w_1}(m(2d)^{s-1})\Bigl(\frac{r_1\cdots r_s(2d)^{s(s-1)/2} 2^{2ds}}{m^s}\bigl|V^{(1)}\bigr|\Bigr)+\frac{q}{w_0}\Bigl(r_s(2d)^{s-1}(2^{2d}-1)\bigl|V^{(1)}\bigr|\Bigr)\Bigr)\\ =&O\Bigl(\frac{r_1\cdots r_s(2d)^{(s^2+s-2)/2}2^{2ds}}{m^{s-1}w_1}+\frac{r_s(2d)^{s-1}2^{2d}}{w_0}\Bigr). \end{align}\] If we set \(w_0=((2d)^{s(s-1)/4}2^{d(s-1)})^{-1}\sqrt{\frac{m^{s-1}}{r_1\cdots r_{s-1}}}\), and \(w_1 = 1/w_0\), the total contribution to the complexity is \[O\Bigl((2d)^{(s^2+3s-4)/4}2^{d(s+1)}r_s\sqrt{\frac{r_1\cdots r_{s-1}}{m^{s-1}}}\Bigr).\]

3. For stage II.\(s\) when \(s\in[k]\), each vertex in \(V^{(s)}\) has \((m-r-s+1)(2^{2d}-1)\) outgoing arcs, and if \(s>1\), each vertex in \(V^{(s)}\) has \(r_{s-1}+1\) incoming arcs. Therefore, the total number of arcs on stage II.\(s\) is \[\frac{\prod_{i=1}^s(m-r-i+1)(2^{2d}-1)}{\prod_{j=2}^{s}(r_{j-1}+1)}\bigl|V^{(1)}\bigr|\leq O\Bigl(\frac{m^s2^{2ds}\bigl|V^{(1)}\bigr|}{r_1\cdots r_{s-1}}\Bigr).\] As we will see later, \(r_i\in o(m)\) for all \(i\in[k]\), so the total number of arcs in stage II is upper bounded by \(O(m^k2^{2dk}\bigl|V^{(1)}\bigr|/(r_1\cdots r_{k-1}))\). Among them, if a vertex in \(V^{(s)}\) has an incoming active arc, that vertex has \(2^{2d}-1\) outgoing active arcs. Therefore, there are at most \(q^{-1}\sum_{i=1}^k(2^{2d}-1)^i = O(2^{2dk}q^{-1})\) active arcs in stage II in total. For every negative input, by 74 , each arc contributes \(qw_2\) to the complexity, so the total contribution is \[O\Bigl(\frac{m^k2^{2dk}\bigl|V^{(1)}\bigr|}{r_1\cdots r_{k-1}}qw_2\Bigr) = O\Bigl(2^{2dk}\frac{m^kw_2}{r_1\cdots r_{k-1}}\Bigr).\] For every positive input, by 74 , each active arc contributes \(q/w_2\) to the complexity, so the total contribution is upper bounded by \[O(2^{2dk}q^{-1}) \frac{q}{w_2} \leq O(2^{2dk}/w_2).\] To balance the contribution from negative inputs and positive inputs, we can set \(w_2=\sqrt{\frac{r_1\cdots r_{k-1}}{m^k}}\) so that the total contribution in stage II is \[O\biggl(2^{2dk}\sqrt{\frac{m^k}{r_1\cdots r_{k-1}}}\, \biggr).\]

The total complexity of all stages is \[O\biggl(2^{2d}r_1 + \Bigl(\sum_{i=2}^k (2d)^{(i^2+3i-4)/4} \, 2^{d(i+1)}r_i\sqrt{\frac{r_1\cdots r_{i-1}}{m^{i-1}}}\Bigr) + 2^{2dk}\sqrt{\frac{m^k}{r_1\cdots r_{k-1}}}\, \biggr).\] To (approximately) balance the summands, we set \(r_i = \ceil{m^{1-1/2^{i+1}-1/(2^{i+1}(2^k-1))}}\) for all \(i\in[k-1]\) and \(r_k=0\). The above equation leads to a complexity of \(O((2d)^{(k^2+k-6)/4}\, 2^{2dk} \, m^{3/4-1/(2^{k+2}-4)})\).

6.2.5 Feasibility↩︎

Fix two inputs \(x\in f^{-1}(1)\) and \(y\in f^{-1}(0)\), to prove 40 holds, it is equivalent to show \[\sum_{A_j^{R,S} \in \mathrm{Act}(x) \colon x_j \neq y_j} X_j^{R,S}[x,y] = 1.\] Since \(\mathrm{Act}(x)= \dot{\bigcup}_{R^{(1)}\in \mathrm{Cst}(x)}\mathrm{Act}(x,R^{(1)})\), it suffices to prove that for all \(R^{(1)}\in \mathrm{Cst}(x)\), \[\label{eq:feasibility95for95k} \sum_{A_j^{R,S} \in \mathrm{Act}(x,R^{(1)}) \colon x_j \neq y_j} X_j^{R,S}[x,y] = \frac{1}{\mathopen{}\mathclose{\left|\mathrm{Cst}(x)}\right|} = q,\tag{75}\]

Recall \(\mathcal{C}(x) = \{a_1,\dots, a_k\}\) is a specific certificate for \(x\) that we chose. Let \(t_1, t_2,\cdots,t_r\in[m]\) be the elements in \(\bigcup R^{(1)}\) given in the order in which they are loaded in \(R^{(1)}\). For \(i\in\mathbb{Z}_{[0,r]}\), let \(T_i\) be the vertex that has loaded \(i\) elements on the unique shortest length-\(r\) path from source \(\varnothing\) to \(R^{(1)}\) (\(\mathopen{}\mathclose{\left|\bigcup T_i}\right| = i\), \(T_0 = \varnothing\) and \(T_r= R^{(1)}\)), so that arcs from \(\varnothing\) to \(R^{(1)}\) is in the form of \(A_{t_i}^{T_{i-1},T_i}\in \mathrm{Act}(x, R^{(1)})\).

We perform the following case analysis depending on whether \(x\) and \(y\) agree on \(R^{(1)}\).

• If \(x\) and \(y\) disagree on \(R^{(1)}\), there exists \(i^* \in [r]\) such that \(x\) and \(y\) disagree on \(T_i\) if and only if \(i\geq i^*\). This follows from the fact that, for each arc \(A_j^{R,S}\) in stage I, the following holds by 71 : \[\forall l\in \bigcup R, \alpha_S^x(l) = \alpha_R^x(l) \text{ and } \alpha_S^y(l) = \alpha_R^y(l),\] so if \(x\) and \(y\) disagree on \(R\), then they disagree on \(S\).

  We show that \(X_{t_{i^*}}^{T_{i^*-1}, T_{i^*}}[x,y] = q\), and for each \(A_j^{R,S}\in \mathrm{Act}(x,R^{(1)})\backslash\{A_{t_{i^*}}^{T_{i^*-1}, T_{i^*}}\}\), either \(x_j = y_j\) or \(X_j^{R,S}[x,y] = 0\).

  • When we load \(t_{i^*}\) into \(T_{i^*-1}\), \(x\) and \(y\) agree on \(T_{i^*-1}\) but not \(T_{i^*}\). Since \(x\) and \(y\) agree on \(T_{i^*-1}\), for all \(i\in \bigcup T_{i^*-1}\), we have \[\alpha_{T_{i^*}}^x(i) = \alpha_{T_{i^*-1}}^x(i) = \alpha_{T_{i^*-1}}^y(i) = \alpha_{T_{i^*}}^y(i),\] so we must have \(\alpha_{T_{i^*}}^x(t_{i^*}) \neq \alpha_{T_{i^*}}^y(t_{i^*})\) as \(x\) and \(y\) disagree on \(T_{i^*}\). Therefore, \(x_{t_{i^*}} \neq y_{t_{i^*}}\) as otherwise \(\alpha_{T_{i^*}}^x(t_{i^*}) = \alpha_{T_{i^*}}^y(t_{i^*})\). Hence, the term \(X_{t_{i^*}}^{T_{i^*-1}, T_{i^*}}[x,y]\) is included in the summation in 75 . Depending on which stage \(A_{t_{i^*}}^{T_{i^*-1}, T_{i^*}}\) is in, either by 72 or by 73 , \[X_{t_{i^*}}^{T_{i^*-1}, T_{i^*}}[x,y] = q,\]

  • When we load \(t_i\) into \(T_{i-1}\) such that \(i\in[i^*-1]\), \(x\) and \(y\) agree on both \(T_{i-1}\) and \(T_{i}\). Then, either \(x_{t_i} = \alpha_{T_i}^x(t_i) = \alpha_{T_i}^y(t_i) = y_{t_i} \neq *\), or \(\alpha_{T_i}^x(t_i) = \alpha_{T_i}^y(t_i) = *\) so that by 73 , \(X^{T_{i-1},T_i}_{t_i}[x,y] = 0\). Therefore, arc \(A_{t_{i}}^{T_{i-1}, T_{i}}\) does not contribute to 75 .

  • Every other arc \(A^{R,S}_j\in \mathrm{Act}(x,R^{(1)})\) is either in stage I and of the form \(A_{t_i}^{T_{i-1},T_i}\) for some \(i>i^*\), \(i\in[r]\), or the arc is in stage II. If the arc is in stage I, then \(x\) and \(y\) disagree on \(R\). Depending on which stage \(A_{t_{i}}^{T_{i-1}, T_{i}}\) is in, either by 72 or by 73 , \(X_j^{R,S}[x,y]=0\).

    If \(A^{R,S}_j\) is in stage II, it suffices to show that if \(x\) and \(y\) disagree on \(R\), then they also disagree on \(S\). If this holds, a short induction establishes that \(x\) and \(y\) disagree on \(R\) for all \(A^{R,S}_j\in \mathrm{Act}(x, R^{(1)})\) in stage II. By 74 , it then follows that \(X_j^{R,S}[x,y]=0\).

    By the definition of consistency, after loading \(j\in\mathcal{C}(x)\), \[\forall i\in \bigcup R, \alpha_S^x(i) = \alpha_R^x(i).\] If \(x\) and \(y\) agree on \(S\), we must have \[\label{eq:feasibility95contradiciton95agree95on95S95for95k} \forall i\in \bigcup R, \alpha_S^y(i) = \alpha_S^x(i) = \alpha_R^x(i).\tag{76}\] However, there exists \(l\in\bigcup R\) such that \(\alpha_R^y(l) \neq \alpha_R^x(l) = \alpha_S^y(l)\) because \(x\) and \(y\) disagree on \(R\). Since \(\{\alpha_R^y(l),\alpha_S^y(l)\} \subseteq \{*, y_l\}\), if 76 holds, it follows that \(\alpha_R^y(l) = *\) and \(y_l = \alpha_S^y(l) = \alpha_S^x(l) = x_l\). Furthermore, one such \(l\) must satisfy \(l\in \bigcup S_{i+1}\) and \(j\in \bigcup S_i\) for some \(i\in[k-1]\), implying \(j=a_i\), and \(y_l = x_l\) is incident to \(y_{a_i} = x_{a_i}\). This contradicts the definition of consistency. Therefore, \(x\) and \(y\) must disagree on \(S\).

• If \(x\) and \(y\) agree on \(R^{(1)}\), we first show the contribution from arcs in \(\mathrm{Act}(x,R^{(1)})\) in stage I to 75 is 0. For each \(i\in[r]\), when we load \(t_i\) into \(T_{i-1}\), \(x\) and \(y\) agree on both \(T_{i-1}\) and \(T_{i}\). An identical argument as in a previous case when \(i\in[i^*-1]\) shows arc \(A_{t_{i}}^{T_{i-1}, T_{i}}\) does not contribute to 75 .

  For stage II, let \(l\) be the smallest number in \([l]\) that \(x_{a_l} \neq y_{a_l}\). Such \(l\) must exist because \(y\) is a negative instance. For active arcs in stage II.\(l'\) such that \(l' < l\), those arcs are loading \(a_{l'}\) but \(x_{a_{l'}}=y_{a_{l'}}\), so those arcs’ \(X\) are not included in the summation in 75 .

  For arcs in stage II.\(l'\) such that \(l' > l\), \(x\) and \(y\) disagree on the vertices before loading \(a_{l'}\). This is because \(a_{l}\) gets uncovered in \(x\), so \(y_{a_{l}}\) must be equal to \(x_{a_l}\) for \(x\) and \(y\) to agree, which leads a contradiction. Then, by 74 , those active arcs’ contribution to 75 is also 0.

  Next, we show the contribution from arcs in \(\mathrm{Act}(x,R^{(1)})\) in stage II.\(l\) to 75 is exactly \(q\). For each \(s\in[l]\) and sequence \((D_1, \dots, D_{s-1})\), there exists exactly one vertex \(T^{(s)}\in V^{(s)}(D_1,\dots, D_{s-1})\) such that \(\bigcup T^{(s)} = \bigcup R^{(1)}\cup\{a_1,\dots,a_{s-1}\}\).

  Let \(B(s, D_1,\dots, D_{s-1})\) be the set of vertices in \(V^{(l)}\) reachable from \(T^{(s)}\) by arcs in \(\mathrm{Act}(x, R^{(1)})\). There is a bijection between vertices in \(B(s, D_1,\dots, D_{s-1})\) and choices \((D_s, \dots, D_{l-1})\); explicitly, each \(R\in B(s, D_1,\dots, D_{s-1})\) corresponds uniquely to a single choice of \((D_s, \dots, D_{l-1})\), satisfying \(R\in V^{(l)}(D_1,\dots, D_{l-1})\). Define the contribution from \(T^{(s)}\) to 75 as \[C(T^{(s)}) \mathrel{\vcenter{:}}= \sum_{R\in B(s, D_1,\dots, D_{s-1}), A_{a_l}^{R,S}\in\mathrm{Act}(x, R^{(1)})}X_{a_l}^{R,S}[x,y].\] Then, our goal becomes showing \(C(R^{(1)}) = q\), and we do this by induction on \(s\) from \(l\) down to 1, and showing \[C(T^{(s)}) = \begin{cases} (-1)^{1+s+\sum_{i=1}^{s-1}\mathopen{}\mathclose{\left|D_i}\right|}q & \text{if x and y agree on T^{(s)},}\\ 0 & \text{if x and y disagree on T^{(s)}.} \end{cases}\]

  • If \(s=l\), \(T^{(s)}\) vertex has \(2^{2d}-1\) outgoing active arcs in \(\mathrm{Act}(x, R^{(1)})\), one for each \(\varnothing\neq D_l\subseteq [2d]\), to vertex \(T^{(l+1)}\in V^{(l+1)}(D_1,\dots,D_{l-1},D_l)\). If \(x\) and \(y\) disagree on \(T^{(s)}\), all these arcs’ contribution to 75 is 0 by 74 . If \(x\) and \(y\) agree on \(T^{(s)}\), since \(x_{a_l}\neq y_{a_l}\), all these outgoing active arcs’ contribution are included in 75 . By 74 , the total contribution from these arcs to 75 is \[\sum_{\varnothing\neq D_l\subseteq [2d]}(-1)^{l+\sum_{i=1}^l\mathopen{}\mathclose{\left|D_i}\right|}q = (-1)^{1+l+\sum_{i=1}^{l-1}\mathopen{}\mathclose{\left|D_i}\right|}q.\] This proves the base case.

  • When \(s<l\), for each \(\varnothing\neq D_s\subseteq [2d]\), there exists a vertex in \(T^{(s+1)}(D_s)\in V^{(s+1)}(D_1,\dots,D_s)\) such that \(A_{a_s}^{T^{(s)}, T^{(s+1)}(D_s)}\in\mathrm{Act}(x, R^{(1)})\). Notice \[B(s,D_1,\dots, D_{s-1}) = \dot{\bigcup_{\varnothing\neq D_s\subseteq[2d]}} B(s+1,D_1,\dots, D_s),\] so \[C(T^{(s)}) = \sum_{\varnothing\neq D_s\subseteq[2d]} C(T^{(s+1)}(D_s)).\]

    • If \(x\) and \(y\) disagree on \(T^{(s)}\), since we are in stage II, as proved in a previous part, \(x\) and \(y\) disagree on \(T^{(s+1)}(D_s)\) for all \(\varnothing\neq D_s \subseteq[2d]\). Assuming the induction hypothesis, we have \(C(T^{(s)}) = 0\).

    • If \(x\) and \(y\) agree on \(T^{(s)}\), although \(x_{a_s} = y_{a_s}\), \(x\) and \(y\) may not agree on \(T^{(s+1)}(D_s)\) due to what are known as faults. We say that an index \(j\in \bigcup R^{(1)}_{s+1}\) is faulty if \(y_j\) is incident to \(y_{a_s}\). Let \(I\) denote the set of all \(i\in[2d]\) such that \[\bigcup_{\varnothing\neq D\subseteq[2d]} T^{(s)}_{s+1}(\mu(D_1),\dots,\mu(D_{s-1}), i, D),\] does not contain a faulty index. By the definitions of assignment and consistency, and the assumption that \(x\) and \(y\) agree on \(T^{(s)}\), since \(x_{a_s} = y_{a_s}\), \(x\) and \(y\) agree on \(T^{(s+1)}(D_s)\) if and only if \(\varnothing\neq D_s\subseteq I\). There are at most \(2(d-1)\) faulty indices since the graph has a max degree of \(d\), so at most \(2(d-1)\) other edges in \(y\) can be incident to \(y_{a_s}\) — a necessary condition for causing a fault. Therefore, \(\mathopen{}\mathclose{\left|I}\right| \geq 2d-2(d-1) > 0\). By the induction hypothesis, \[\begin{align} C(T^{(s)}) =& \sum_{\varnothing\neq D_s\subseteq I} C(T^{(s+1)}(D_s)) \notag \\ =& \sum_{\varnothing\neq D_s\subseteq I}(-1)^{1+(s+1)+\sum_{i=1}^{s}\mathopen{}\mathclose{\left|D_i}\right|}q = (-1)^{1+s+\sum_{i=1}^{s-1}\mathopen{}\mathclose{\left|D_i}\right|}q. \end{align}\]

  The above proof completes the induction and shows that \(C(R^{(1)})\), the contribution from arcs in \(\mathrm{Act}(x,R^{(1)})\) in stage II.\(l\) to 75 , is exactly \(q\).

6.3 Towards a tight lower bound for \(k\)-distinctness↩︎

In this subsection, we show that the next conjecture suffices to lift our nearly tight lower bound for \(k\)-cycle finding in the low maximum degree regime to a nearly tight lower bound for \(k\)-distinctness.

By definition, \(D\) is the union of \(D[\mathcal{P}]\) over all partitions \(\mathcal{P}\). Therefore, the reverse inequality, \(Q(k\mathsf{\text{-}CYCLE}|_{D[\mathcal{P}]}) \leq Q(k\mathsf{\text{-}CYCLE}|_{D})\), trivially holds. Why is the conjecture plausible? Intuitively, in \(k\mathsf{\text{-}CYCLE}|_{D}\) we are computing \(k\mathsf{\text{-}CYCLE}\) without access to the partition of the input graph, while in \(k\mathsf{\text{-}CYCLE}|_{D[\mathcal{P}]}\) we are given this extra information. However, the symmetries of the \(k\mathsf{\text{-}CYCLE}\) problem appear to make this extra information hard to exploit. This is somewhat reminiscent of the fact that increasing the alphabet size of a highly symmetric function does not increase its approximate degree (a measure of complexity) as established by Ambainis in [52]. Indeed, the conjecture may also hold for functions other than \(k\mathsf{\text{-}CYCLE}\), in particular, functions satisfying graph symmetries.

We now prove that the conjecture implies a tight lower bound for \(k\)-distinctness. The idea is that (i) \(k\mathsf{\text{-}CYCLE}|_{D[\mathcal{P}]}\) is \(k\)-distinctness in disguise and (ii) our lower bound for \(k\)-cycle in fact also holds for \(k\mathsf{\text{-}CYCLE}|_{D}\). The next two lemmas show (i) and (ii) respectively.

Proving the next lemma requires some more basic facts about random graphs, which we collect here. The proof of this fact is given in 7.

We remark that for the second and third items, we can in fact lower bound the probabilities by quantities considerably larger than \(1 - o(1/\log^k(n))\), as will be clear from the proof, but the results as stated suffice for our purpose of proving the next lemma.

Acknowledgments↩︎

We thank François Le Gall for suggesting the study of quantum algorithms in the edge list model. We thank Yassine Hamoudi for helpful discussions on [2] and for simplifying our original proof of the Mirroring Lemma (5) in the binary-alphabet case. We thank anonymous reviewers for identifying errors in the Mirroring Lemma in submitted versions of this paper; these have been corrected in the current version.

Amin Shiraz Gilani is supported by the U.S. Department of Energy ASCR Quantum Testbed Pathfinder program (awards DE-SC0019040 and DE-SC0024220) and the U.S. Department of Energy, Office of Science, Accelerated Research in Quantum Computing, Fundamental Algorithmic Research toward Quantum Utility (FAR-Qu) program. Daochen Wang is supported by NSERC Grants CRC-2023-00039, RGPIN-2024-06493, and DGECR-2024-00113. Xingyu Zhou is supported by NSERC Grant RGPIN-2024-06493.

7 Appendix: Facts about random graphs↩︎

For completeness, we prove facts on random graphs used in the main body in this appendix.

References↩︎

---

1. University of Maryland. asgilani@umd.edu↩︎

2. University of British Columbia. wdaochen@gmail.com↩︎

3. The Pennsylvania State University. pei.wu@psu.edu↩︎

4. University of British Columbia. zxingyu@cs.ubc.ca↩︎

5. In general, for integers \(b\geq a \geq 1\), \(\Sigma\) a finite non-empty set, and a string \(x\in \Sigma^b\): a length-\(a\) subsequence of \(x\) is a string of the form \(x_{i_1}x_{i_2}\dots x_{i_a}\) for some integers \(1\leq i_1<i_2<\dots<i_a \leq b\).↩︎

6. We use the notation \(\widetilde{O},\widetilde{\Omega},\widetilde{\Theta}\) to denote big-\(O\),\(\Omega\), and \(\Theta\) up to poly-logarithmic factors.↩︎

7. We assume \(d\) is known in advance. This is for simplicity in presentation: by using approximate counting to estimate \(d\), it can be seen that the bound holds even if \(d\) is not known in advance. The same comment applies to \(\mathop{\mathrm{\mathsf{TriangleVertex}}}\).↩︎

8. While \(\mathop{\mathrm{\mathsf{Triangle}}}\) 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.↩︎

9. Note that the best known quantum query lower bound for \(k\mathsf{\text{-}DIST}\) for every \(k\geq 4\) (see [25], [26]) is also polynomially far from the upper bound witnessed by Belovs’s learning graph algorithm.↩︎

10. We may assume \(m/d \in \mathbb{Z}\) without loss of generality. We will not make further remarks like this in the technical overview.↩︎

11. We chose this name because \(\Sigma\) resembles a rotated M and \(\mathrm{\Sigma MAJ}_n\) is (a restriction of) the composition of two \(\mathrm{MAJ}_n\)s.↩︎

12. The arguments here are better understood by considering \(n\), which represents the number of vertices in the graph. But recall that 3 concerns the regime \(m=\Theta(n)\), so all results here can also be expressed in terms of \(m\).↩︎

13. To quantum query lower bound experts: the standard quantum adversary method [36], [37] 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., [38]–[40].↩︎

14. [42] goes much beyond merely interpreting Belovs’s algorithm. However, in this paper, we will only use [42] to aid our explanation of Belovs’s algorithm.↩︎

15. While 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.↩︎

16. As a simple example, \(\mathop{\mathrm{\mathrm{ED}}}_m \colon [s]^m \to \{0,1\}\) when \(s < m\) is the constant \(1\) function by the pigeonhole principle so \(Q(\mathop{\mathrm{\mathrm{ED}}}_m) = 0\); but when \(s\geq m\), \(Q(\mathop{\mathrm{\mathrm{ED}}}_m) = \Theta(m^{2/3})\).↩︎

17. In general, for integers \(b\geq a \geq 1\), \(\Sigma\) a finite non-empty set, and a string \(x\in \Sigma^b\): a length-\(a\) subsequence of \(x\) is a string of the form \(x_{i_1}x_{i_2}\dots x_{i_a}\) for some integers \(1\leq i_1<i_2<\dots<i_a \leq b\).↩︎

18. This assumption is without loss of generality under our convention in the preliminaries of what \(Q(\mathop{\mathrm{\mathsf{TriangleEdge}}}_{m,d})\) means when the alphabet size is not specified.↩︎

19. The \(Q(\mathop{\mathrm{\mathsf{HIDE}}}_m[f]) = \Omega(\sqrt{m/n}\cdot Q(f))\) part of 7 also holds for partial \(f\) (like \(\mathop{\mathrm{\mathrm{ED}}}_d'\)) by the same argument.↩︎

20. An alternative way to see this is simply that \(\mathrm{\Sigma MAJ}_n\) is the composition of two gapped \(\mathrm{MAJ}_n\) functions, each of which has constant randomized query complexity. Therefore, the randomized query complexity of the composition is also constant using the fact that \(R(f\circ g) = O(R(f)\cdot R(g)\cdot \log(R(f)))\).↩︎

21. Formally, \(\mathbb{C}^K\) is identified with a tensor product space \(\bigotimes_{i=1}^k\mathbb{C}^{\Sigma_i}\) for some alphabets \(\Sigma_i\) and the output on measuring the string \(w = w_1 \dots w_k\), where \(w_i\in \Sigma_i\), is the substring \(w' \mathrel{\vcenter{:}}= w_1 \dots w_{k'}\) for some \(k'\leq k\).↩︎

22. For intuition only, if we view each non-\(\bot\) symbol in \(x\) as contributing one unit of “degree”, then this fact is akin to the polynomial method [32]. We remark that (essentially) this fact alone can be used to prove non-trivial lower bounds, see, e.g., [20].↩︎

23. Suppose basis state \(\ket{i',u',w'}\ket{x'}\) is orthogonal to \(\ket{i,u,w}\ket{x}\). If \((i',u',w')\neq (i,u,w)\), then it is clear that the two states remain orthogonal after applying \(\Pi^{ \begin{tikzpicture}[scale=0.1,baseline=(current bounding box.center)] \draw (0,0) -- (1,2) -- (2,0); \end{tikzpicture}}_{[r,\infty)}\mathop{\mathrm{\mathcal{R}}}\) since the operator can only act non-trivially on the input register. If \((i',u',w') = (i,u,w)\) and \(x_j\neq x'_{j}\) for some \(j\neq i\), then the two states still remain orthogonal since \(\mathop{\mathrm{\mathcal{R}}}\) does not act on the \(I_j\) register and \(\Pi^{ \begin{tikzpicture}[scale=0.1,baseline=(current bounding box.center)] \draw (0,0) -- (1,2) -- (2,0); \end{tikzpicture}}_{[r,\infty)}\) is diagonal in the \(\{\ket{z} \mid z\in ([N]\cup \{\bot\})^m\}\) basis. The case \((i',u',w') = (i,u,w)\) and \(x_i\neq x'_i\) is forbidden by the assumption that the basis states lie in the support of \(\Pi_\perp\). We will later reuse similar arguments without comment.↩︎

24. More formally, because the underlying distribution of \(G_{n,p}\) is just \(\mathop{\mathrm{\mathrm{E}}}_{m}[G_{n,m}]\) for some distribution on the edge count \(m\).↩︎