Quantum Property Testing in Sparse Directed Graphs

In this modern big data era, the size of inputs has grown so much that even just reading the full input has become extremely expensive computationally. To tackle this challenge, the framework of property testing was initiated. It focuses on designing ultrafast algorithms (also known as “testers”) that read only a small part of the input, and distinguish inputs that satisfy some property from inputs that are “far” from satisfying it. As a possible use-case, when the exact computation is expensive, one can use property testing algorithms as a precursor to running the final algorithm. If the input does not pass the property testing test, we can safely reject it, without running the expensive final computation.

At the same time, the field of quantum computing has significantly influenced many computer science paradigms, including cryptography, algorithms, and large-scale data processing. This new perspective on computer science based on quantum physics has sparked many fresh research directions. This includes the topic of this work, which combines quantum computing and property testing. More specifically, we consider quantum algorithms for graph property testing.

Graphs are of paramount importance for instance when it comes to understanding large datasets, since they provide a natural way to represent and analyze complex relationships inside datasets. Goldreich, Goldwasser, and Ron [28] were the first to consider graphs in the context of property testing. Formally, given some form of query access to an unknown graph $G$ on $N$ vertices, and a property $𝒫$ of interest, the goal is to distinguish with high probability if $G$ satisfies the property $𝒫$, or whether it is “far” from all graphs that satisfy $𝒫$, with a suitable notion of farness. In [28], the “dense” model was considered, where a graph is accessed through adjacency queries: for a pair of vertices $(u,v)$, the query reveals whether $(u,v)$ is an edge in the graph. In this model, a graph $G$ is $\epsilon$-far from satisfying $𝒫$ if one needs to add or remove at least $\epsilon N^2$ edges of $G$ to obtain a graph that satisfies $𝒫$.

In a later work, Goldreich and Ron [29] introduced the “bounded-degree” model for testing sparse graphs, focusing on the properties of bipartiteness and expansion. In this model, a $d$-bounded degree graph $G$ with $N$ vertices is accessed by performing neighbor queries: for a vertex $v$ and an integer $i\in [d]$, the query $(v,i)$ returns either the $i$-th neighbor of $v$, or some special symbol if $v$ has less than $i$ neighbors. The graph $G$ is said to be $\epsilon$-far from some property $𝒫$, if one needs to add or delete at least $\epsilon dN$ edges of $G$ to obtain a graph that satisfies $𝒫$. Over the last two decades, there has been a significant number of works in this model, and we refer the interested reader to the books by Goldreich [26] and Bhattacharyya and Yoshida [14] and several surveys [24, 40, 23, 41].

Some researchers have considered efficient quantum algorithms for testing both classical and quantum objects, see for instance [18, 6, 31, 12, 10] and the survey [36]. Notably, the authors in [7] initiated the study of bounded degree graph property testing in the quantum model. One important result in this context is the result of [12], who proved that there can be exponential quantum advantage in the bounded degree graph model of property testing. However, as mentioned in their paper, the graph property admitting the exponential quantum advantage is not a natural one.

While all of the aforementioned works consider undirected graphs, many real-world instances (such as the world wide web) actually correspond to directed graphs. Consequently, Bender and Ron [13] introduced a model of property testing for directed graphs, focusing on the properties of acyclicity and connectivity. Following that work, we open a new research line by studying quantum algorithms for testing directed graphs. As we will see, by doing so, we address new fundamental questions in the field of quantum complexity. Answering them requires using recent techniques and partially answering some new or open questions.

As described in [13], for bounded-degree directed graphs there are two natural query models: (i) the unidirectional model, where the algorithm is allowed to query the outgoing edges of a vertex, but not the incoming edges, and (ii) the bidirectional model, where the algorithm can query both the incoming and outgoing edges of a vertex. Interestingly, [13] showed that strong connectivity is testable in the bidirectional model (i.e., it can be tested with a number of queries that depends on $\epsilon$ but not on $N$), but it requires $\mathrm{\Omega }(\sqrt{N})$ queries in the unidirectional model. Later, the testability of other graph properties like Eulerianity, vertex and edge connectivity [37, 46, 25, 21] was also shown in the bidirectional model. While there is a clear distinction between the two models, Czumaj, Peng and Sohler [22] showed that if a property is testable in the bidirectional model, then it has a tester with sublinear (i.e., $o(N)$) query complexity in the unidirectional model.

In this work, we consider a particularly important problem in the unidirectional model: the problem of testing subgraph-freeness. More precisely, we examine the problem of testing “$k$-source-subgraph-freeness”, where the goal is to test $H$-freeness for some constant-sized subgraph $H$ with $k$ “source components”, where a source component is a strongly connected subgraph that has no incoming edges. This problem was first studied by Hellweg and Sohler [32], and they provided a testing algorithm that performs $O(N^{1-1/k})$ queries. They also proved a tight lower bound of $\mathrm{\Omega }(N^{2/3})$ for the $k=3$ case (see [32, Theorem 1 and Theorem 3]). Very recently, Peng and Wang [38] proved a matching lower bound for any constant $k$. In particular, they showed that $\mathrm{\Omega }(N^{1-\frac{1}{k}})$ queries are necessary for testing $k$-star-freeness (which is a special case of testing $k$-source-subgraph-freeness) in the unidirectional model, for arbitrary $k$ (see [38, Theorem 1.2]). Notice that asymptotically the complexity of testing $k$-star-freeness becomes $\mathrm{\Omega }(N)$. This also proves that the aforementioned reduction of [22] can not be made much stronger: for the property of $k$-star-freeness, the separation between the query complexities in the bi- and unidirectional models is maximal, as this property can be tested using constant many queries in the bidirectional model.

A closely related problem to finding $k$-stars in graphs is finding $k$-collisions in integer sequences. The two mentioned classical papers on subgraph-freeness testing [32, 38] actually consider a collision-type intermediate problem for proving their lower bounds. As we are also going to do so, let us look at some related, known results.

The problem of collision finding is a ubiquitous problem in the field of algorithm theory with wide applications in cryptography. Here, given a sequence $s$ of $N$ integers, the goal is to find a duplicate in $s$. If one has the guarantee that $\mathrm{\Theta }(N)$ elements of the sequence are duplicated, which is the case for instance when the sequence consists of uniformly random integers from $[N]$, it is well-known that classically $\mathrm{\Theta }(\sqrt{N})$ queries are necessary and sufficient due to the birthday paradox. In the quantum model, this can be solved with query complexity $\mathrm{\Theta }(N^{1/3})$ by the algorithm of Brassard, Høyer and Tapp [17]. The matching lower bound was first stated for a specific set of hard instances known as $2$-to-$1$ (i.e., each integer appears exactly twice or not at all) by Aaronson and Shi [3]. For some constant integer $k\ge 3$, those results can be further extended to finding $k$-collisions in a random input with suitable alphabet size, so that it contains $\mathrm{\Theta }(N)$ $k$-duplicates with high probability. The classical query complexity for this problem is $\mathrm{\Theta }(N^{1-1/k})$ [32, 38], and quantumly it is $\mathrm{\Theta }\left(N^{\frac{1}{2}\left(1-\frac{1}{2^k-1}\right)}\right)$ [34]. The situation is more complex for non-random inputs.

Remarkably, the complexity of testing $k$-collision-freeness (i.e., the absence of $k$-collisions) is harder to settle on the lower bound side than the finding version. In this work, we are going to focus on the hardness of distinguishing inputs that have linearly many collisions from those that do not have any. For $k=2$, the two problems have the same complexity, since intuitively the only way to distinguish is to find a collision. This can be formalized easily in the classical case. Quantumly, this is more challenging, but the lower bound in [3] proved the hardness of distinguishing between $2$-to-$1$ instances and ones with no duplicate.

However, for larger $k$, distinguishing such inputs might be easier than finding a collision. The classical upper bound of $O(N^{1-1/k})$ queries is straightforward for the finding variant. In the lower bounds of [32, 38], the authors consider the distinguishing version, so classically the question is settled. But in the quantum setting, the upper and lower bounds of [34] are tight only for finding $k$-collisions in random inputs, and for the distinguishing variant, we are not currently aware of anything better than the $\mathrm{\Omega }(N^{1/3})$ lower bound corresponding to the $k=2$ case. To our knowledge, this problem has not yet been studied in the quantum setting.

In this work, we present two lines of results for quantum property testing of graph properties.

In the first line, we consider the problem of testing $k$-source-subgraph-freeness in the unidirectional model. This problem is almost maximally hard for large $k$ in the classical regime, and we show that it admits an almost quadratic advantage in the quantum setting.

In order to prove the above result, we connect it to the problem of finding $k$-collisions. In [34], an algorithm is given for finding $k$-collisions in sequences of random integers. We generalize this to the context of graph property testing in two ways: finding a subgraph (instead of a collision); and considering graphs that are far from being $H$-free (instead of random).

Moreover, we prove that this quantum advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials.

For proving graph property testing lower bounds, both the classical works of [32] and [38] prove collision testing lower bounds using the proportional moments technique of [39]. At the heart of this technique is a construction of two positive integer random variables, $X_1$ and $X_2$, with different expectations but with the following conditions on the first $k-1$ moments: $𝔼[X_1]/𝔼[X_2]=𝔼[X_1^2]/𝔼[X_2^2]=\mathrm{\dots }=𝔼[X_1^{k-1}]/𝔼[X_2^{k-1}]$. Such a construction leads to a randomized query complexity lower bound of $\mathrm{\Omega }(N^{1-\frac{1}{k}})$ for various property testing problems such as $k$-collision-freeness [38]. Having a quantum version of this technique has been identified as an important open problem [6], since this could be used to pave the way to stronger quantum lower bounds in related settings. We modestly made progress to this quest for the special case of testing $k$-collision-freeness.

In [34], in addition to the algorithm we mentioned, they also prove a matching lower bound showing that their algorithm for finding $k$-collisions in random inputs is optimal. However, this time we cannot reuse those techniques for our purpose for two main reasons. First, the property testing variant of this problem could be easier. Moreover, their lower bound technique requires random inputs and hence it does not apply to our case. This is why we use yet another method, that of dual polynomials, to prove our lower bound.

In the second line of results, we show that not all problems in graph property testing admit such a quantum speedup. This fact even remains valid for the case of undirected graphs. For this, we consider the property testing variant of the famous problem of $3$-colorability: namely, distinguishing whether an unknown undirected graph $G$ can be properly colored with $3$ colors, or one needs to modify a large fraction of its edges to make it $3$-colorable. In the classical bounded degree setting, this problem has been studied by [15], who proved a lower bound of $\mathrm{\Omega }(N)$ queries. In this work, we present a simple argument that proves that there exists no sublinear quantum tester either for this problem. Our result is stated as follows:

Our work raises several important open questions. First, there is still a gap between our lower and upper bounds on the quantum query complexity of testing $k$-collision-freeness. In [35], the authors keep using the dual polynomial method to improve the lower bound of [19] for the $k$-distinctness problem. They achieve this by using a slightly different dual polynomial for ${\mathrm{THR}}_N^k$, where they allow more weight on the false positive inputs. This makes it impossible to prove the high correlation of the dual and the primal functions, so they use a modified block composition. Our technique might be combined with this other approach to improve our lower bound to $\tilde{\mathrm{\Omega }}(N^{1/2-1/(4k)})$.

The authors in [6] stated it as an open question if one could use a variant of the proportional moments result of [39] to prove lower bounds on quantum algorithms. We leave this question open, and conjecture that a similar result holds in the quantum setting with a lower bound of $\mathrm{\Omega }\left(N^{\frac{1}{2}\left(1-\frac{1}{k}\right)}\right)$. This work may be considered as a proof of this conjecture for the special case of $k$-collision-freeness, and we hope that it will serve as a step towards proving it in general.

In [22], it was proved that if a graph property can be tested with $O(1)$ queries in the bidirectional model, then it can be tested using $O(N^{1-\mathrm{\Omega }(1)})$ queries in the unidirectional model. It would be very interesting to investigate if it also implies a quantum tester with query complexity, say $O(N^{1/2-\mathrm{\Omega }(1)})$.

Let us denote $[n]=\{1,\mathrm{\dots },n\}$ and ${[n]}_0=\{0,\mathrm{\dots },n\}$. When dealing with Boolean variables, we will usually use $b\in \{-1,1\}$ instead of $b\in \{0,1\}$. We can get to one from the other easily with the mapping $b\mapsto 1-2b$, or its inverse, which means that $-1$ is going to be treated as the “true” or “accepting” value. The reason for using $\{-1,1\}$ is that when dealing with dual polynomials, it is easier to use this notation.

We denote by $1^n$ the length-$n$ binary vector made only of $1$s, and respectively $-1^n$. The Hamming weight $|x|$ of $x\in {\{-1,1\}}^n$ is then defined as the number of $-1$s in $x$, that is $|x|=\mathrm{\#}\{i\in [n]:x_i=-1\}$. Let $H_{\le w}^n=\{x\in {\{-1,1\}}^n:|x|\le w\}$ denote the set of length-$n$ binary vectors with Hamming weight at most $w$. For any $x\in ℝ$, $\mathrm{sgn}(x)=1$ when $x\ge 0$, and $-1$ otherwise.

For a polynomial $p$, let $\mathrm{deg}(p)$ denote its degree. The composition $f\circ g:{\{-1,1\}}^{nm}\to \{-1,1\}$ of two Boolean functions $f:{\{-1,1\}}^n\to \{-1,1\}$ and $g:{\{-1,1\}}^m\to \{-1,1\}$ is defined as $(f\circ g)(x)=f(g(x_1),\mathrm{\dots },g(x_n))$ where $x=(x_1,\mathrm{\dots },x_n)$ with each $x_i\in {\{-1,1\}}^m$.

A directed graph or digraph $G=(V,E)$ is a pair of a vertex set $V$ and an edge set $E$. The latter consists of directed edges that are ordered pairs of vertices: we say that $(u,v)\in E$ is directed from $u$ to $v$ where $u,v\in V$. We say that there is a directed path from $s=v_0$ to $t=v_{l+1}$ (with $s,t\in V$) if there exists an integer $\mathrm{\ell }$ and vertices $v_1,\mathrm{\dots },v_{\mathrm{\ell }}\in V$ such that $\forall i\in {[\mathrm{\ell }]}_0:(v_i,v_{i+1})\in E$. A digraph $G=(V,E)$ is called strongly connected if for every $u\in V$ and $v\in V\setminus \{u\}$, there exists a directed path from $u$ to $v$. A subgraph of a graph $G=(V,E)$ is any graph $G^{\prime }=(V^{\prime },E^{\prime })$ satisfying $V^{\prime }\subseteq V$, $E^{\prime }\subseteq E$ and $E^{\prime }\subseteq V^{\prime }\times V^{\prime }$.

Finally, throughout this work, notations $O(\cdot )$ and $\mathrm{\Omega }(\cdot )$ will be hiding the dependencies on parameters $\epsilon$, $k$ and $d$ that we consider to be constants. Additionally, we will use $\tilde{O}(\cdot )$ and $\tilde{\mathrm{\Omega }}(\cdot )$, where we hide poly-logarithmic dependencies on the parameters.

In query complexity, we consider inputs $x\in {\mathrm{\Sigma }}^I$ over a finite alphabet $\mathrm{\Sigma }$ and indexed by a set $I$. They are not given explicitly to the algorithm. Instead, the algorithm has query access to an input oracle ${𝒪}_x:I\to \mathrm{\Sigma }$ encoding $x$ by ${𝒪}_x(i)=x_i$. Quantumly, the query access is described by the unitary operator $O_x|i⟩|z⟩=|i⟩|z\oplus x_i⟩$, for $z\in \mathrm{\Sigma }$ and $i\in I$, where $\oplus$ is usually the bit-wise exclusive-OR operation up to some binary encoding of the elements of $\mathrm{\Sigma }$. But our lower bound technique applies to any reversible operation $\oplus$.

Query complexity measures the minimum number of queries that an algorithm has to make in order to decide whether a property $𝒫:D_{𝒫}\subseteq {\mathrm{\Sigma }}^I\to \{-1,1\}$ is satisfied, for an arbitrary input $x\in D_{𝒫}$. Since the work of [11], it has been known that in the Boolean case (i.e., when $\mathrm{\Sigma }=\{-1,1\}$), the acceptance probability of a $T$-query bounded-error quantum algorithm is a multivariate polynomial (in all the $x_i$’s) of degree at most $2T$.

In this work, two kinds of inputs are going to play a crucial role. When the input is a sequence $s=(s_1,\mathrm{\dots },s_N)$ of positive integers $\le R$, then $I=[N]$ and $\mathrm{\Sigma }=[R]$.

In the undirected bounded-degree graph model, we have query access to the adjacency list of an undirected graph $G=(V,E)$ with maximum degree $d$, represented as an oracle ${𝒪}_G:V\times [d]\to V\cup \{\perp \}$. Then we can set $I=V\times [d]$ and $\mathrm{\Sigma }=V\cup \{\perp \}$, such that for any $v\in V$ and $i\in [d]$, we have the following:

For bounded-degree directed graphs, there exist two query models. In the bidirectional model, we have access to both the outgoing and incoming edges of each vertex. Correspondingly, it is imposed that both the in- and out-degrees of a vertex are bounded by $d$. In the unidirectional model, we can only make queries to the adjacency list of the outgoing edges, and we impose only that the out-degrees of a vertex are bounded by $d$. Since in this work the primary focus will be on the latter model, let us formally define it below.

In the unidirectional bounded-degree graph model, we have query access to the adjacency list of a digraph $G=(V,E)$ where the out-degree of every vertex is at most $d_{\mathrm{out}}$: for all $v\in V$: ${\text{deg}}_{\mathrm{out}}(v)\le d_{\mathrm{out}}$. This access is represented as an oracle ${𝒪}_G^{\mathrm{out}}:V\times [d_{\mathrm{out}}]\to V\cup \{\perp \}$. Then we can set $I=V\times [d_{\mathrm{out}}]$ and $\mathrm{\Sigma }=V\cup \{\perp \}$, such that for any $v\in V$ and $i\in [d_{\mathrm{out}}]$, we have the following:

For completeness, we note that in some of the previous works on the unidirectional model, the authors do impose the degree bound on both the out- and in-degree (see, e.g., [22]). This is mostly because this makes for an easier comparison between the uni- and bidirectional models, as this way they allow the same set of graphs. In this work, we assume that only the out-degrees of the vertices are bounded by $d$.

In total decision problems, the algorithm has to decide if the input satisfies a property or not. In the case of property testing, the question is relaxed: the algorithm has to distinguish inputs that satisfy the property from those that are “far” (according to some distance measure) from any input that satisfies it.

The choice of distance measure usually depends on the query model considered. As discussed before, the general query access can be viewed as black box access to the input $x\in {\mathrm{\Sigma }}^I$ where querying an index $i\in I$ reveals $x_i\in \mathrm{\Sigma }$. This way, the distance of two objects is described as the proportion of positions where they differ:

Applying this to the case of bounded-degree graphs with degree bound $d$ and query access to the adjacency list, the distance of two graphs is the number of edges where they differ divided by $|V|d$. The distance of an object $x$ from a property $𝒫$ is the minimum distance between $x$ and any object that satisfies $𝒫$.

Notice that no restriction is given on the acceptance probability of the algorithm for inputs that do not satisfy $𝒫$ but are $\epsilon$-close to it.

We are not going into details about quantum computing, because for this paper, it suffices to state very few results in the field and use them in a black box way. One of the most important results in quantum computing is Grover’s algorithm for unordered search [30]: finding a marked element in an unordered database of size $N$ takes $\mathrm{\Theta }(N)$ queries classically, but the quantum query complexity of the same task is $\mathrm{\Theta }(\sqrt{N})$. We are going to use a particular variant of this result that has been used many times in the literature (see e.g., [4, Item 3 in Section 2.2], which was implicitly proved in [16]).

We now formally define the problems we study and argue about certain relations between them. While the problems are phrased as decision problems, ultimately we will care about the quantum query complexity for testing the corresponding properties. The complexity is going to be parameterized by a parameter $k$. Moreover, the parameters $k,\epsilon$ and the degree bound $d$ are all considered to be constants throughout this paper.

Let us start with some definitions that will be useful to define our problems precisely.

Notice that a $k$-star has $k$ source components each consisting of a single vertex.

We will now state the decision variants of several problems. The “property” corresponding to a decision problem is the set of inputs that should be accepted in the decision problem.

To illustrate our algorithm, we first consider the $k=2$ case to build some intuition. Here, our algorithm generalizes the BHT algorithm for collision finding [17] in the context of graphs. The high level idea is that if we manage to sample a vertex from each of the two source components of an $H$-subgraph (a collision), then by querying their “surroundings” we will discover the $H$-instance. In the following, we set $h=|V(H)|$, the number of vertices in $H$.

1. 1.

   Sample a uniformly random vertex subset $𝒮$ of size $t=\mathrm{\Theta }(N^{1/3})$ in $G$. Perform a depth-$h$ BFS from every vertex in $𝒮$.

2. 2.

   Perform Grover search over the remaining vertices $V\backslash 𝒮$ in the following way. A vertex $v$ is marked if there exists another vertex $u\in 𝒮$ such that $u$ and $v$ are from the 2 different source components of an $H$ subgraph of $G$.

3. 3.

   If any occurrence of $H$ in $G$ is found, output Reject. Otherwise, output Accept.

Note that if $G$ is $H$-free, then the above algorithm will always accept. Now we need to argue that if $G$ is $\epsilon$-far from being $H$-free, then with constant probability, the above algorithm will find a copy of $H$ and thus will output reject.

By Proposition 12, with high probability, a constant fraction of the $t$ vertices in $𝒮$ are part of a source component in source-disjoint $H$-subgraphs of $G$. For such vertices, the BFS in step 1 will discover the entire source component, as well as all other vertices reachable from that source component in $H$. Then, in step 2 we search for a vertex that is in the remaining source component of such an instance of $H$ that we already partly discovered. This can be verified by doing a depth-$h$ BFS from it and checking if this completes an $H$-instance with one of the previously sampled vertices’ neighborhoods. As we mentioned, by Proposition 12 with high probability there are $\mathrm{\Omega }(t)$ many marked vertices. This proves the correctness of the algorithm.

Finally, we bound the algorithm’s query complexity. Step 1 makes $O(t)=O(N^{1/3})$ many (classical) queries. In step 2 we use Theorem 6 and Remark 7: checking whether a vertex is marked requires running a depth-$h$ BFS from it, which costs $c=O(1)$ queries. We argued that there are $\mathrm{\Omega }(t)$ many marked vertices, so Grover search makes $O(\sqrt{N/t})=O(N^{1/3})$ quantum queries.

We are now ready to state our general upper bound result.

The algorithm and proof follow the same lines as the $k=2$ case. In order to extend the $k=2$ case described above to larger $k$, we first try to find many partial $H$-instances with $k-1$ source components found, and then extend one of them to a complete $H$-instance. We present a brief description of our algorithm, where $h$ is the number of vertices of $H$:

1. 1.

   Sample a uniformly random vertex subset ${𝒮}_1$ in $G$ of size $t_1$. Perform a depth-$h$ BFS from every vertex in ${𝒮}_1$. Let ${𝒮}_1^{\prime }={𝒮}_1$.

2. 2.

   For iterations $i=2$ to $k-1$, do the following:

   1. (a)

      Perform a Grover search $t_i$ times on the vertices $V\setminus {𝒮}_{i-1}^{\prime }$ in the following way. A vertex $v$ is marked if there exist $i-1$ other vertices $u_j\in {𝒮}_j$ for each $j\in [i-1]$ such that $u_1,\mathrm{\dots },u_{i-1}$ and $v$ are from $i$ different source components of an $H$ subgraph of $G$. If we do not find $t_i$ vertices like this, output Reject, otherwise let ${𝒮}_i$ denote the set of the vertices $v$ that we found.

   2. (b)

      Set ${𝒮}_i^{\prime }={𝒮}_{i-1}^{\prime }\cup {𝒮}_i$.

3. 3.

   Perform Grover search on $V\backslash {𝒮}_{k-1}^{\prime }$ to find a complete $H$-instance. I.e., a vertex $v$ is marked if there exist $k-1$ other vertices $u_j\in {𝒮}_j$ for each $j\in [k-1]$ such that $u_1,\mathrm{\dots },u_{k-1}$ and $v$ are from the $k$ different source components of an $H$ subgraph of $G$.

4. 4.

   If any occurrence of $H$ in $G$ is found, output Reject and terminate the algorithm. Otherwise, output Accept.

The correctness proof can be found in the full version of the paper [9].

Technically, the problem we use in the proof of Theorem 14 is slightly more restricted than $k$-collision-freeness: we want to distinguish no $k$-collision from many distinct collisions of size at least $k$.

Notice that this problem is not a property testing problem, as the outcome is not determined based on the distance between inputs. Nevertheless, it is a valid promise problem and a special case of testing $k$-collision-freeness, which we use to prove lower bounds on the other problems of interest.

To prove a bound on the $\mathrm{Collision}$ function, we will actually relate it to the composition of two more elementary functions $g,h$, where by composition we mean $(g\circ h)(x)=g(h(x_1),\mathrm{\dots },h(x_n))$ (where $x=(x_1,\mathrm{\dots },x_n)$ and each $x_i$ is a binary vector of appropriate dimension). Let us define (i) the threshold function ${\mathrm{THR}}_N^k:{\{-1,1\}}^N\to \{-1,1\}$ which is $-1$ if the input bitstring contains at least $k$ many $-1$s, and it is 1 otherwise; and (2) the gap version of $\mathrm{OR}$, that is ${\mathrm{GapOR}}_R^{\gamma }:D_{{\mathrm{GapOR}}_R^{\gamma }}\subset {\{-1,1\}}^R\to \{-1,1\}$ which takes value 1 if the input is $1^R$, $-1$ if the input contains at least $\gamma R$ many $-1$s, and is undefined otherwise. We show that the double-promise approximate degree of ${\mathrm{GapOR}}_R^{\gamma }\circ {\mathrm{THR}}_N^k$ lower bounds the quantum query complexity of the collision problem.

Before proving this lemma, we prove some helper propositions. In order to apply the dual polynomial method for partial symmetric functions, we start by proving that ${\mathrm{Collision}}_{N,R^{\prime }}^{k,{\gamma }^{\prime }}$ is at least as hard as a very similar problem. We introduce a “dummy-augmented” version ${\mathrm{dCollision}}_{N,R}^{k,\gamma }:D_{{\mathrm{dCollision}}_{N,R}^{k,\gamma }}\subseteq {[R]}_0^N\to \{-1,1\}$ of the problem ${\mathrm{Collision}}_{N,R}^{k,\gamma }$ for the purpose of proving Lemma 23, where now the input sequence can have integer $0$, but those $0$s are just ignored when they occur. We show that it is enough to prove a lower bound for this second version.

The proof is deferred to the full version of the paper [9]. The following proposition relates $\mathrm{dCollision}$ to $\mathrm{GapOR}\circ \mathrm{THR}$.

We are now ready to give the proof of Lemma 23.