Technion, Israelckeren@cs.technion.ac.ilhttps://orcid.org/0000-0003-4395-5205
Tel-Aviv University<EMAIL_ADDRESS>Nagoya University,
<EMAIL_ADDRESS>Technion<EMAIL_ADDRESS>Tel-Aviv University<EMAIL_ADDRESS>Keren Censor-Hillel, Orr Fischer,
François Le Gall, Dean Leitersdorf, Rotem Oshman [500]Networks Network
algorithms [500]Theory of computation Distributed algorithms This project was
partially supported by the European Union’s Horizon 2020 Research and
Innovation Programme under grant agreement no. 755839. François Le Gall was
supported by JSPS KAKENHI grants Nos. JP19H04066, JP20H05966, JP20H00579,
JP20H04139, JP21H04879 and MEXT Quantum Leap Flagship Program (MEXT Q-LEAP)
grants No. JPMXS0118067394 and JPMXS0120319794.Mark Braverman 1 13th
Innovations in Theoretical Computer Science Conference (ITCS 2022) ITCS 2022
ITCS 2022 January 31–February 3, 2022 Berkeley, CA, USA 215 93

# Quantum Distributed Algorithms for Detection of Cliques

Keren Censor-Hillel  Orr Fischer  François Le Gall  Dean Leitersdorf  Rotem
Oshman

###### Abstract

The possibilities offered by quantum computing have drawn attention in the
distributed computing community recently, with several breakthrough results
showing quantum distributed algorithms that run faster than the fastest known
classical counterparts, and even separations between the two models. A prime
example is the result by Izumi, Le Gall, and Magniez [STACS 2020], who showed
that triangle detection by quantum distributed algorithms is easier than
triangle listing, while an analogous result is not known in the classical
case.

In this paper we present a framework for fast quantum distributed clique
detection. This improves upon the state-of-the-art for the triangle case, and
is also more general, applying to larger clique sizes.

Our main technical contribution is a new approach for detecting cliques by
encapsulating this as a search task for nodes that can be added to smaller
cliques. To extract the best complexities out of our approach, we develop a
framework for _nested_ distributed quantum searches, which employ checking
procedures that are quantum themselves.

Moreover, we show a circuit-complexity barrier on proving a lower bound of the
form $\Omega(n^{3/5+\epsilon})$ for $K_{p}$-detection for any $p\geq 4$, even
in the classical (non-quantum) distributed CONGEST setting.

###### keywords:

distributed graph algorithms, quantum algorithms, cycles, cliques, Congested
Clique, CONGEST

##  1 Introduction

Quantum distributed computing. The power of quantum computing in the
distributed setting has recently been the subject of intensive investigations
[15, 21, 25, 26]. The main difference between classical and quantum
distributed computing is that the quantum setting, quantum information, i.e.,
quantum bits (qubits), can be sent through the edges of the network instead of
classical information (i.e., bits). Le Gall and Magniez [25] and Izumi and Le
Gall [21], in particular, have shown the superiority of quantum distributed
computing over classical distributed computing for two fundamental models, the
Congest model and the Congested Clique model.

The (classical) Congest model is one of the most studied models in classical
distributed computing. In this model, $n$ nodes communicate with each other
over the network by exchanging messages of $O(\log n)$ bits in synchronous
rounds. All links and nodes are reliable and suffer no faults. Each node has a
distinct identifier, but the network graph is not initially known to the
nodes. In the quantum version of this model (which we denote Quantum Congest),
as defined in [15, 25], the only difference is that the nodes can exchange
quantum information: each message exchanged consists of $O(\log n)$ quantum
bits instead of $O(\log n)$ bits in the classical case. In particular,
initially the nodes of the network do not share any entanglement. Achieving
quantum speedups in this setting is especially challenging since, as shown by
Elkin et al. [15], the ability to send quantum information is not helpful for
many crucial components of distributed algorithms (e.g., routing or broadcast
of information). Le Gall and Magniez [25] have nevertheless showed the
superiority of quantum distributed computing in this model: they constructed a
$\tilde{O}(\sqrt{n})$-round quantum algorithm for the exact computation of the
diameter of the network (for networks with small diameter), while it is known
that any classical algorithm in the Congest model requires $\tilde{\Omega}(n)$
rounds, even for networks with constant diameter [17].

The (classical) Congested Clique model is similar to the (classical) Congest
model, but it separates the input to the problem we are working on from the
communication topology: the input is some graph $G=(V,E)$, but the
communication topology allows all nodes to communicate directly with one
another (i.e., a clique). This model is close in flavor to massively-parallel
computing, but we focus only on rounds and communication, not memory. The
Quantum Congested Clique model is defined as the quantum version of the
Congested Clique model: the only difference is again that each exchanged
message consists of $O(\log n)$ quantum bits instead of $O(\log n)$ bits.
Izumi and Le Gall [21] showed that quantum distributed algorithms can be more
powerful than classical distributed algorithms in the Congested Clique model
as well: they constructed a quantum algorithm faster than the best known
classical algorithms for the All-Pair Shortest Path problem.

#### Distributed subgraph detection.

In the past few years there has been a surge of works on classical distributed
algorithms investigating the complexity of the subgraph detection problem,
which asks to detect the existence of a specified subgraph within the input
graph (which coincides with the communication network in the Congest and
Quantum Congest models). For small subgraphs, the subgraph-detection problem
is extremely _local_ , and yet it is challenging to solve in the Congest
model, due to the restricted bandwidth. Most prior work has focused on
detecting $p$-cliques (denoted below $K_{p}$) and $\ell$-cycles (denoted below
$C_{\ell}$), for small values of $p$ and $\ell$. In particular, in the
$p$-clique detection problem (also called the $K_{p}$-freeness problem), the
goal is to decide if the input graph contains a $p$-clique or not. If it
contains a $p$-clique then at least one node must output “yes”. Otherwise all
nodes must output “no”. (A detailed review of classical algorithms for
$p$-clique detection is given at the end of this section.)

Izumi et al. [22] recently showed that quantum algorithms can give an
advantage for triangle detection (i.e., $K_{3}$ detection), by constructing a
quantum algorithm with round complexity $\tilde{O}(n^{1/4})$ in the Quantum
Congest model (the best known classical algorithm for triangle detection, by
Chang and Saranurak [9], has complexity $\tilde{O}(n^{1/3})$). The key
technique used in [22] is _distributed Grover search_ , which was introduced
in [25] and consists in a distributed implementation of Grover’s celebrated
quantum algorithm [20].

#### Our results.

In this paper we further investigate the power of quantum distributed
algorithms. Using a new approach based on _nested_ distributed quantum
searches, we obtain quantum algorithms for $p$-clique detection, in both the
Quantum Congest model and the Quantum Congested Clique model, that outperform
their classical counterparts.

We first consider clique detection in the Quantum Congested Clique model. Our
results are summarized in the following theorem (the upper bounds we obtain
for $K_{p}$-detection with $p\geq 5$ are actually even stronger — see
Corollary 5.4 in Section 5).

######  Theorem 1.1.

There exists a quantum algorithm that solves $p$-clique detection with success
probability at least $1-1/\operatorname{poly}(n)$ in the Quantum Congested
Clique model with complexity $\tilde{O}(n^{1/5})$ for $p=3$ and
$\tilde{O}(n^{1-2/(p-1)})$ for $p\geq 4$.

For all values $p\geq 3$, the quantum algorithms we obtain by Theorem 1.1 are
faster than all known classical and quantum algorithms for $p$-clique
detection.

We then investigate clique detection in the Quantum Congest model.

######  Theorem 1.2.

There exists a quantum algorithm that solves $p$-clique detection with success
probability at least $1-1/\operatorname{poly}(n)$ in the Quantum Congest model
with complexity $\tilde{O}(n^{1/5})$ for $p=3$, and $\tilde{O}(n^{1-2/(p-1)})$
for $p\geq 7$.

For all $p=3$ and $p\geq 7$, the quantum algorithms we obtain by Theorem 1.2
are faster than all known algorithms for $p$-clique detection in the Congest
or Quantum Congest model. For $4\leq p\leq 6$, our approach currently does not
lead to an improvement over the classical algorithms from [4], which are
respectively $\tilde{O}(\sqrt{n})$, $\tilde{O}(n^{3/5})$ and
$\tilde{O}(n^{2/3})$. The reason is, informally, that in the Quantum Congest
model we (and all prior work on listing cliques) decompose the graph into
well-connected clusters, and simulate the Quantum Congested Clique on each
cluster; for very small cliques, the effort required to collect the edges
needed at each cluster overwhelms any time savings we currently gain from the
quantum search.

Finally, we consider lower bounds. While a tight $\Omega(\sqrt{n})$ lower
bound for $K_{4}$-detection is known in the (classical) Congest model [10],
tight lower bounds are not known for larger cliques, and there is no known
non-trivial lower bound for $K_{p}$-detection in the quantum setting. We show
a barrier for proving an $\Omega(n^{3/5+\epsilon})$ lower bound for $p$-clique
detection for any $\varepsilon>0$. Namely, such a bound would imply
breakthrough results in the field of circuit complexity, which are far beyond
the current state-of-the-art. We actually show this barrier for the
(classical) Congest model, but since any lower bound in the Quantum Congest
model also holds the Congest model, this barrier holds for the Quantum Congest
model as well.111Note that the statement of Theorem 1.3 is actually
interesting only for $p\geq 6$, since for $p=4,5$ we know that there exist
algorithms beating this barrier: as already mentioned, algorithms with
complexity $\tilde{O}(\sqrt{n})$ for $p=4$ and $\tilde{O}(n^{3/5})$ for $p=5$
are given in [4].

######  Theorem 1.3.

For any constant integer $p\geq 4$ and any constant $\epsilon>0$, proving a
lower bound of $\Omega(n^{3/5+\epsilon})$ on $p$-clique detection in the
Congest model would imply new lower bounds on high-depth circuits with
constant fan-in and fan-out gates.

Previously, several such barriers were known: in [13] it is shown that there
is an absolute constant $c$ such that proving a lower bound of the form
$\Omega(n^{1-c})$ for $C_{2k}$-detection would imply breaking a circuit
complexity barrier. In [14] such a barrier is shown for proving an
$\Omega(n^{\epsilon})$ lower bound on triangle detection, and in [5] a barrier
for proving a lower bound of $\Omega(n^{1/2+\epsilon})$ for $C_{6}$-detection
is given.

We refer to Table 1 for a summary of our results and a detailed comparison
with prior works.

Table 1: Our upper bounds for subgraph detection, and the corresponding known
results in the classical setting. Here $n$ denotes the number of nodes in the
network. Note that in Quantum Congested Clique, the algorithms we obtain for
$K_{p}$-detection with $p\geq 6$ are even faster than shown here, see
Corollary 5.4.

Subgraph |  Congested Clique |  Quantum Congested Clique
---|---|---
$K_{3}$ |  $\tilde{O}(n^{1/3})$ [9] |  $\tilde{O}(n^{1/4})$ [22]
$\tilde{O}(n^{1/5})$ Theorem 1.1
$K_{p}$ ($p\geq 4$) |  $\tilde{O}(n^{1-2/p})$ [4] |  $\tilde{O}(n^{1-2/(p-1)})$ Theorem 1.1

Subgraph |  Congest |  Quantum Congest
---|---|---
$K_{3}$ |  $\tilde{O}(n^{1/3})$ [9] |  $\tilde{O}(n^{1/4})$ [22]
$\tilde{O}(n^{1/5})$ Theorem 1.2
$K_{p}$ ($p\geq 7$) |  $\tilde{O}(n^{1-2/p})$ [4] |  $\tilde{O}(n^{1-2/(p-1)})$ Theorem 1.2
${\Omega}(\sqrt{n})$ [10]

#### Overview of our main technique.

Our key approach is to encapsulate $K_{p}$-detection as a search task, and use
a distributed implementation [25] of Grover search [20] to solve the task.
Grover’s algorithm consists of alternating between quantum operations called
_Grover diffusion operations_ , and checking operations, also called _checking
queries_. The total number of operations is ${O}(\sqrt{|X|})$, where $X$ is
the search domain. In the distributed implementation developed in [25], one
specific node of the network (the _leader_) executes each Grover diffusion
operation locally, but implements each query in a distributed way using a
distributed checking procedure. All prior works using this framework ([21, 25,
22]) considered the setting where the checking procedure is a classical
procedure. In this work, we consider checking procedures that themselves also
apply distributed Grover searches; we develop a framework to describe such
_nested_ distributed quantum searches (see Lemma 2.2 in Section 2). Our
framework can actually be applied in a completely “black-box” way to design
quantum distributed algorithms (i.e., no knowledge of quantum computation is
needed to apply this framework).

The main challenge in applying quantum search to the clique-detection problem
is that the search-space is very large: we must search over the
$\Theta(n^{p})$ possibilities, and a naïve approach would require
$\Theta(n^{p/2})$ quantum queries, which is extremely inefficient. Instead, we
show that one can carefully split the search into nested stages, so that each
stage adds a single node to the clique we are trying to find. Crucially,
nesting the stages of the search allows us to re-use information computed in
one stage for all the search queries in the next stage: in each stage, we have
already found some $\ell$-cliques, where $\ell<p$, and we want to add one more
node to the cliques, to obtain $(\ell+1)$-cliques (until in the final stage we
obtain $p$-cliques). To this end, the nodes collect some edges, which allow
them to detect some $(\ell+1)$-cliques, and then use a nested search to try to
complete the $(\ell+1)$-cliques into $p$-cliques.

Perhaps surprisingly, it turns out that in many cases it is not worthwhile to
“start the search from scratch”: instead of using quantum search to detect
$p$-cliques “from scratch”, it is more efficient to first _classically_ list
all $q$-cliques for some $q<p$, and then use quantum search to find an
extension of some $q$-clique into a $p$-clique. This echoes the theme of re-
using information throughout the stages of the search: we precompute some
information classically, which will be used by all stages of the search. For
example, we show that to solve triangle-detection, we can improve on the
algorithm from [22] by first classically listing _edges_ , so that every node
of the congested clique learns some set of edges that it will be responsible
for trying to complete into a triangle, and then using quantum search to find
a node that forms a triangle with some edge. This reduces the running time
from $\tilde{O}(n^{1/4})$ rounds in [22] to $\tilde{O}(n^{1/5})$ rounds in our
new algorithm.

More generally, we can solve the $K_{p}$-detection problem by first
classically listing all instances of $K_{p-1}$ in the graph, and then
performing distributed Grover search over the nodes, to check if some
$(p-1)$-clique can be extended into a $p$-clique. Since there are $n$ nodes to
check, the Grover search will require $\sqrt{n}$ quantum queries, and each
query can be checked in $O(1)$ rounds (in the congested clique, it is possible
to learn all neighbors of a given node in a single round). Thus, the overall
running time we obtain will be $\tilde{O}(L_{p-1}+\sqrt{n})$, where $L_{p-1}$
is the time required to list all $(p-1)$-cliques. For example, $4$-cliques can
be listed in $L_{4}=O(\sqrt{n})$ rounds [12], and this approach allows us to
solve the $K_{5}$-detection problem in roughly the same time complexity,
$\tilde{O}(\sqrt{n})$. However, the cost $L_{p-1}$ grows with $p$, so
sometimes it is better to start from a smaller clique, $K_{q}$ for $q<p-1$,
and extend by more than a single node. This leads to our general nested-
search-based approach, which starts by listing all copies of $K_{q}$ for some
$q<p$, and then uses nested quantum search to check if some $q$-clique can be
extended into a $p$-clique.

Review of prior works on classical algorithms for clique detection. In the
Congest model, the first sublinear algorithm for $p$-clique detection was
obtained for $p=3$ (i.e., triangle detection) by Izumi and Le Gall [23]. The
complexity of triangle detection was then improved to $\tilde{O}(\sqrt{n})$ by
Chang et al. [8], where $n$ denotes the number of nodes, and then further to
$\tilde{O}(n^{1/3})$ by Chang and Saranurak [9]. For $p$-cliques with $p\geq
4$, the first sublinear detection algorithm was constructed by Eden et al.
[13]. These results were improved to $\tilde{O}(n^{p/(p+2)})$ rounds for all
$p\geq 4$ by Censor-Hillel et al. [6], and very recently,
$\tilde{O}(n^{1-2/p})$ rounds for all $p\geq 4$ by Censor-Hillel et al. [4].
Czumaj and Konrad [10] have shown the lower bound $\Omega(\sqrt{n})$ for
$p$-clique detection for $p\geq 4$, which matches the upper bound from [4] for
$p=4$. Proving lower bounds for triangle detection, on the other hand, appears
extremely challenging: it is known that for any $\varepsilon>0$, showing a
lower bound of $\Omega(n^{\varepsilon})$ on triangle detection implies strong
circuit complexity lower bounds [5] (see nevertheless [1] for a weaker, but
still non-trivial, lower bound for triangle detection).222Note that the
algorithms from [8, 6, 9, 4] actually solve the listing version of the problem
(which asks to list all $p$-cliques of the graph) as well. For the listing
version, lower bounds matching the upper bounds from [9, 4] for all values of
$p\geq 3$ are known [23, 28, 16].

In the powerful Congested Clique model, the best known upper bounds on the
round complexity of $p$-clique detection is $O(n^{0.158})$ for $p=3$, which is
obtained by the algebraic approach based on matrix multiplication developed by
Censor-Hillel et al. [7], and $O(n^{1-2/p})$ for any constant $p\geq 4$ [12].

Further related works on quantum distributed computing. There exist a few
works investigating the power of quantum distributed computing in other models
or settings (see also [2] and [11] for surveys). In the LOCAL model,
separations between the computational powers of the classical and quantum
algorithms have been also obtained [18, 26]. Over anonymous networks, zero-
error quantum algorithms have been constructed for leader election [30].
Finally, quantum algorithms for byzantine agreements have also been
investigated [3].

Organization of the paper. The core conceptual message of the paper is
contained in the first 10 pages: we describe our main technique in Section 2
and then, in Section 3, explain how to use this technique to construct fast
quantum algorithms for clique detection in the Quantum Congested Clique model.
Further sections then show how to apply the technique to construct fast
algorithms in the Quantum Congest model (Section 4, which proves Theorem 1.2)
and construct even faster algorithms in the Quantum Congested Clique model
(Section 5, which proves Theorem 1.1). A proof of Theorem 1.3 is given in
Section 6.

##  2 Nested Distributed Quantum Searches

In this section we present our main technique: nested distributed quantum
searches. This is a generalization of a technique (called below _distributed
Grover search_) used in prior quantum distributed works [21, 25, 22].

We note that implementing distributed quantum searches in a nested way is
already allowed (but not used) in the framework introduced in [25]. Our main
contribution in the current section is developing this approach into a full
framework and describing its concrete implementation in the distributed
setting.

#### Standard Grover search.

We begin by informally describing the most standard framework for Grover
search — as a technique to solve a search problem with black-box access.

Consider the following: given black-box access to a function $f\colon
X\to\\{0,1\\}$, for an arbitrary $X$, find an $x\in X$ such that $f(x)=1$, if
such an element exists. Grover’s quantum algorithm [20] solves this problem
with high probability using ${O}(\sqrt{|X|})$ calls to the black box. Grover’s
algorithm consists of ${O}(\sqrt{|X|})$ steps, where each step executes one
quantum operation called the _Grover diffusion operation_ , which does not use
the black-box, and an operation called the _checking procedure_ , which uses
one call to the black-box.

#### Distributed Grover search.

Let us present the basic quantum distributed search framework (distributed
Grover search) introduced in [25]. In this distributed implementation, one
specific node, called _the leader_ , run each Grover diffusion locally, but
the checking procedure is implemented via a distributed algorithm.

Consider again a function $f\colon X\to\\{0,1\\}$, for an arbitrary $X$, and
the following search problem: one specified node (the leader) should find an
element $x\in X$ such that $f(x)=1$, or, if no such element exists the leader
should output “not found”. Assume there exists a distributed algorithm
$\mathcal{A}$, called the _checking procedure_ , in which the leader is given
$x\in X$ as input, and the leader returns $f(x)$ as output. The checking
procedure $\mathcal{A}$ is often described as a classical algorithm, but it
can also be a quantum distributed algorithm.333As explained in [25], a
classical procedure can easily be converted using standard techniques into a
quantum procedure able to deal with superpositions of inputs.

Let $r$ be the round complexity of $\mathcal{A}$. The framework introduced in
[25] shows that there is a quantum distributed algorithm that runs in
$\tilde{O}(\sqrt{|X|}\cdot r)$ rounds and enables the leader to solve the
above search problem with probability at least $1-1/\operatorname{poly}(n)$.
While the original statement in [25] was for the Quantum Congest model, as
explained in [21], the same holds for the Quantum Congested Clique model.

######  Lemma 2.1 ([25]).

There is a quantum algorithm that runs in $\tilde{O}(\sqrt{|X|}\cdot r)$
rounds and enables the leader to solve the above search problem with
probability at least $1-1/\operatorname{poly}(n)$. This statement holds in
both the Quantum Congest and the Quantum Congested Clique models.

Nested distributed quantum searches. All prior works using quantum distributed
search ([21, 25, 22]) used a classical checking procedure $\mathcal{A}$. The
framework of [25] nevertheless allows quantum checking procedures. In
particular, a distributed Grover search can be used as the checking procedure.
We now present our framework for nested distributed quantum searches,
consisting of $k$ nested levels, where at each level:

  1. 1.

The nodes run a distributed _setup_ step for the current level, collecting
information and preparing for the next search levels. The setup procedure in
our results is classical, but in general it can be quantum.

  2. 2.

We execute the next level of the search. Crucially, the information prepared
during the setup will be re-used to evaluate all the nested queries in the
next level (and subsequent levels).

Formally, let $f\colon X_{1}\times\cdots\times X_{k}\rightarrow\\{0,1\\}$ be a
function, for a constant $k\geq 2$ and sets $X_{1},\ldots,X_{k}$. The goal is
finding $(x_{1},\ldots,x_{k})\in X_{1}\times\cdots\times X_{k}$ where
$f(x_{1},\ldots,x_{k})=1$, if such exists. For $\ell\in\\{1,\ldots,k-1\\},u\in
V$, let $\textsf{setup}^{u}_{\ell}\colon X_{1}\times\ldots\times
X_{\ell}\to\\{0,1\\}^{\ast}$ be a function describing the setup data of $u$
for the $(\ell+1)$-th search. Let $\mathcal{S}_{1},\ldots,\mathcal{S}_{k-1}$
and $\mathcal{C}$ be distributed algorithms with the following specifications.

  * •

Algorithm $\mathcal{S}_{1}$. Input: the leader is given $x_{1}\in X_{1}$.
Output: each node $u\in V$ outputs $\textsf{setup}^{u}_{1}(x_{1})$.

  * •

Algorithm $\mathcal{S}_{\ell}$ for any $\ell\in\\{2,\ldots,k\\}$. Input: the
leader is given $(x_{1},\ldots,x_{\ell})\in X_{1}\times\cdots\times X_{\ell}$
and each node $u\in V$ is given
$\textsf{setup}^{u}_{\ell-1}(x_{1},\ldots,x_{\ell-1})$. Output: each node
$u\in V$ outputs $\textsf{setup}^{u}_{\ell}(x_{1},\ldots,x_{\ell})$.

  * •

Algorithm $\mathcal{C}$. Input: the leader is given $(x_{1},\ldots,x_{k})\in
X_{1}\times\cdots\times X_{k}$ and each node $u\in V$ is given
$\textsf{setup}^{u}_{k-1}(x_{1},\ldots,x_{k-1})$. Output: the leader outputs
$f(x_{1},\ldots,x_{k})$.

Let $s_{1},\ldots,s_{k-1}$ and $c$ denote the round complexities of
$\mathcal{S}_{1},\ldots,\mathcal{S}_{k-1}$ and $\mathcal{C}$, respectively.
Applying Lemma 2.1 leads to the following result.

######  Lemma 2.2.

There is a quantum algorithm that runs in

$\tilde{O}\left(\sqrt{|X_{1}|}\left(s_{1}+\sqrt{|X_{2}|}\left(s_{2}+\sqrt{|X_{3}|}\left(s_{3}+\ldots+\sqrt{|X_{k-1}|}\left(s_{k-1}+\sqrt{|X_{k}|}\left(s_{k}+c\right)\right)\right)\right)\right)\right)$

rounds and enables the leader to output $x_{1},\ldots,x_{k}$ such that
$f(x_{1},\ldots,x_{k})=1$, or output that there are no such
$x_{1},\ldots,x_{k}$, with probability at least $1-1/\operatorname{poly}(n)$.
This statement holds in both the Quantum Congest and the Quantum Congested
Clique models.

##  3 The Power of Nested Quantum Search: Clique-Detection from Listing in the
Quantum Congested Clique Model

In this section we describe our approach for taking an algorithm for
$K_{p}$-listing in the Congested Clique or Quantum Congested Clique model, and
extending it to $K_{p+t}$-detection (for some $t>0$) using quantum search. We
give two variations of the approach: the first uses the $K_{p}$-listing
algorithm _as a black box_ , so that any such algorithm can be used (for
example, algorithms that perform better on certain classes of input graphs,
etc.). This also forms the basis of our Quantum Congest algorithms in Section
4. The second approach yields faster results, but it “opens the black box”,
relying on the properties of the $K_{p}$-listing algorithm from [12]. Since it
is more complicated, the second approach is described in Section 5.

To exploit the large bandwidth of the Congested Clique, we use Lenzen’s
routing scheme for solving the _information distribution task_ : for some
$s\geq 1$, each $v\in V$ has at most $s\cdot n$ messages
$m^{v}_{1},\dots,m^{v}_{r}$, each of $O(\log n)$ bits, and each with a
destination $\mathit{dest}(m^{v}_{i})\in V$. Each $v\in V$ is the destination
of at most $s\cdot n$ messages ($|\\{m^{u}_{i}\mid u\in V\land i\in[s\cdot
n]\land\mathit{dest}(m^{u}_{i})=v\\}|\leq s\cdot n$), and we wish to deliver
each message $m^{v}_{i}$ to its destination $\mathit{dest}(m^{v}_{i})$.

######  Lemma 3.1 (Lenzen’s Routing Scheme[27]).

The information distribution task with parameter $s$ can be solved in $O(s)$
rounds in Congested Clique.

###  3.1 Warmup: Detecting Triangles in $\tilde{O}(n^{1/5})$ Rounds

We describe a simple triangle detection algorithm demonstrating the basic idea
of our approach, and improving upon the state-of-the-art algorithm from [22].

In the algorithm, we partition the search-space $V^{3}$ into $n$ _shards_ ,
one per node, and each $v\in V$ checks if there is a triplet
$(u_{1},u_{2},u_{3})$ in its shard that is a triangle in $G$. Each shard has
the form $A_{i}\times A_{j}\times Q_{k}$, where $A_{1},\ldots,A_{n^{2/5}}$
partitions $V$ into sets of $n^{3/5}$ nodes, and $Q_{1},\ldots,Q_{n^{1/5}}$
partitions $V$ into sets of size $n^{4/5}$.444To simplify the presentation,
here and everywhere in the paper, when partitioning $V$ into $n^{\delta}$
subsets, for a $\delta\in(0,1)$, we assume $n^{\delta}$ is an integer and
divides $n$. If this is not the case, one can replace $n^{\delta}$ by $\lceil
n^{\delta}\rceil$, without affecting the asymptotic complexity.Note that the
total number of shards is indeed $n^{2/5}\cdot n^{2/5}\cdot n^{1/5}=n$.

To check if its shard $A_{i}\times A_{j}\times Q_{k}$ contains a triangle,
node $v$ learns the edges $E(A_{i},A_{j})=E\cap\left(A_{i}\times
A_{j}\right)$, and then, using a distributed quantum search, checks if some
$w\in Q_{k}$ forms a triangle with some $\left\\{u_{1},u_{2}\right\\}\in
E(A_{i},A_{j})$. The search is not performed directly over $Q_{k}$: instead,
we partition $Q_{k}$ into _batches_ , $Q_{k}^{1},\ldots,Q_{k}^{b}$, and search
for a batch $Q_{k}^{\ell}$ with a node forming a triangle. Processing the
nodes in batches allows us to fully utilizes the bandwidth in the Congested
Clique. However, we must balance the _size_ of batches, which determines the
time to check if a batch has a node completing a triangle, against the
_number_ of batches, which determines the number of quantum queries we will
need to perform.

#### Detailed description of the algorithm.

Consider a node $v$, and let $A_{i}\times A_{j}\times Q_{k}$ be the shard
assigned to node $v$. The algorithm has two steps:

  1. 1.

Node $v$ learns $E(A_{i},A_{j})$, using Lenzen’s routing scheme.

  2. 2.

Node $v$ partitions $Q_{k}$ into $n^{2/5}$ batches,
$Q_{k}=\\{Q_{k}^{1},\ldots,Q_{k}^{n^{2/5}}\\}$, each containing $n^{2/5}$
nodes (since $|Q_{k}|=n^{4/5}$). We use a quantum search over
$\ell\in[n^{2/5}]$ to check whether there exists a $Q_{k}^{\ell}$ containing a
node $w\in Q_{k}^{\ell}$ that forms a triangle together with two nodes
$u_{1}\in A_{i},u_{2}\in A_{j}$.

Formally, we instantiate Lemma 2.1 with the search-space $X=[n^{2/5}]$ (i.e.,
the batch indices). The checking procedure $\mathcal{A}$ checks an index
$\ell\in[n^{2/5}]$ by routing $E(A_{i}\cup A_{j},Q_{k}^{\ell})$ to $v$ (in
parallel at all nodes). Then, $v$ locally checks whether there is a
$(u_{1},u_{2},w)\in A_{i}\times A_{j}\times Q_{k}^{\ell}$ such that
$\left\\{u_{1},u_{2}\right\\}\in E(A_{i},A_{j}),\left\\{u_{1},w\right\\}\in
E(A_{i},Q_{k}^{\ell})$, and $\left\\{u_{2},w\right\\}\in
E(A_{j},Q_{k}^{\ell})$; it sends ’1’ to the leader if it found such a triplet,
and ’0’ otherwise.

#### Complexity.

Step 1 requires $O(|A_{i}|\cdot|A_{j}|/n)=O(n^{2\cdot 3/5-1})=O(n^{1/5})$
rounds, using Lenzen’s routing scheme (Lemma 3.1). In Step 2, checking a
particular batch $Q_{k}^{\ell}$ requires node $v$ to learn $E(A_{i}\cup
A_{j},Q_{k}^{\ell})$. As $|E(A_{i}\cup
A_{j},Q_{k}^{\ell})|=O(n^{3/5+2/5})=O(n)$, this can be done in $O(1)$ rounds
using Lemma 3.1. By Lemma 2.1, since the search space is $[n^{2/5}]$, Step 2
takes $\tilde{O}(n^{1/5})$ rounds. In total, the algorithm takes
$\tilde{O}(n^{1/5})$ rounds.

###  3.2 Extending $K_{p}$ _Listing_ to $K_{p+t}$ _Detection_

Our triangle detection algorithm has the following structure: we view a
triangle as an edge $\left\\{u_{1},u_{2}\right\\}$, plus a node $w$ connected
to $u_{1},u_{2}$. We _classically_ route information between nodes, so they
can list the edges $\left\\{u_{1},u_{2}\right\\}$ in the sets they are
responsible for ($A_{i}\times A_{j}$). Then, we use _quantum search_ to check
if there is a node $w$ forming a triangle with a listed edge.

We extend this idea to cliques of arbitrary sizes: given $q>2$, take $p,t$
where $p+t=q$. We view a $q$-clique as a $p$-clique
$\left\\{v_{1},\ldots,v_{p}\right\\}$, plus a $t$-clique
$\left\\{u_{1},\ldots,u_{t}\right\\}$ where $u_{1},\ldots,u_{t}$ are all
connected to $v_{1},\ldots,v_{p}$. We classically list all $p$-cliques, and
then use quantum search to check for a $t$-clique forming a $q=(p+t)$-clique
with a listed $p$-clique.

We present two variants of this approach. The first takes a $K_{p}$-listing
algorithm as a black box, making no assumptions about which $p$-cliques are
found by which nodes. The second improves on the first by “opening the black
box” and using properties of the $K_{p}$-listing algorithm of [12]: knowing
which $p$-cliques are listed by each node reduces the amount of information we
route during the quantum search, as some edges are not relevant to some nodes.
We present the first variant here, and the second is given in Section 5. Note
that our triangle detection algorithm is an instance of the second variant,
since we exploit out knowledge of $A_{i},A_{j}$ to determine which edges
($E(A_{i}\cup A_{j},Q_{k}^{\ell})$) are learned by a given node as it
evaluates batch $Q_{k}^{\ell}$.

How should we explore the search-space $V^{(t)}$ of possible $t$-cliques that
may extend a given $p$-clique to a $(p+t)$-clique? One possibility is to
partition it into batches, and search over them, as we did for triangles.
However, the large search-space makes this inefficient: every node must learn
the edges between every pair of nodes in the current batch, and since we can
use at most $n^{2}$ batches555Otherwise we will need more than
$\sqrt{n^{2}}=n$ quantum queries. to cover $V^{(t)}$, very soon we reach a
situation where every node needs to learn _all_ the edges. Instead, we use a
_nested search_ , building the $t$-clique node-by-node. The search is
structured so that edges learned at a given level are re-used to evaluate
_many_ nested queries on following levels. See Fig. 1 for an example
partitioning of the search-space.

Figure 1:  Extending from $K_{p}$-listing to $K_{p+2}$-detection. We search
$V\times V$ to check for a pair of nodes that can be added to an existing
$p$-clique to form a $(p+2)$-clique (in the figure, $|V|=9$). A non-nested
search requires $\sqrt{n\cdot n}=n$ queries. In contrast, in a nested search,
we split the first dimension into $\sqrt{n}$ batches, and search over them
(requiring $n^{1/4}$ outer queries); to implement each outer query, all nodes
send the edges corresponding to the current batch (requiring $\sqrt{n}$
rounds), and then explore the second dimension ($|V|=n$) using $\sqrt{n}$
inner quantum queries. The time of the entire search is
$\tilde{O}\left(n^{1/4}\left(\sqrt{n}+\sqrt{n}\right)\right)=\tilde{O}\left(n^{3/4}\right)$.

#### The initial state.

Let $V^{(p)}$ denote all subsets of $V$ with cardinality $p$. When we begin,
we assume copies of $K_{p}$ have already been found: each node $u\in V$ has a
subset $S_{u}^{p}\subseteq V^{(p)}$ of $p$-cliques it found. Let
$S^{p}=\bigcup_{u\in V}S_{u}^{p}$ be all copies of $K_{p}$ found by the nodes.
We assume $S^{p}$ is the set of all $p$-cliques in $G$.

We say that an algorithm $A$ _extends_ from $K_{p}$ to $K_{p+t}$ if, given
sets $\left\\{S_{u}^{p}\right\\}_{u\in V}$, w.h.p., algorithm $A$ outputs ’1’
at all nodes iff $G$ contains a $(p+t)$-clique
$\left\\{v_{1},\ldots,v_{p+t}\right\\}\in V^{(p+t)}$ such that
$(v_{1},\ldots,v_{p})\in S^{p}$.

######  Theorem 3.2.

For every $p\geq 2$, $t\geq 1$, there is an algorithm that extends from
$K_{p}$ to $K_{p+t}$ in $\tilde{O}(n^{1-1/2^{t}})$ rounds in Quantum Congested
Clique.

######  Proof 3.3.

Fix in advance $t$ partitions of $V$, where the $\ell$-th partition divides
$V$ into $n^{1/2^{t-\ell}}$ sets, $V_{1}^{\ell},\ldots,V_{n^{1/2^{t-\ell}}}$,
each of size $n^{1-1/2^{t-\ell}}$. Note that the partitions become
increasingly finer, until at level $\ell=t$ we have $n$ sets comprising a
single node each. Our goal is to execute a nested quantum search to check if
there is a $t$-tuple of indices $(x_{1},\ldots,x_{t})$, such that there exist
$v_{1}\in V_{x_{1}}^{1},\ldots,v_{t}\in V_{x_{t}}^{t}$ forming a
$(p+t)$-clique together with some previously-listed $p$-clique
$\left\\{w_{1},\ldots,w_{p}\right\\}\in S^{p}$.

We instantiate Lemma 2.2, executing a nested search with $t$ levels over the
domain $X_{1}\times\ldots\times X_{t}$, where $X_{\ell}=[n^{1/2^{t-\ell}}]$
for each $\ell=1,\ldots,t$. We search for an element satisfying the function

$f(x_{1},\ldots,x_{t})=1\Leftrightarrow\\\ \exists v_{1}\in
V_{x_{1}}^{1}\ldots\exists v_{t}\in
V_{x_{t}}^{t}\exists\left\\{w_{1},\ldots,w_{p}\right\\}\in
S^{p}:\text{$\left\\{w_{1},\ldots,w_{p},v_{1},\ldots,v_{t}\right\\}$ is a
$(p+t)$-cliqe in $G$}.$

At level $\ell\leq t$ of the search, the setup we prepare takes the form of
sets $\left\\{S_{u}^{p+\ell}\right\\}_{u\in V}$ at the nodes, where
$S_{u}^{p+\ell}\subseteq V^{(p+\ell)}$ is a set of $(p+\ell)$-cliques in $G$
that node $u$ has learned about. When initiating the search (“$\ell=0$”), we
are given $\left\\{S_{u}^{p}\right\\}_{u\in V}$. The algorithm
$\mathcal{S}_{\ell}$ that prepares the setup for level $\ell\geq 1$ is as
follows:

  * •

Every node $u\in V$ broadcasts the subset of $V_{x_{\ell}}^{\ell}$ that it is
neighbors with:

$N_{u,x_{\ell}}=\left\\{v\in V_{x_{\ell}}^{\ell}:\left\\{u,v\right\\}\in
E\right\\}.$

  * •

Locally, each node $u\in V$ prepares $S_{u}^{p+\ell}$, by listing all the
$(p+\ell)$-cliques that it can form by taking a $(p+\ell-1)$-clique from
$S_{u}^{p+\ell-1}$ and appending to it a node from $V_{x_{\ell}}^{\ell}$:

$S_{u}^{p+\ell}=\left\\{\left\\{v_{1},\ldots,v_{p+\ell}\right\\}\in
V^{(p+\ell)}:\left\\{v_{1},\ldots,v_{p+\ell-1}\right\\}\in
S_{u}^{p+\ell-1},\right.\\\ \left.v_{p+\ell}\in V_{x_{\ell}}^{\ell},\text{ and
for each $i=1,\ldots,p+\ell-1$ we have }v_{p+\ell}\in
N_{v_{i},x_{\ell}}\right\\}.$

The final algorithm $\mathcal{C}$ that evaluates $f(x_{1},\ldots,x_{t})$
simply has each node $u$ inform the leader whether $S_{u}^{p+t}$ is empty or
not. If there is some node $u$ with $S_{u}^{p+t}\neq\emptyset$, the leader
outputs ’1’, and otherwise ’0’.

#### Complexity.

The size of the $\ell$-th level partition is chosen to as to balance the setup
cost against the time required for the remainder of the nested search: at
level $\ell$, the setup cost is
$|V_{x_{\ell}}^{\ell}|=s_{\ell}=n^{1-1/2^{t-\ell}}$. Using Lemma 2.2, a
backwards induction on $\ell$ shows the cost for levels $\ell+1,\ldots,t$ of
the search is $\tilde{O}\left(n^{1-1/2^{t-\ell}}\right)$, matching the setup
cost. The cost of the entire search (i.e., levels $\ell=1,\ldots,t$) is
$\tilde{O}\left(n^{1-1/2^{t}}\right)$.

By combining the classical clique-listing algorithm of [12] with Theorem 3.2,
we obtain an algorithm for detection of $K_{p}$ which improves on the state-
of-the-art classical algorithm for $p\geq 5$.

######  Theorem 3.4.

Given a graph $G=(V,E)$ and a clique size $p\geq 5$, it is possible to detect
whether there exists an instance of $K_{p}$ in $G$ within
$\tilde{O}(\min_{t\in\mathbb{N}}\max\\{n^{1-\frac{2}{p-t}},n^{1-\frac{1}{2^{t}}}\\})$
rounds of the Quantum Congested Clique model.

For instance, for $p=5$, by taking $t=1$, we get $K_{5}$-detection in
$\tilde{O}(n^{1/2})$ rounds of the Quantum Congested Clique model, improving
on the classical runtime of $\tilde{O}(n^{3/5})$. We note that
$\tilde{O}(n^{1/2})$ is the time required to classically list $K_{4}$, so the
quantum-search-based extension from 4-cliques to 5-cliques is “for free”.

##  4 Detection from Listing in the Quantum Congest Model

This section is devoted to the proof of Theorem 1.2.

  * Theorem 1.2.

There exists a quantum algorithm that solves $p$-clique detection with success
probability at least $1-1/\operatorname{poly}(n)$ in the Quantum Congest model
with complexity $\tilde{O}(n^{1/5})$ for $p=3$, and $\tilde{O}(n^{1-2/(p-1)})$
for $p\geq 7$.

We begin with the proof for triangle detection in Quantum Congest, and then
proceed with $K_{p}$ detection for $p\geq 7$.

At a very high level, our algorithms in this section use the framework of
decomposing the graph into clusters of high conductance and working within
each cluster in order to find the required subgraph, and then recursing over
the edges remaining outside of clusters. To work within a cluster, throughout
this section we will use the following expander decomposition and routing
theorems.

#### Preliminaries.

We begin by defining the notions of mixing time and conductance, which are
used in the context of the expander decomposition. We note that we do not use
these definitions directly, but rather, we use previously-proven lemmas that
use these properties to obtain efficient routing or simulation procedures on
such graphs.

The _conductance_ of a graph $G$ is $\Phi(G)=\min_{S\subseteq
V}\frac{|E(S,V\setminus S)|}{\min(|E(S,V)|,|E(V,V\setminus S)|)|}$, is the
worst-case ration between the number of edges crossing a cut in the graph, and
the number of edges contained on either side of the cut.

The conductance is related to the _mixing time_ of the graph, which,
informally, is the number of steps required for a random walk starting from
any vertex $u$ to become close to its stationary distribution, where the
probability of being at any given vertex $v$ is roughly
$\mathit{degree}(v)/2m$. The mixing time of a graph $G$ is denoted
$\tau_{\textrm{mix}}(G)$, and it is related to the conductance as follows:
$\Theta\left(\frac{1}{\Phi(G)}\right)\leq\tau_{\textrm{mix}}(G)\leq\Theta\left(\frac{\log
n}{\Phi^{2}(G)}\right)$ (see Corollary 2.3 in [24]).

######  Lemma 4.1 ([9, 4]).

Let $\delta>0$ such that $m=n^{1+\delta}$. For any $\epsilon\in(0,1)$, and
constant $\gamma\in(0,1)$, there is a constant $a_{\gamma}>0$ dependent only
on $\gamma$, such that a decomposition can be constructed in
$\tilde{O}(n^{\gamma})$ rounds, with high probability, in which the edges of
the graph are partitioned into two sets, $E_{m},E_{r}$, that satisfy the
following conditions:

  1. 1.

Each connected component (cluster) $C$ of $E_{m}$ has conductance
$\Phi(C)\geq(\epsilon/\log{n})^{a_{\gamma}}$, and has average degree at least
$\epsilon n^{\delta}$.

  2. 2.

For any cluster $C$ and node $v\in V_{C}$,
$\deg_{V_{C}}(v)\geq(\epsilon/\log{n})^{a_{\gamma}}\deg_{V\setminus
V_{C}}(v)$.

  3. 3.

$E_{r}\leq\epsilon m$.

######  Theorem 4.2 (Expander routing [9, 19]).

Suppose $\tau_{\operatorname{mix}}(G)=\operatorname{\mathrm{polylog}}(n)$ and
let $0\leq\gamma\leq 1$ be a constant. There is an $O(n^{\gamma})$-round
algorithm that pre-processes the graph such that for any subsequent routing
task where each node $v$ is a source and a destination of at most
$L\cdot\deg(v)$ messages of $O(\log n)$ bits, all messages can be delivered in
$L\cdot\log^{\alpha}(n)$ rounds of the Congest model, with high probability,
where $\alpha$ is a constant that depends only on $\gamma$.

###  4.1 $\tilde{O}(n^{1/5})$-Round Triangle Detection in the Quantum Congest
Model

In this section we show an $\tilde{O}(n^{1/5})$-round triangle detection
algorithm in Quantum Congest. That is, we prove the following theorem, which
is part of Theorem 1.2.

######  Theorem 4.3.

There exists an algorithm that solves triangle detection with success
probability at least $1-1/\operatorname{poly}(n)$ in the Quantum Congest model
with complexity $\tilde{O}(n^{1/5})$.

As observed in [8, 9] (see also Theorem 4 in [22]), it is sufficient to solve
this problem in high conductance graphs (with some additional edges incident
to this graph) in order to obtain an algorithm for general graphs. Our Quantum
Congest algorithm shares many similarities with the $\tilde{O}(n^{1/5})$
triangle detection quantum algorithm in the Quantum Congested Clique shown in
Section 3, but requires a more “sparsity aware” approach for it to work in
this more restricted model.

Specifically, in the FindTriangleInSubnetwork problem, as defined in [22], the
input network $G^{\prime}=(V^{\prime},E_{\mathrm{in}}\cup E_{\mathrm{out}})$
is a connected network such that the mixing time of the graph
$G_{\mathrm{in}}=(V(E_{\mathrm{in}}),E_{\mathrm{in}})$ is at most
$O(\operatorname{\mathrm{polylog}}(n))$ (e.g., its conductance is at least
$\Omega(1/\operatorname{\mathrm{polylog}}(n))$), and each edge in
$E_{\mathrm{out}}$ is incident to a node in $V(E_{\mathrm{in}})$ so that
$deg_{G_{\mathrm{in}}}(v)\geq deg_{G^{\prime}-G_{\mathrm{in}}}(v)$ for every
node $v\in G_{\mathrm{in}}$, and the goal of the network is to determine
whether $G^{\prime}$ is triangle-free.

######  Theorem 4.4 ([8, 9], Theorem 4 in [22]).

Assume that there exists an $r$-round distributed Quantum Congest algorithm
$A$ that solves the FindTriangleInSubnetwork problem with probability at least
$1-1/n^{3}$ and uses only the edges in $E_{\mathrm{in}}\cup E_{\mathrm{out}}$
for communication. Then there exists an $O(r\log{n}+n^{0.1})$-round Quantum
Congest algorithm that solves the triangle finding problem over the whole
graph $G=(V,E)$ with probability at least $1-1/\operatorname{poly}(n)$.

In the remainder of this subsection we describe an algorithm in Quantum
Congest for the problem FindTriangleInSubnetwork, which assumes the input
network has the restrictions mentioned above. We then plug this algorithm into
Theorem 4.4 and obtain Theorem 4.3 as claimed. Specifically, we prove the
following.

######  Theorem 4.5.

There exists an algorithm that solves the FindTriangleInSubnetwork problem
with success probability at least $1-1/n^{3}$ in the Quantum Congest model
with complexity $\tilde{O}(n^{1/5})$.

Denote by $m_{\mathrm{in}}=|E_{\mathrm{in}}|$ and by
$n_{\mathrm{in}}=|V(E_{\mathrm{in}})|$ the number of edges and vertices inside
the high conductance graph respectively, and by $\bar{m}=|E_{\mathrm{in}}\cup
E_{\mathrm{out}}|,\bar{n}=|V^{\prime}|$ the number of edges and vertices in
$G^{\prime}$ respectively. Denote $\delta>0$ such that
$\bar{m}=\bar{n}^{1+\delta}$, that is, $O(\bar{n}^{\delta})$ is the average
degree in $G^{\prime}$.

Computation units. Since $deg_{G_{\mathrm{in}}}(v)\geq
deg_{G^{\prime}-G_{\mathrm{in}}}(v)$ for every node $v\in G_{\mathrm{in}}$,
there is a constant $c>1$ such that $\bar{m}\leq cm_{\mathrm{in}}$. We define
a _computation unit_ to be a paired set $(v,\tilde{E})$ where $v\in
V(E_{\mathrm{in}}),\tilde{E}\subseteq E_{\mathrm{in}}$, and such that
$|\tilde{E}|=\lfloor\bar{n}^{\delta}/(2c)\rfloor$ and all edges in $\tilde{E}$
are incident to $v$. We say that the node $v$ is the _core_ of the computation
unit. Notice that a node can be a core of multiple computation units. A set of
computation units is called _pairwise-disjoint_ if for any two computation
units $(v_{1},E_{1}),(v_{2},E_{2})$ in the set, either the cores are
different, i.e., $v_{1}\neq v_{2}$, or the edges $E_{1}$ and $E_{2}$ are
disjoint.

The reason we define computation units is as follows. In a nutshell, our
algorithm will split the edges of the input into sets, such that each set
defines a triangle finding _task_ of checking whether any three edges in the
set form a triangle and such that all possible triplets of edges are checked.
To do so, we need to assign all such tasks to the nodes. However, a node with
a smaller degree can receive less information to check compared with a node
with a higher degree. This is where the computation units come into play: Each
core of a computation unit will use the edges of its unit to send and receive
information, so that it can process edges associated with a single such task.
Now, the bandwidth of a node with a high degree will be exploited by having
this node be a core of more computation units, and hence it will be
responsible for solving more such tasks, compared with a node of a smaller
degree.

First, we show that we have sufficient computation units. Consider a node $v$
with internal degree at least $\bar{n}^{\delta}/2c$ and split its edges into
disjoint sets of size $\lfloor\bar{n}^{\delta}/2c\rfloor$, and a remainder set
of edges of size at most $\lfloor\bar{n}^{\delta}/2c\rfloor$. Mark each such
set of size $\lfloor\bar{n}^{\delta}/2c\rfloor$ as a computation unit with the
node $v$ as its core.

######  Lemma 4.6.

In the process above, the set of marked computation units is pairwise-
independent and is of size at least $\bar{n}/2$.

######  Proof 4.7.

We note that the set is indeed pairwise independent, as for each node $v$ the
edges of the computation units with node $v$ are edge-disjoint.

Recall that $\bar{m}\leq cm_{\mathrm{in}}$ for the constant $c>1$. Assume by
contradiction that there are less than $\bar{n}/2$ computation units marked.
Consider a graph $\tilde{G}_{\mathrm{in}}$ that is defined as a subgraph of
$G_{\mathrm{in}}$ after removing all edges participating in any marked
computation unit. By the assumption on the number of computation units and by
the bound on the number of edges in a computation unit, there are at most
$(\bar{n}/2)\cdot\lfloor\bar{n}^{\delta}/2c\rfloor=\bar{n}^{1+\delta}/4c$
edges removed. This implies that the number of edges in
$\tilde{G}_{\mathrm{in}}$ is at least
$m_{\mathrm{in}}-\bar{n}^{1+\delta}/4c\geq
c\bar{m}-\bar{n}^{1+\delta}/4c=\bar{n}^{1+\delta}(c-1/4c)\geq\bar{n}^{1+\delta}/2c$,
where the last inequality holds for $c\geq\sqrt{3}/4$, which we have since
$c>1$.

This implies that the average degree in $\tilde{G}_{\mathrm{in}}$ is at least
$\bar{n}^{1+\delta}/2cn_{\mathrm{in}}\geq\bar{n}^{1+\delta}/2c\bar{n}\geq\bar{n}^{\delta}/2c$,
which implies that there is at least one node $v$ with degree
$\bar{n}^{\delta}/2c$ in $\tilde{G}_{\mathrm{in}}$, which contradicts the
process above, as $v$ could have marked an additional computation unit.

The above process of constructing computation units can easily be computed by
each node separately. Thus, in order to prove Theorem 4.5, we need a way to
make the computation units globally known, in the sense that each has a unique
identifier that is known to all nodes. To this end, we will use the following
technical claim.

######  Claim 1 ([8] variant of Lemma 4.1).

Let $G=(V,E)$ be a graph with $\operatorname{\mathrm{polylog}}(n)$ diameter.
Assume every node has some integer value $f(v)$ which fits in a single $O(\log
n)$ bit message. It is possible to give every node $v$ in the network a new
unique identifier $i_{v}\in[n]$, such that there is a globally known function
$\tilde{f}:[n]\rightarrow\mathbb{N}$ that any node $u$ can locally compute any
of its values, and such that $\tilde{f}(i_{v})$ is a $2$-approximation to
$f(v)$ for all $v\in V$. This algorithm requires
$\operatorname{\mathrm{polylog}}(n)$ rounds of the Congest model.

We will also need the ability to have a leader node that coordinates quantum
searches. To implement a leader, the diameter of the network naturally gets
into the round complexity. Luckily, in [13], it was shown that for any
$H$-freeness problem (i.e., $H$-detection), we may assume without loss of
generality that the network has small diameter, stated as follows.

######  Lemma 4.8 ([13]).

Consider an $H$-freeness problem, where $|H|=k$. Let $\mathcal{A}$ be a
protocol that solves $\mathcal{P}$ in time $T(n,D)$ with error probability
$\rho=o(\frac{1}{n\log{n}})$. There is an algorithm $\mathcal{A}^{\prime}$
that solves $\mathcal{P}$ with round complexity
$\tilde{O}(T(n,O(k\log{n}))+k\log^{2}{n})$ and error probability at most
$c\rho n\log{n}+\frac{1}{\mathrm{poly}(n)}$, for some constant $c$.

Using the above _diameter reduction_ technique, we assume that the diameter of
the network is $O(\operatorname{\mathrm{polylog}}(n))$. Moreover, we assume
that the network computes a leader node $v^{*}$ and a BFS tree rooted at
$v^{*}$, which can be done by the network in
$O(\operatorname{\mathrm{polylog}}(n))$ rounds.

The last ingredient that we need is the notion of $k$-wise independent hash
functions. For two integers $a,b$ we say that a function $f:[a]\rightarrow[b]$
is a _$k$ -wise independent hash function_ if for any $k$ distinct elements
$x_{1},\dots,x_{k}\in[a]$ and any $k$ elements $y_{1},\dots,y_{k}\in[b]$, it
holds that $\Pr(f(x_{1})=y_{1}\land\dots\land f(x_{k})=y_{k})=1/b^{k}$.

We will use the following tail bound for bounding the size of a given bin in a
$k$-wise independent hash function.

######  Lemma 4.9 ([29],Theorem 5(II)(b)).

If $\mathrm{X}$ is the sum of $k$-wise independent random variables, each of
which is confined to the interval $[0,1]$ and has $\mu=E[\mathrm{X}]$, then
for $\alpha\geq 1$ and assuming $k\leq\lceil\alpha\mu e^{-1/3}\rceil$,

$\Pr(|X-\mu|\geq\alpha\mu)\leq e^{-\lfloor k/2\rfloor}.$

We are now ready to prove Theorem 4.5.

######  Proof 4.10 (Proof of Theorem 4.5).

First, each node splits its edges into computation units as describe above.
This is done locally without communication. By Lemma 4.6, there are at least
$\bar{n}/2$ computation units.

Recall that by Lemma 4.8, we can assume that the diameter of $G^{\prime}$ is
$O(\operatorname{\mathrm{polylog}}{n})$. The nodes run the procedure of Claim
1 to give to each node $v$ a new unique ID $i_{v}$ in $[\bar{n}]$, such that
there is a globally known function $\tilde{f}:[n]\rightarrow\mathbb{R}$ that
any node $u$ can locally compute any of its values, and such that for any
$v\in V$, $\tilde{f}(i_{v})$ is a $2$-approximation to the number of
computation units of $v$. Using this knowledge, the network gives a unique ID
in $\lfloor\bar{n}/4\rfloor$ to a set of $\lfloor\bar{n}/4\rfloor$ marked
computation units, such that all nodes know for each such computation unit its
node ID (this can be done locally since the function $\tilde{f}(i_{v})$ is
globally known). Note that we have $\lfloor\bar{n}/2\rfloor$ marked
computation units, but we can only promise global knowledge of a
2-approximation on their number. This stage completes in
$O(\operatorname{\mathrm{polylog}}{n})$ rounds.

Following this, using standard computation of a maximum value, the nodes of
the network find the node $v^{*}$ in $G_{\mathrm{in}}$ with the highest ID and
mark it as the leader node. The nodes then construct a BFS tree of
$G^{\prime}$ from $v^{*}$ and, using the BFS tree, $v^{*}$ propagates
$O(\operatorname{\mathrm{polylog}}{n})$ unused random bits to the rest of the
network. Since the diameter of the network is at most
$O(\operatorname{\mathrm{polylog}}{n})$, the above needs at most
$O(\operatorname{\mathrm{polylog}}{n})$ rounds.

Using the the propagated random bits, the nodes choose at random two hash
functions, $h_{A}:[\bar{n}]\rightarrow[\bar{n}^{2/5}]$ and
$h_{S}:[\bar{n}]\rightarrow[\bar{n}^{1/5}]$, uniformly and independently from
a $\Theta(\log{n})$-wise independent hash function family. Let
$A=\\{A_{1},\dots,A_{\bar{n}^{2/5}}\\}$ be the sets such that $A_{i}=\\{v\mid
h_{A}(v)=i\\}$, and let $S=\\{S_{1},\dots,S_{\bar{n}^{1/5}}\\}$ be the sets
such that $S_{i}=\\{v\mid h_{S}(v)=i\\}$.

Now, let $P$ be a partition of the computation units of $G_{\mathrm{in}}$ into
$\bar{n}^{4/5}$ sets of size at least $\bar{n}^{1/5}/4$ each. We arbitrarily
index the sets in $P$ by $P_{i,j}$ for $1\leq i,j\leq\bar{n}^{2/5}$, and
associate each set $P_{i,j}$ in $P$ with a pair of sets $(A_{i},A_{j})$. In
addition, for each $1\leq i,j\leq\bar{n}^{2/5}$ and each computation unit
$C_{i,j,\ell}$ in $P_{i,j}$ (for $\ell$ in a range from 1 to a value that is
at least $\bar{n}^{1/5}/4$), we associate $C_{i,j,\ell}$ with at most $4$ sets
in $S$ (this is possible as there are at least $\bar{n}^{1/5}/4$ computation
units in each $P_{i,j}$ and $\bar{n}^{1/5}$ sets in $S$). We denote the sets
in $S$ that are associated with $C_{i,j,\ell}$ by
$S_{i,j,\ell,1},\dots,S_{i,j,\ell,4}$ (the indices $i,j$ can be omitted by
being using the same 4 sets depending only on $\ell$ and being the same for
every $i,j$).

The algorithm proceeds in two phases: For the first phase, consider a set of
computation units $P_{i,j}$ in $P$, and define $E_{1}(i,j)=E(A_{i},A_{j})$. In
the first phase, for each $1\leq i,j\leq\bar{n}^{2/5}$, each core $v$ of a
computation unit in part $P_{i,j}$ of $P$ learns all edges in $E_{1}(i,j)$. As
$h_{A}$ is a pairwise-independent hash function, for an edge $\\{u,w\\}$, we
have $\Pr(h_{A}(u)=i\land h_{A}(w)=j)=(1/\bar{n}^{2/5})^{2}=1/\bar{n}^{4/5}$.
Therefore, the number of edges that a core $v$ is required to learn in
expectation is
$\mathbf{E}(|E_{1}(i,j)|)=\bar{m}/\bar{n}^{4/5}=\bar{n}^{\delta+1/5}$.

By the tail bound of Lemma 4.9, since we use an $\Omega(\log{n})$-wise
independent hash function family (this is a logarithm of the total number of
nodes $n$), the number of these edges is at most
$\tilde{O}(\bar{n}^{\delta+1/5})$ w.h.p. (in $n$). Therefore, the core of a
computation unit may learn these edges in $\tilde{O}(\bar{n}^{1/5})$ rounds
using the routing scheme of Theorem 4.2 with a sufficiently small $\gamma$
(since we have a degree of $O(\bar{n}^{\delta})$ in $G_{\mathrm{in}}$ for the
core using edges of this computation unit alone).

We now have that for every $i,j$, there are at least $\bar{n}^{1/5}/4$
computation units (those in $P_{i,j}$), whose cores know all edges in
$E(A_{i},A_{j})$. Each such core is associated with 4 sets
$S_{i,j,k,1},\dots,S_{i,j,k,4}$, and what we would like to do in the second
phase is for each core to check all edges from one of its $S$ sets to nodes in
$A_{i},A_{j}$ and detect a triangle. To leverage the power of the distributed
Grover search, we split the task of each core into subtasks on which we can
apply Lemma 2.1.

Formally, for the second phase, we define for each $S_{i}$ an arbitrarily
split of $S_{i}$ into $\bar{n}^{2/5}$ batches, each of size
$\tilde{O}(\bar{n}^{2/5})$ nodes, and denote these batches by
$S_{i}^{(1)},\dots,S_{i}^{(\bar{n}^{2/5})}$. We define the following protocols
$\mathcal{A}_{1},\dots,\mathcal{A}_{\bar{n}^{2/5}}$. The protocol
$\mathcal{A}_{r}$ is defined as follows: For each $k$ such that $1\leq
k\leq\bar{n}^{1/5}$ and for each $1\leq r\leq\bar{n}^{2/5}$, let
$E_{2}(i,j,k,r)=\\{(u,w)\mid u\in S_{k}^{(r)}\land w\in A_{i}\cup A_{j}\\}$.
In the protocol, each core $v$ of a computation unit $C_{i,j,\ell}$ in
$P_{i,j}$ learns all edges of $E_{2}(i,j,k,r)$ for at most 4 values of $k$
which are assigned to it. Since a set $S_{k}^{(r)}$ has
$\tilde{O}(\bar{n}^{2/5})$ nodes, the number of edges to be collected between
nodes of $S_{k}^{(r)}$ and $A_{i}\cup A_{j}$ is in expectation
$\mathbf{E}(|E_{2}(i,j,k,r)|)=\bar{n}^{1+\delta}\cdot(\bar{n}^{2/5}/\bar{n})\cdot(\bar{n}^{3/5}/\bar{n})=\tilde{O}(\bar{n}^{\delta})$.
By the tail bound of Lemma 4.9, the number of these edges is at most
$\tilde{O}(\bar{n}^{\delta})$ w.h.p. (in $n$), therefore the computation unit
may learn these edges in $\tilde{O}(1)$ rounds using the routing scheme of
Theorem 4.2. A computation unit in $P_{i,j}$ rejects if there is a triangle
contained in $E_{1}(i,j)\cup E_{2}(i,j,k,r)$ for any of the 4 values of $k$
which are assigned to it. Using the BFS tree, the network determines whether
there was a computation unit that rejected, rejects if so, and otherwise
accepts (notice that this propagation would not be needed in a non-quantum
algorithm, as it is sufficient that one node rejects, but here we need the
leader $v^{*}$ to know this information).

The way these protocols are exectued is as follows. In the second phase, the
leader $v^{*}$ performs the quantum procedure described in Lemma 2.1 on
$\mathcal{A}_{1},\dots,\mathcal{A}_{\bar{n}^{2/5}}$. Therefore, by Lemma 2.1,
the quantum protocol rejects if and only if the network rejects in at least
one of these procedures, and terminates after
$\tilde{O}(\sqrt{\bar{n}^{2/5}})=\tilde{O}(\bar{n}^{1/5})=\tilde{O}(n^{1/5})$
rounds.

#### Correctness.

If the graph is triangle-free then the network accepts, as a core $v$ of a
computation unit only rejects if it detects a triangle in the edges
$E_{1}(i,j)\cup E_{2}^{r}(k)$ for some appropriate parameters $i,j,r,k$.
Otherwise, let $\\{v_{1},v_{2},v_{3}\\}$ be vertices of a triangle in
$G^{\prime}$. Let $i,j\in[\bar{n}^{2/5}]$ such that $v_{1}\in A_{i},v_{2}\in
A_{j}$ and let $P_{i,j}$ be the set of computation units to which the pair
$A_{i},A_{j}$ is mapped. Let $k\in[\bar{n}^{1/5}]$ and $r\in[\bar{n}^{2/5}]$
such that $v_{3}\in S^{(r)}_{k}$ and let $w\in P_{i,j}$ be the core of a
computation unit in $P_{i,j}$ to which $S_{k}$ is mapped. We note that the
triangle is contained in $E_{1}(i,j)\cup E_{2}(i,j,k,r)$, and therefore the
network rejects in the protocol $\mathcal{A}_{r}$, and hence our algorithm
rejects as well.

###  4.2 Quantum Detection of $K_{p}$ for $p\geq 7$

We now show our method for enhancing the $K_{p}$-listing algorithm of [4] with
a quantum procedure that allows us to detect a $K_{p+1}$ instance. To ease the
notation, we will be using $p+1$ for the size of the clique that we are
detecting, and hence note that the following statement is shifted, i.e., holds
for $p\geq 6$.

######  Theorem 4.11.

There exists a quantum algorithm that solves $(p+1)$-clique detection with
success probability at least $1-1/\operatorname{poly}(n)$ in the Quantum
Congest model with complexity $\tilde{O}(n^{1-2/p})$, for $p\geq 6$.

In a nutshell, the algorithm uses a conductance decomposition, and works on
clusters in parallel. There are three ways in which the $K_{p}$-listing
algorithm of [4] may find instances of $K_{p}$. The first two ways involve
having a node learn its induced 2-hop neighborhood, and in these cases, this
clearly gives detection of a $K_{p+1}$ instance if such an instance exists,
without further effort on our part. The third case is where we diverge from
the algorithm of [4] by incorporating Grover searches inside the clusters,
using Lemma 2.1.

During the algorithm, some parts use a simple listing of the edges in a node’s
induced $2$-hop neighborhood. For completeness, we state here a formal claim
and proof of how this is done.

######  Claim 2.

Given a graph $G=(V,E)$, and some value $\alpha$, every node $v$ such that
$\deg(v)\leq\alpha$ can learn its induced $2$-hop neighborhood in at most
$O(\alpha)$ rounds of the Congest model.

######  Proof 4.12 (Proof of Claim 2).

Let $v$ be such a node. Node $v$ iterates over its at most $\alpha$ neighbors.
When it considers neighbor $i$, it sends a message to all its neighbors asking
if they neighbor $i$, to which they each respond whether or not they have an
edge to node $i$. At the end of the iterations, after $O(\alpha)$ rounds, node
$v$ knows all of its induced $2$-hop neighborhood.

Notice that it does not matter if $v$ has a neighbor $u$ which also tries to
perform this search in parallel to $v$, in the odd rounds $v$ and $u$ just
sends queries to each other across their shared edge, and in the even rounds
they each respond to one another.

We are now ready to prove Theorem 4.11.

######  Proof 4.13 (Proof of Theorem 4.11).

We begin by briefly explaining the $K_{p}$ listing algorithm of [4]. The
algorithm of [4] works in iterations, which are composed of stages. In every
stage, some $K_{p}$ in the graph may be listed. We split the listed $K_{p}$
instances according to the stage in the algorithm in which they are listed.
For each stage, we show how to detect in a quantum manner if there is an
instance of $K_{p}$ that is listed in that stage which can be extended to
(i.e., is a part of) an instance of $K_{p+1}$. As such, if there is any
instance of $K_{p+1}$ in the graph, then we will certainly detect this as some
instance of $K_{p}$ could be extended to it.

We now show the $K_{p}$ listing algorithm, and interject at appropriate places
in order to perform quantum searches. Each iteration of the algorithm of [4]
consists of the following steps.

  * 1.

Exhaustive search detection stage. Every node $v$ with degree $O(n^{1/2})$
learns its induced 2-hop neighborhood in $O(n^{1/2})$ rounds using Claim 2,
lists any cliques which it sees involving itself, and removes itself, along
with its incident edges from the graph.

Detection of $K_{p+1}$: In particular, because the entire induced 2-hop
neighborhood is learned, any instance of $K_{p}$ that is listed that can be
extended to an instance of $K_{p+1}$ can be immediately listed in this way
even without further communication, which proves our claim for this stage.

  * 2.

Graph decomposition and cluster exhaustive search detection stage. An expander
decomposition is computed according to Lemma 4.1, with $\gamma=0.1$ (any small
constant would do here), while the above ensures that the average degree in
the graph (and thus in the clusters, due to Lemma 4.1) is at least
$\Omega(n^{1/2})$. In clusters with $O(n^{1-2/p})$ nodes, each node learns its
induced 2-hop neighborhood in $G$ using Claim 2 and lists all the instances of
$K_{p}$ which it is a part of, and finally removes itself and its incident
edges from the graph. Because Lemma 4.1 promises that the number of edges that
leave $C$ is at most $\tilde{O}(|E_{C}|)$, where $E_{C}$ is the set of edges
inside $C$, then this completes in $\tilde{O}(n^{1-2/p})$ rounds.

Detection of $K_{p+1}$: As in the previous stage, because of the exhaustive
search nature of this stage, we again obtain that any instance of $K_{p}$ that
is listed that can be extended to an instance of $K_{p+1}$ can be immediately
listed in this way even without further communication, which proves our claim
for this stage.

  * 3.

Cluster listing. Within every remaining cluster $C$, some nodes are designated
as _good_ and the rest as _bad_. For a good node $v$, the nodes of $C$ learn
amongst themselves (collectively, not necessarily by a single node, and in
particular not necessarily by $v$ itself) all the edges in the induced 2-hop
neighborhood of $v$. That is, the nodes of $C$ request from the nodes
neighboring the cluster to send in edges from outside $C$ to nodes inside $C$,
such that all the induced 2-hop neighborhood of $v$ is known to the nodes in
$C$. Now, the nodes in $C$ ensure that every instance of $K_{p}$ involving $v$
and at least one other node in $C$ is becomes known to some node in $C$ – that
is, these $K_{p}$ instances are listed by $C$. The good nodes are then removed
from the graph along with all of their edges.

This concludes the description of the Congest algorithm in [4]. The exact
definition of good nodes is not required for our purpose. The proof of [4]
shows that each iteration completes within $\tilde{O}(n^{1-2/p})$ rounds, and
that after $\operatorname{poly}\log(n)$ iterations the remaining graph is
empty and hence $\tilde{O}(n^{1-2/p})$ rounds are sufficient for the entire
algorithm.

The cluster quantum detection stage. We now provide the quantum procedure that
we run after the above Cluster listing stage, in order to detect an instance
of $K_{p+1}$ that contains an instance of $K_{p}$ that was listed during this
stage. First, let the $C$-degree of a node be its number of neighbors in $C$,
let $\mu_{C}$ be the average $C$-degree of nodes in $C$, and let $H(C)$ be the
high $C$-degree cluster nodes, namely, those of $C$-degree $\Omega(\mu_{C})$.
Notice that due to the invocation above of Lemma 4.1, it holds that
$\mu_{C}=\Omega(n^{1/2})$. A more precise description of the algorithm in [4]
is that the induced 2-hop neighborhood of each good node $v$ becomes known to
the nodes in $H(C)$ rather than to any node in $C$. Second, denote by
$N^{+}(C)$ the set of nodes which have a neighbor in $C$ (this includes all of
$C$ as $C$ is connected, by definition) and by $N(C)=N^{+}(C)-C$ the neighbors
of $C$ outside of $C$. In the above Cluster listing stage we piggyback the
degree (not $C$-degree) of every node in $N(C)$ onto the messages containing
its edges, so that the degrees of all nodes in $N(C)$ are also known to nodes
of $H(C)$.

The quantum process starts with the following. The nodes in $C$ elect some
arbitrary leader $v_{C}\in H(C)$. This can be done in
$\operatorname{poly}\log(n)$ rounds because this is a bound on the diameter of
the cluster, by Lemma 4.1. The nodes of $H(C)$ now broadcast within $H(C)$ the
degrees of all the nodes in $N(C)$. This is done in two steps. In the first
step, each node in $H(C)$ sends $v_{C}$ the degrees of nodes in $N(C)$ which
it knows about. As every node sends and receives at most $|N(C)|=O(n)$ pieces
of information, and every node in $H(C)$ has $C$-degree at least
$\Omega(\mu_{C})=\Omega(n^{1/2})$, this takes at most $\tilde{O}(n^{1/2})$
rounds, using the routing algorithm of Theorem 4.2 with a sufficiently small
$\gamma$. In the second step, $v_{C}$ makes this information known to all
nodes in $H(C)$ using a simple doubling procedure: in each phase of this
procedure, each informed node shares the information with a unique uninformed
node. Each phase completes in $\tilde{O}(n^{1/2})$ rounds by the same argument
using the routing algorithm of Theorem 4.2, and the number of phases is
logarithmic. In a similar fashion, the nodes in $H(C)$ learn all the degrees
of the nodes in $C$.

Knowing the degrees of all nodes in $N^{+}(C)$, the nodes $H(C)$ _bucket_
$N^{+}(C)$ by degrees. That is, they compute
$N^{+}(C)=N^{+}_{1}(C),\dots,N^{+}_{\log n}(C)$, such that the degree of any
$v\in N^{+}_{i}(C)$ is in $[2^{i-1},\dots,2^{i})$. Our goal is to iterate over
the $\log n$ buckets, whereby in each bucket we check whether a node $v$ in
$N^{+}_{i}(C)$ can be used to extend some $K_{p}$ instance, which is already
listed by $H(C)$, into an instance of $K_{p+1}$. This is done as follows.

Fix an $i$ between 1 and $\log n$. We perform a Grover search over $v\in
N^{+}_{i}(C)$ using $v_{C}$ as the leader of the search: In each query (i.e.,
over such a $v$), we broadcast within $H(C)$ all the neighbors of $v$ which
are known to $H(C)$, in order to try to extend any $K_{p}$ listed by $H(C)$ to
a $K_{p+1}$ involving $v$. Let $\kappa_{p}$ be such a $K_{p}$. As it is listed
by $H(C)$, it must involve at least one good node in $C$, denoted
$g\in\kappa_{p}$. Further, recall that every edge in the induced 2-hop
neighborhood of $g$ is known to $H(C)$. Thus, if $v$ that can be used to
extend $\kappa_{p}$ to an instance of $K_{p+1}$, all the edges between $v$ and
$\kappa_{p}$ are known to the nodes of $H(C)$. Therefore, if we manage to
broadcast in $H(C)$ all the edges incident to $v$ that are known to $H(C)$,
then if there is a way to use $v$ to extend a $K_{p}$ listed by $H(C)$ to a
$K_{p+1}$, we will certainly find it. Similarly to the above analysis, using
the routing algorithm of Theorem 4.2 and the doubling procedure, we broadcast
within $H(C)$ the edges incident to $v$ which are known to $H(C)$. This
completes in $O(2^{i}/\mu_{C}+1)$ rounds, as the degree of $v$ is at most
$2^{i}$.

In order to conclude the proof, we need to bound the size of each
$N^{+}_{i}(C)$. iIn order to obtain the bound on the size of $N^{+}_{i}(C)$,
we compute an upper bound on the number of _all_ edges incident to nodes in
$N^{+}(C)$ and use the bound on degrees of nodes in the bucket. To this end,
we wish to show that $\sum_{v\in N^{+}(C)}\deg(v)=\tilde{O}(n\cdot\mu_{C})$.
To do so, we split the edges into three categories: $E_{1}$ – edges with both
endpoints in $C$; $E_{2}$ – edges with one endpoint in $C$; $E_{3}$ – edges
with both endpoints not in $C$. As $\mu_{C}$ is the average $C$-degree of the
nodes in $C$, and $n$ is the number of nodes in the entire graph, implying
$|C|\leq n$, it holds that $E_{1}=O(n\cdot\mu_{C})$. It is ensured in Lemma
4.1 that for every $v\in C$, it holds that $\deg(v)=\tilde{O}(\deg_{C}(v))$,
where $\deg_{C}(v)$ is the $C$-degree of $v$, implying
$|E_{2}|=\tilde{O}(|E_{1}|)=\tilde{O}(n\cdot\mu_{C})$. Further, it is ensured
in Lemma 4.1 that $|E_{3}|/n=\tilde{O}(|E_{1}|/|C|)=\tilde{O}(\mu_{C})$,
implying that $|E_{3}|=\tilde{O}(n\cdot\mu_{C})$. Thus, for every
$N^{+}_{i}(C)$, due to the degrees in the bucket and due to the pigeonhole
principle, it must be that $|N^{+}_{i}(C)|=\tilde{O}(n\cdot\mu_{C}/2^{i})$.
Further, as $n$ is the number of nodes in the graph, it also trivially holds
that $|N^{+}_{i}(C)|\leq n$. All in all, we get that
$|N^{+}_{i}(C)|=\tilde{O}(\min\\{n,n\cdot\mu_{C}/2^{i}\\})$.

Finally, we can analyze the round complexity of the algorithm. The $K_{p}$
listing algorithm is shown in [4] to take $\tilde{O}(n^{1-2/p})$ rounds. For
each $i$, the checking procedure in our Grover search takes
$\tilde{O}(2^{i}/\mu_{C}+1)$ rounds. For every $i$ such that
$2^{i}/\mu_{C}\leq 1$, the checking procedure takes $O(1)$, and
$|N^{+}_{i}(C)|=\tilde{O}(n)$, implying that the Grover search takes a total
of $\tilde{O}(n^{1/2})$ rounds, using Lemma 2.1. For every $i$ such that
$2^{i}/\mu_{C}>1$, the checking procedure takes
$\tilde{O}(2^{i}/\mu_{C}+1)=\tilde{O}(2^{i}/\mu_{C})$, and
$|N^{+}_{i}(C)|=\tilde{O}(n\cdot\mu_{C}/2^{i})$, implying that the Grover
search takes a total of
$\tilde{O}(\sqrt{n\cdot\mu_{C}/2^{i}}\cdot(2^{i}/\mu_{C}))=\tilde{O}(\sqrt{n\cdot(2^{i}/\mu_{C})})$
rounds, using Lemma 2.1. As $2^{i}=O(n)$ and $\mu_{C}=\Omega(n^{1/2})$ (due to
the guarantees of the invocation of Lemma 4.1, as stated above), this takes at
most $\tilde{O}(n^{3/4})$ rounds.

We thus have that our quantum algorithm for detecting an instance of $K_{p+1}$
for $p\geq 5$ completes in $\tilde{O}(n^{3/4}+n^{1-2/p})$ rounds, with
probability at least $1-1/\operatorname{poly}(n)$.

We note that we can decrease the $\tilde{O}(n^{3/4})$ part of the complexity,
by slightly changing the listing algorithm of [4]. That is, the algorithm
stated there performs $K_{p}$ listing in $\tilde{O}(n^{1-2/p})$ rounds, while
ensuring $\mu_{C}=\Omega(n^{1/2})$. It is implied in the proofs in [4] that,
for any $1/2\leq\delta<1$, one can pay an additional $\tilde{O}(n^{\delta})$
rounds (by performing an exhaustive search, as done in Claim 2) in order to
ensure $\mu_{C}=\Omega(n^{\delta})$. Further, notice that our Grover searches
take a total of
$\tilde{O}(n^{1/2}+n/\mu_{C}^{1/2})=\tilde{O}(n^{1/2}+n^{1-\delta/2})$ rounds.

All in all, for any $1/2\leq\delta<1$, our algorithm requires
$\tilde{O}(n^{1-2/p}+n^{\delta}+n^{1/2}+n^{1-\delta/2})=\tilde{O}(n^{1-2/p}+n^{\delta}+n^{1-\delta/2})$
rounds. One can set $\delta=2/3$, giving a final algorithm running in
$\tilde{O}(n^{1-2/p}+n^{2/3}+n^{1-1/3})=\tilde{O}(n^{1-2/p}+n^{2/3})=\tilde{O}(n^{1-2/p})$
rounds, where the last transition is since $p\geq 6$.

##  5 Faster Clique Detection in the Quantum Congested Clique Model

We present here an approach that improves upon our approach in Section 3 by
taking into consideration _which_ clique nodes know of which copies of
$K_{p}$: instead of treating the $K_{p}$-listing algorithm as a black box, we
explicitly use the $K_{p}$-listing algorithm of [12], so that we know which
copies of $K_{p}$ will be listed by each clique node, and what other
information that node already has. We then search for $(p+t)$-cliques by
having each clique node learn only the edges that it needs to check if the
$p$-cliques it has listed can be extended. (In the previous approach, edges
could be learned by nodes that had no use for them, since they were not
adjacent to any $p$-clique that the node had listed.)

Throughout this section we use the following notation: we let
$\bigtimes(S_{1},\ldots,S_{k})$ denote the Cartesian product
$S_{1}\times\ldots\times S_{k}$. Also, we denote by $E(S_{1},\ldots,S_{k})$
the edges $E\cap\bigcup_{i\neq j}\left(S_{i}\times S_{j}\right)$ that cross
between any two sets $S_{i},S_{j}$.

For presenting our algorithm for a general $p$, we first shortly review the
listing algorithm of Dolev et al. [12]. Fix an arbitrary partition
$S_{1},\ldots,S_{n^{1/p}}$ of the nodes of $V$, such that $|S_{i}|=n^{1-1/p}$
for each $i$, and a 1:1 mapping
$g:V\rightarrow\left\\{1,\ldots,n^{1/p}\right\\}^{p}$ assigning to each node
$v\in V$ a $p$-tuple
$g(v)=(i_{1},\ldots,i_{p})\in\left\\{1,\ldots,n^{1/p}\right\\}^{p}$. We assume
for simplicity that $n^{1/p}$ is an integer; otherwise, we can adjust the set
size to an integer, without changing the asymptotic complexity of the
algorithm.

For each node $v\in V$ and index $j\in\left\\{1,\ldots,p\right\\}$, let
$T_{j}^{v}=S_{g(v)_{j}}$. (That is, if $g(v)=(i_{1},\ldots,i_{p})$, then
$T_{1}^{v}=S_{i_{1}},\ldots,T_{p}^{v}=S_{i_{p}}$.) Also, let
$T^{v}\coloneq\bigcup_{j=1}^{p}T_{j}^{v}$. Node $v$ is responsible for listing
all $p$-cliques
$(u_{1},\ldots,u_{p})\in\bigtimes(T_{1}^{v},\ldots,T_{p}^{v})$. To do so, node
$v$ needs to learn all edges in $E(T_{1}^{v},\ldots,T_{p}^{v})$; there are at
most $p(n^{1-1/p})^{2}=O(n^{2-2/p})$ such edges, which, using Lenzen’s routing
scheme, can be collected in $O(n^{2-2/p-1})=O(n^{1-2/p})$ rounds. After
collecting the edges in $E(T_{1}^{v},\ldots,T_{p}^{v})$, node $v$ locally
enumerates all $p$-cliques it sees.

###  5.1 $K_{p+1}$-Detection from $K_{p}$-Listing

We start by showing how to use the $K_{p}$ listing algorithm for obtaining
$K_{p+1}$-detection, stated as follows.

######  Theorem 5.1.

For any $p\geq 3$, the $K_{p+1}$-detection problem in the Quantum Congested
Clique can be solved in $\tilde{O}(n^{(1-1/p)/2}+n^{1-2/p})$ rounds.

######  Proof 5.2.

First, we let each node $v\in V$ collect all edges in $E(T^{v}\times T^{v})$,
and list all cliques in $\bigtimes(T_{1}^{v},\ldots,T_{p}^{v})$, as described
above.

Our goal now is for each node $v\in V$ to check whether there is a node $u\in
V$ that extends a $p$-clique found by node $v$ in the previous step into a
$(p+1)$-clique. In other words, node $v$ searches for $(p+1)$-cliques in
$\bigtimes(T_{1}^{v},\ldots,T_{p}^{v},V)$.

To speed up the search, we partition the nodes of $V$ into $n^{1-1/p}$
batches, $Q_{1},\ldots,Q_{n^{1-1/p}}$, each of size $n^{1/p}$. We then use a
Grover search (Lemma 2.1) to find an index $i$ such that
$\bigtimes(T_{1}^{v},\ldots,T_{p}^{v},Q_{i})$ contains a $(p+1)$-clique (or
determine that there is no such $i$).

We denote by $A_{i}$ a query for determining whether
$\bigtimes(T_{1}^{v},\ldots,T_{p}^{v},Q_{i})$ contains a $(p+1)$-clique, and
we now describe how each query is implemented. In $A_{i}$, node $v$ needs to
collect all edges in $E(T,Q_{i})$; recall that $T=\bigcup_{j=1}T_{j}^{v}$, and
its size is $|T|\leq p\cdot n^{1-1/p}$. Since $|Q_{i}|=n^{1/p}$, the number of
edges $v$ needs to learn about is $n^{1-1/p}\cdot n^{1/p}=n$, and using
Lenzen’s routing scheme. this can be done in a single round. After learning
the relevant edges, node $v$ locally searches for a $(p+1)$-clique contained
in the edges it has learned; it outputs “yes” if and only if it finds one.

The running time of the resulting algorithm is as follows. Executing the
$K_{p}$-listing algorithm from [12] requires $O(n^{1-2/p})$ rounds. The Grover
search requires $\sqrt{n^{1-1/p}}$ queries, each requiring a single round.
Using Lemma 2.1, the overall running time is therefore
$\tilde{O}(n^{(1-p)/2})$ for the quantum search, in addition to the
$O(n^{1-2/p})$ rounds required for $K_{p}$-listing. Specifically, for
$K_{4}$-detection ($p=3$), the total running time we obtain is
$\tilde{O}(n^{1-2/3}+n^{1/2-1/6})=\tilde{O}(n^{1/3})$.

Theorem 5.1 gives, combined with the algorithm of Section 3.1, the statement
of Theorem 1.1 in the introduction.

###  5.2 $K_{p+t}$-Detection from $K_{p}$-Listing

Now, we prove the following theorem, which shows how to obtain
$K_{p+t}$-detection from $K_{p}$-listing.

######  Theorem 5.3.

Given a graph $G=(V,E)$ and values $p$, $t$ such that $t\leq
1+\log\left(p-1\right)$, it is possible to detect if $G$ contains an instance
of $K_{p+t}$ in $\tilde{O}(n^{(1-1/p)(1-1/2^{t})}+n^{1-2/p})$ rounds of
communication in the Quantum Congested Clique, w.h.p.

Optimizing our results over all choices of $p,t$ yields the following:

######  Corollary 5.4.

The time required to solve $K_{p+t}$-detection in Quantum Congested Clique is

$\tilde{O}\left(\min_{p,t:t\leq
1+\log\left(p-1\right)}\left(n^{(1-1/p)(1-1/2^{t})}+n^{1-2/p}\right)\right).$

######  Proof 5.5 (Proof of Theorem 5.3).

High-level overview. We again first let each node $v\in V$ collect all edges
in $E(T^{v}\times T^{v})$, and list all cliques in
$\bigtimes(T_{1}^{v},\ldots,T_{p}^{v})$. Now we want to solve $(p+t)$-clique
detection, having already listed all $p$-cliques using the algorithm of [12].

To do this, we generalize the +1 extension from the previous section using a
_recursive_ search procedure, $\mathsf{check}_{k}(P_{1},\ldots,P_{k},F)$ where
$k\leq p+t$. The procedure is given $k$ sets of nodes,
$P_{1},\ldots,P_{k}\subseteq V$, and the set $F$ of all edges in
$E(P_{1},\ldots,P_{k})$; it recursively checks whether there is a $k$-clique
$(u_{1},\ldots,u_{k})\in\bigtimes(P_{1},\ldots,P_{k})$ that can be extended
into a $(p+t)$-clique. The recursion begins at $k=p$, with the sets
$P_{1}=T_{1}^{v},\ldots,P_{p}=T_{p}^{v}$, and the edges that node $v$
collected in the pre-processing stage; the recursion terminates at $k=p+t$,
where node $v$ enumerates all $(p+t)$-tuples $(u_{1},\ldots,u_{p+t})\in
P_{1}\times\ldots\times P_{p+t}$ and checks using the edges of $F$ whether one
of them forms a $(p+t)$-clique. Next, we explain how each internal level of
the recursion is implemented. Fix $t$ predetermined partitions of the nodes of
$V$, where the $i$-th partition is given by
$X_{i}^{1},\ldots,X_{i}^{n^{r_{i}}}$ for a parameter $r_{i}\in(0,1)$, and all
subsets in each partition have the same size:
$|X_{i}^{1}|=\ldots=|X_{i}^{n^{r_{i}}}|=n^{1-r_{i}}$. (We assume again for
simplicity that $n^{r_{i}}$ is an integer.) For
$i\in\left\\{0,\ldots,t-1\right\\}$, when
$\mathsf{check}_{p+i}(P_{1},\ldots,P_{p+i},F)$ is called, node $v$ uses a
Grover search to check if there is some set $X_{i+1}^{j}$ such that
$\mathsf{check}_{p+i}(P_{1},\ldots,P_{p+i},X_{i+1}^{j},F^{\prime})$ returns
true, where $F^{\prime}=E(P_{1},\ldots,P_{p+i},X_{i+1}^{j})$. Each query
$A_{j}$ in the Grover search takes the index $j\in[n^{r_{i}}]$ as input,
learns all the edges in $F^{\prime}\setminus F$ (the edges of $F$ are already
known), and calls
$\mathsf{check}_{p+i+1}(P_{1},\ldots,P_{p+i},X_{i+1}^{j},F^{\prime})$.

The formal algorithm. Fix $p\geq 2$ and $t\geq 1$ satisfying the constraint.
Also, for each $i=1,\ldots,t$, fix a partition
$X_{i}^{1},\ldots,X_{i}^{n^{r_{i}}}$ of $V$, where

$r_{i}=(1-1/p)/2^{t-i},$

and $|X_{i}^{1}|=\ldots=|X_{i}^{n^{r_{i}}}|=n^{1-r_{i}}$. The partitions are
arbitrary, but fixed in advance, so no communication is necessary to compute
them. Note that $r_{i}\geq 1/p$ for each $i=1,\ldots,t$.

Our algorithm is a depth-$t$ nested quantum search, over the search space
$[n^{r_{1}}]\times\ldots\times[n^{r_{t}}]$, with the goal function
$f:[n^{r_{1}}]\times\ldots\times[n^{r_{t}}]\rightarrow\left\\{0,1\right\\}$
such that $f(i_{1},\ldots,i_{t})=1$ iff there exists a $p$-clique
$v_{1},\ldots,v_{p}\in V^{p}$, and there exist $u_{1}\in
X_{1}^{i_{1}},\ldots,u_{t}\in X_{t}^{i_{t}}$, such that
$v_{1},\ldots,v_{p},u_{1},\ldots,u_{t}$ is a $(p+t)$-clique.

Before the quantum search begins, the nodes list all $p$-cliques in the graph;
each node $v$ learns all edges in $E(T_{1}^{v},\ldots,T_{p}^{v})$ as described
in the beginning of the section.

The setup algorithms $\mathcal{S}_{1},\ldots,\mathcal{S}_{t-1}$ are as
follows: in $\mathcal{S}_{i}$, the leader disseminates the current partial
search query
$(j_{1},\ldots,j_{i})\in[n^{r_{1}}]\times\ldots\times[n^{r_{i}}]$. The nodes
use Lenzen’s routing scheme (Lemma 3.1) so that each $v\in V$ learns the edges
$E(T_{1}^{v}\cup\ldots\cup T_{p}^{v}\cup X_{1}^{j_{1}}\cup\ldots\cup
X_{i-1}^{j_{i-1}},X_{i}^{j_{i}})$. The running time $s_{i}$ of
$\mathcal{S}_{i}$ is $O(n^{1-1/p-r_{i}})$: we have $|T_{1}^{v}\cup\ldots\cup
T_{p}^{v}|=O(n^{1-1/p})$ (treating $p$ as a constant),
$|X_{1}^{j_{1}}\cup\ldots\cup X_{i-1}^{j_{i-1}}|=O(n^{1-1/p})$ (by our
assumption that $r_{i}\geq 1/p$ and treating $t$ as a constant), and
$|X_{i}^{j_{i}}|=O(n^{1-r_{i}})$. By Lemma 3.1, the information can be routed
in $O(n^{1-1/p+1-r_{i}-1})=O(n^{1-1/p-r_{i}})$ rounds.

The final classical evaluation procedure, $\mathcal{C}$, is as follows: the
leader disseminates the query
$(j_{1},\ldots,j_{t})\in[n^{r_{1}}]\times\ldots\times[n^{r_{t}}]$ to all
nodes, and the nodes use Lenzen’s routing scheme so that each $v\in V$ learns
the edges $E(T_{1}^{v}\cup\ldots\cup T_{p}^{v}\cup X_{1}^{j_{1}}\cup\ldots\cup
X_{t-1}^{j_{t-1}},X_{t}^{j_{t}})$. Together with the edges in
$\bigcup_{i<t}\mathsf{setup}_{i}^{t}(j_{1},\ldots,j_{i})$, each node $v$ now
knows $E(T_{1}^{v},\ldots,T_{p}^{v},X_{1}^{j_{1}},\ldots,X_{t}^{j_{t}})$. Node
$v$ now checks whether it sees a $(p+t)$-clique, and informs the leader. The
running time of $\mathcal{C}$ is $O(n^{1-1/p-r_{t}})$ (as above).

By Lemma 2.2, the overall running time of the quantum search is given by

$\displaystyle\\!\\!\\!\\!\\!\\!\tilde{O}\\!\left(n^{r_{1}/2}\\!\left(n^{1-1/p-r_{1}}\\!+\\!n^{r_{2}/2}\\!\cdot\\!\left(n^{1-1/p-r_{2}}\\!+\\!\ldots\\!+\\!n^{r_{t-1}/2}\left(n^{1-1/p-r_{t-1}}\\!+\\!n^{r_{t}/2}\cdot
n^{1-1/p-r_{t}}\right)\\!\right)\\!\right)\\!\right)\\!.$

Denote by $g(i)$ the running time of the innermost $t-i+1$ levels of the
search, starting from level $i$ up to level $t$:

$\displaystyle
g(i)=\tilde{O}\left(n^{r_{i}/2}\left(n^{1-1/p-r_{i}}+\ldots+n^{r_{t-1}/2}\left(n^{1-1/p-r_{t-1}}+n^{r_{t}/2}\cdot
n^{1-1/p-r_{t}}\right)\right)\right).$

We claim, by backwards induction on $i$, that

$g(i)=\tilde{O}(n^{(1-1/p)(1-1/2^{t-i+1})}).$ (1)

For the base case, $i=t$, we have

$\displaystyle g(i)=\tilde{O}\left(n^{r_{t}/2}\cdot
n^{1-1/p-r_{t}}\right)=\tilde{O}\left(n^{1-1/p-r_{t}/2}\right)=\tilde{O}\left(n^{1-1/p-(1-1/p)/2}\right)=\tilde{O}\left(n^{(1-1/p)/2}\right),$

and indeed this matches (1). For the induction step, suppose the claim holds
for $i$, and consider $g(i-1)$:

$\displaystyle g(i-1)$
$\displaystyle=\tilde{O}\left(n^{r_{i-1}/2}\left(n^{1-1/p-r_{i-1}}+g(i)\right)\right)$
$\displaystyle=\tilde{O}\left(n^{(1-1/p)/2^{t-i+1}/2}\left(n^{1-1/p-(1-1/p)/2^{t-i+1}}+n^{(1-1/p)(1-1/2^{t-i+1})}\right)\right)$
$\displaystyle=\tilde{O}\left(n^{(1-1/p)/2^{t-i+2}}\cdot
2n^{(1-1/p)(1-1/2^{t-i+1})}\right)$
$\displaystyle=\tilde{O}\left(n^{(1-1/p)(1-1/2^{t-i+2})}\right),$

again matching (1).

We thus obtain that the running time of the entire quantum search is

$g(1)=\tilde{O}\left(n^{(1-1/p)(1-1/2^{t})}\right),$

and together with the complexity of listing the initial $p$-clique, we get the
claimed complexity.

A note on the restriction on $p,t$. Recall that we assumed throughout that
$1-r_{i}\leq 1-1/p$ for each $i=1,\ldots,t$, so that the sets of nodes we
handle at each step never exceed the size of the sets in the $p$-clique-
listing pre-processing step ($n^{1-1/p}$). In other words, we must have
$r_{i}\geq\frac{1}{p}$. The value of $r_{i}$ decreases with $i$, so it
suffices to require that $r_{1}\geq 1/p$. We now see that not every choice of
$p,t$ respects this condition: since we set
$r_{1}=\frac{1}{2^{t-1}}\left(1-\frac{1}{p}\right)$, we require that $p,t$
satisfy $t\leq 1+\log\left(p-1\right)$.

For example, suppose we want to start by lising all triangles ($p=3$), and
extend to $K_{5}$ (i.e., $t=2$). This is possible, since $2\leq
1+\log\left(3-1\right).$ However, extending from triangles to $K_{6}$ using
the approach described here is not possible, because if we take $p=3$ and
$t=3$, we get $3\not\leq 1+\log\left(3-1\right).$

Although we think of $p,t$ as constants, we observe that when $p$ is large and
$t\approx\log(p)$, the overall running time of the quantum part of our scheme
is $\approx n^{1-2/p}$. Thus, the cost of extending from $p$-cliques to
$(p+t)$-cliques roughly matches the cost of the classical $p$-clique listing,
which is $n^{1-2/p}$, and we get a quantum algorithm for $K_{p+t}$-detection
that roughly matches the cost of classical $K_{p}$-listing.

##  6 Circuit-Complexity Barrier to Proving an $\Omega(n^{3/5+\alpha})$-Round
Lower Bound for Clique Detection in the Congest Model

In this section, we show that for any $\alpha>0$, a lower bound of the form
$\Omega(n^{3/5+\alpha})$ for $K_{p}$-detection in (non-quantum) Congest would
imply strong circuit complexity results, far beyond the current state-of-the-
art. As mentioned in the introduction, this barrier also applies to the
Quantum Congest model.

Given a constant integer $\alpha>0$, let $\mathcal{F}_{\alpha}$ be the family
of Boolean circuits $F$ where:

  * •

$F$ has $M\log{M}$ input wires for some integer $M$, which we interpret as
encoding a graph $\bar{G}$ on $O(M)$ edges.

  * •

All gates in $F$ have constant fan-in and fan-out.

  * •

$F$ has depth at most $R=M^{\alpha}$.

  * •

$F$ has at most $M^{1+\alpha}$ wires in total.

######  Theorem 6.1.

If $K_{p}$-detection has a round complexity of $\Omega(n^{3/5+\alpha})$ for
some constant $\alpha>0$, then there is no circuit family contained in
$\mathcal{F}_{\alpha}$ that solves $K_{p}$-detection.

In other words, a lower bound of the form $\Omega(n^{3/5+\alpha})$ for any
constant $\alpha>0$ rules out the existence of a circuit with polynomial depth
and super-linear size (in terms of wires) for an explicit problem,
$K_{p}$-detection. Such a lower bound would be a major breakthrough in circuit
complexity (see [13] for discussion). This gives the statement of Theorem 1.3
in the introduction.

The proof of Theorem 6.1 is essentially a reduction from $K_{p}$-detection in
general graphs to $K_{p}$-detection in high-conductance graphs. It was shown
in [13] that in high-conductance graphs, we can efficiently _simulate_ a
circuit from the family $\mathcal{F}_{\alpha}$ of certain size, so given such
a circuit for $K_{p}$-detection, we can use it to solve the distributed
$K_{p}$-detection problem in high-conductance graphs. To reduce from general
graphs to high-conductance graphs, we use a similar approach to the clique
detection algorithm of [4]: we first compute an expander-decomposition
procedure from to partition the graph into high-conductance clusters with few
inter-cluster edges, and have the nodes of the clusters learn the relevant
sets of edges in the clusters’ neighborhood, so that we either find a
$K_{p}$-copy or can remove most of edges of the graph without removing a
$K_{p}$-copy, and recurse on the remaining edges.

###  6.1 Reducing $K_{p}$-Freeness From General Graphs to High-Conductance
Graphs

To reduce from general graphs to high-conductance components, we use several
results from [4]. We require slightly different parameters than the ones used
in [4], so for the sake of completeness, we re-analyze these procedure for in
Appendix A.

For a set of vertices $A$, we denote by $N(A)=(\bigcup_{v\in A}N(v))\setminus
A$ the set of neighbors of $A$.

Assume that we have a procedure $\mathcal{A}$ which solves $K_{p}$-detection
on high conductance graphs, where nodes may have some additional input edges,
which are not communication edges. In this subsection, we show how to solve
$K_{p}$-detection in general graphs using $\mathcal{A}$, and in the next
subsection we show how to obtain an efficient procedure $\mathcal{A}$ assuming
the existence of a circuit family $\mathcal{F}_{\alpha}$ that solves
$K_{p}$-detection. The reduction now proceeds as follows.

First, the network runs the decomposition of Lemma 4.1 to obtain a partition
of the edges to set $E_{m},E_{r}$ with the described properties.

Next, we show that in parallel for all small clusters $C$, the network can can
determine efficiently whether there is a $K_{p}$-copy containing a node of
$C$. This is again a variation on a claim from [4].

######  Lemma 6.2 ([4], Lemma 4.2).

There is a procedure that terminates after $O(n^{3/5})$ rounds in which the
network can determine whether there is a $K_{p}$-copy which at least one of
its nodes is contained in a cluster of size $|V_{C}|\leq n^{3/5}$.

Following this, by Lemma 6.3 there is an $\tilde{O}(n^{3/5})$-round procedure
in which for each cluster $C$, and each vertex $v\in V_{C}$ in the cluster
learns the neighborhood induced by their neighbors outside $C$.

Therefore, we turn our attention to large clusters. For a cluster $C$, let
$S^{*}_{C}=\\{u\in N(C)\mid\deg_{V_{C}}(u)\leq\deg_{V\setminus
V_{C}}(u)/n^{3/5}\\}$ be the set of nodes $v$ adjacent to the cluster, such
that the number of neighbors $v$ has in $C$ is larger by a factor of at least
$n^{3/5}$ than the number of neighbors $v$ has outside $C$. Let $S_{C}=\\{u\in
V_{C}\mid\deg_{S^{*}_{C}(v)}\geq n^{3/5}\\}$ be the set of nodes in $C$ that
have at least $n^{3/5}$ neighbors in $S^{*}_{C}$. Informally, we think of
$S_{C}$ as _bad_ cluster nodes, and $S^{*}_{C}$ as bad nodes neighboring the
cluster.

We claim that each large cluster can efficiently “pull in” all the “non-bad”
edges in its vicinity that it needs to check for copies of $K_{p}$ that
involve a node in $C\setminus S_{C}$:

######  Lemma 6.3 (Implicit in [4]; Lemma A.5 in Appendix A).

In $\tilde{O}(n^{3/5})$ rounds, the network can for each cluster $C$ with
$|V_{C}|\geq n^{3/5}$ partition $E(N(C)\setminus S^{*}_{C},N(C))$ into sets
$\\{E_{v,C}\\}_{v\in C}$, each of size at most $\tilde{O}(n^{3/5}\deg{v})$,
and have each node $v\in V_{C}$ learn the edges of $E_{v,C}$, and in addition,
each node $v\in C\setminus S_{C}$ learns the set $E^{\prime}_{v,C}=E(N(v)\cap
S^{*}_{C},N(v)\cap S^{*}_{C})$.

Next, each cluster runs the $K_{p}$-detection procedure $\mathcal{A}$ with the
edges of the cluster as inputs, and where every node is given as additional
input the set of edges $E_{v,C}\cup E^{\prime}_{v,C}$.

We note that by Lemma 6.3, the only edges from the vicinity of a cluster $C$
not contained in $\bigcup_{v\in C}E_{v,C}\cup\bigcup_{v\in C\setminus
S_{C}}E^{\prime}_{v,C}$ are edges in $S^{*}_{C}\times S^{*}_{C}$ whose
endpoints do not share a neighbor in $C\setminus S_{C}$. Therefore, if no
$K_{p}$-copy was found in the clusters, we know that any $K_{p}$-copy must be
contained in the edge set

$E_{\mathit{recurse}}=E_{r}\cup\bigcup_{C:|V_{C}|\geq n^{3/5}}E(S_{C},S_{C}),$

In the following lemma, we note that the total number of edges in between any
two bad cluster nodes of in all of the clusters is not large.

######  Lemma 6.4 (Implicit in [4]; Lemma A.3 in Appendix A).

We have $\bigcup_{C:|V_{C}|\geq n^{3/5}}|E(S_{C},S_{C})|\leq\epsilon m$.

Therefore the set $E_{\mathit{recurse}}$ is of size at most $2\epsilon m$, and
we recurse on this set. If a node found no $K_{p}$-copy in all recursion
steps, it accepts.

###  6.2 Simulating Circuits On High-Conductance Graphs

Next, we use the theorem presented in [13] for relating lower bounds in high
conductance networks to circuit complexity.

######  Lemma 6.5 ([13]).

Let $U$ be a graph $U=(V,E)$ with $|V|=\bar{n}$ vertices and
$|E|=\bar{n}^{1+\rho}$ edges, with mixing time $\tau_{\textrm{mix}}$. Suppose
that $f:\\{0,1\\}^{c\bar{n}^{1+\rho}\log{n}}\rightarrow\\{0,1\\}$ for some
integer $c>1$ is computed by a circuit $\mathcal{C}$ of depth $R$, comprising
of gates with constant fan-in and fan-out, and at most $O(c\cdot
s\cdot\bar{n}^{1+\rho}\log{\bar{n}})$ wires. Then for any input partition that
assigns to each vertex in $U$ no more than $c\deg(v)\log{n}$ input wires,
there is an $O(R\cdot c\cdot s\cdot\tau_{\textrm{mix}}\cdot
2^{O(\sqrt{\log\bar{n}\log\log\bar{n}})})$-round protocol in the Congest model
on $U$ that computes $f$ under the input partition.

Taking $c=\tilde{\Theta}(n^{3/5})$, $R=n^{\alpha/2},s=\Theta(n^{\alpha/2})$
and $f$ to be the function that given the encoding of edges outputs whether
the graph on these edges is $K_{p}$-free, we get that given a constant fan-in
fan-out gate circuit with $O(s\cdot c\cdot n^{1+\delta}\log{n})$ wires and
depth $R$ that solves $f$, we could solve $K_{p}$-detection in Congest in
$O(n^{3/5+\alpha+o(1)})$ rounds, since each node has indeed
$\tilde{O}(n^{3/5}\deg_{C}(v))$ input edges to encode, we can encode its input
with at most $\tilde{O}(n^{3/5}\deg_{C}(v))$ input wires. Therefore, if the
round complexity of $K_{p}$-detection in Congest is $\Omega(n^{3/5+\alpha})$
for some constant $\alpha>0$, there are circuit family in
$\mathcal{F}_{\alpha^{\prime}}$ for some constant $\alpha^{\prime}>0$ which
solves $K_{p}$-detection, which implies Theorem 6.1.

## References

  * [1] Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Christoph Lenzen.  Fooling views: a new lower bound technique for distributed computations under congestion.  Distributed Computing, 33(6):545–559, 2020.
  * [2] Heger Arfaoui and Pierre Fraigniaud.  What can be computed without communications?  SIGACT News, 45(3):82–104, 2014.
  * [3] Michael Ben-Or and Avinatan Hassidim.  Fast quantum byzantine agreement.  In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pages 481–485, 2005.
  * [4] Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, and Dean Leitersdorf.  Tight distributed listing of cliques.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 2878–2891, 2021.
  * [5] Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman.  Fast distributed algorithms for girth, cycles and small subgraphs.  In Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020), pages 33:1–33:17, 2020.
  * [6] Keren Censor-Hillel, François Le Gall, and Dean Leitersdorf.  On distributed listing of cliques.  In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 474–482, 2020.
  * [7] Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela.  Algebraic methods in the congested clique.  Distributed Computing, 32(6):461–478, 2019.
  * [8] Yi-Jun Chang, Seth Pettie, and Hengjie Zhang.  Distributed triangle detection via expander decomposition.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 821–840, 2019.
  * [9] Yi-Jun Chang and Thatchaphol Saranurak.  Improved distributed expander decomposition and nearly optimal triangle enumeration.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 66–73, 2019.
  * [10] Artur Czumaj and Christian Konrad.  Detecting cliques in CONGEST networks.  Distributed Computing, 33(6):533–543, 2020.
  * [11] Vasil S. Denchev and Gopal Pandurangan.  Distributed quantum computing: a new frontier in distributed systems or science fiction?  SIGACT News, 39(3):77–95, 2008.
  * [12] Danny Dolev, Christoph Lenzen, and Shir Peled.  “tri, tri again”: Finding triangles and small subgraphs in a distributed setting.  In Proceedings of the 26th International Symposium on Distributed Computing (DISC 2012), pages 195–209, 2012.
  * [13] Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman.  Sublinear-time distributed algorithms for detecting small cliques and even cycles.  In Proceedings of the 33rd International Symposium on Distributed Computing (DISC 2019), pages 15:1–15:16, 2019.
  * [14] Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman.  Sublinear-time distributed algorithms for detecting small cliques and even cycles (journal version).  To appear in Distributed Computing, 2021.
  * [15] Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan.  Can quantum communication speed up distributed computation?  In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC 2014), pages 166–175, 2014.
  * [16] Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman.  Possibilities and impossibilities for distributed subgraph detection.  In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), pages 153–162, 2018.
  * [17] Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer.  Networks cannot compute their diameter in sublinear time.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1150–1162, 2012.
  * [18] Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz.  What can be observed locally?  In Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009), pages 243–257, 2009.
  * [19] Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su.  Distributed MST and routing in almost mixing time.  In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 131–140, 2017.
  * [20] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996), pages 212–219, 1996.
  * [21] Taisuke Izumi and François Le Gall.  Quantum distributed algorithm for the all-pairs shortest path problem in the CONGEST-CLIQUE model.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 84–93, 2019.
  * [22] Taisuke Izumi, François Le Gall, and Frédéric Magniez.  Quantum distributed algorithm for triangle finding in the CONGEST model.  In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 23:1–23:13, 2020\.
  * [23] Taisuke Izumi and François Le Gall.  Triangle finding and listing in CONGEST networks.  In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 381–389, 2017.
  * [24] Mark Jerrum and Alistair Sinclair.  Approximating the permanent.  SIAM journal on computing, 18(6):1149–1178, 1989.
  * [25] François Le Gall and Frédéric Magniez.  Sublinear-time quantum computation of the diameter in CONGEST networks.  In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC 2018), pages 337–346, 2018.
  * [26] François Le Gall, Harumichi Nishimura, and Ansis Rosmanis.  Quantum advantage for the LOCAL model in distributed computing.  In Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS 2019), pages 49:1–49:14, 2019.
  * [27] Christoph Lenzen.  Optimal deterministic routing and sorting on the congested clique.  In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC 2013), pages 42–50, 2013.
  * [28] Gopal Pandurangan, Peter Robinson, and Michele Scquizzato.  On the distributed complexity of large-scale graph computations.  In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), pages 405–414, 2018.
  * [29] Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan.  Chernoff-Hoeffding bounds for applications with limited independence.  In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1993), pages 331–340, 1993.
  * [30] Seiichiro Tani, Hirotada Kobayashi, and Keiji Matsumoto.  Exact quantum algorithms for the leader election problem.  ACM Transactions on Computation Theory, 4(1):1:1–1:24, 2012.

##  Appendix A Re-Analysis of Sub-procedures of [4]

For completeness, we repeat the analysis done in [4] for the sub-procedure
which partitions the graph into clusters and has all but a few nodes in most
clusters learn its neighborhood, with different parameters.

######  Lemma A.1 (based on [9], Theorem 1 and optimal cliques).

Let $\delta>0$ such that $m=n^{1+\delta}$. For any $\epsilon\in(0,1)$, and
constant $\gamma\in(0,1)$, there is a constant $\alpha_{\gamma}>0$ dependent
only on $\gamma$, such that a decomposition can be constructed in
$\tilde{O}(n^{\gamma})$ rounds, with high probability, in which the edges of
the graph are partitioned into two sets, $E_{m},E_{r}$, that satisfy the
following conditions:

  1. 1.

Each connected component (cluster) $C$ of $E_{m}$ has conductance
$\Phi(C)\geq(\epsilon/\log{n})^{\alpha_{\gamma}}$, and has average degree at
least $\epsilon n^{\delta}$.

  2. 2.

For any cluster $C$ and node $v\in V_{C}$,
$\deg_{V_{C}}(v)\geq(\epsilon/\log{n})^{\alpha_{\gamma}}\deg_{V\setminus
V_{C}}(v)$.

  3. 3.

$E_{r}\leq\epsilon m$.

######  Proof A.2.

The network runs the expander decomposition of [9] with parameters
$(\epsilon/2,1/\operatorname{\mathrm{polylog}}(n))$ to partition the graph
into sets $E^{\prime}_{m},E^{\prime}_{r}$ such that each connected component
$C$ of $E^{\prime}_{m}$ has conductance
$\Phi(C)\geq(\epsilon/\log{n})^{\alpha_{\gamma}}$, for each $v\in V_{C}$,
$\deg_{V_{C}}(v)\geq(\epsilon/\log{n})^{\alpha_{\gamma}}\deg_{V\setminus
V_{C}}(v)$, and $E^{\prime}_{r}\leq\epsilon m$, in $O(n^{\gamma})$ rounds. The
network marks all edges in $E^{\prime}_{r}$ to be in $E_{r}$. In parallel,
each cluster $C$ computes a BFS spanning tree on the cluster, and counts the
number of edges and nodes in $C$. If the average degree in $C$ is less than
$\epsilon n^{\delta}$, the network adds all edges of $C$ into $E_{r}$. The
total number of edges in clusters of $E^{\prime}_{m}$ with average degree
$2|E_{C}|/|V_{C}|\leq\epsilon n^{\delta}$ is at most $n\cdot(\epsilon
n^{\delta})/2=\epsilon n^{1+\delta}/2=(\epsilon/2)m$. The network marks the
remaining edges as $E_{m}$. We note that indeed
$E_{r}\leq(\epsilon/2+\epsilon/2)m=\epsilon m$. Each remaining cluster $C$
that was not removed to $E_{r}$ has average degree at least $\epsilon
n^{\delta}$, and by the construction of [9], has
$\Phi(C)\geq(\epsilon/\log{n})^{\alpha_{\gamma}}$ and for each $v\in V_{C}$,
$\deg_{V_{C}}(v)\geq(\epsilon/\log{n})^{\alpha_{\gamma}}\deg_{V\setminus
V_{C}}(v)$.

For a cluster $C$, let $N(C)=\\{v\mid\exists_{u\in C}(u,v)\in E^{\prime}\\}$
be the nodes outside the cluster which have a neighbor in $C$,. Let
$\beta=3/5$, $S^{*}_{C}=\\{u\in N(C)\mid\deg_{V_{C}}(u)\leq\deg_{V\setminus
V_{C}}(u)/n^{\beta}\\}$, and let $S_{C}=\\{u\in
V_{C}\mid\deg_{S^{*}_{C}(v)}\geq n^{\beta}\\}$.

######  Lemma A.3 ([4]).

The size of $\bigcup_{C:|V_{C}|\geq n^{3/5}}E(S_{C},S_{C})$ is at most
$\epsilon m$.

######  Proof A.4.

We bound from above the size of $S_{C}$ with regards to $m$:

$2m\geq\sum_{u\in S^{*}_{C}}\deg_{V\setminus V_{C}}(u)\geq n^{\beta}\sum_{u\in
S^{*}_{C}}\deg_{S^{*}_{C}}(u)\geq n^{\beta}\sum_{v\in
S_{C}}\deg_{S^{*}_{C}}(u)\geq n^{2\beta}|S_{C}|.$

Therefore,

$|S_{C}|\leq 2m/n^{2\beta}$ (2)

and

$E(S_{C},S_{C})\leq|S_{C}|^{2}\leq 2m/n^{4\beta}\leq 2n^{2}/n^{4\beta}.$ (3)

As the clusters are vertex-disjoint, there are at most $O(n^{1-\beta})$
clusters with more than $O(n^{\beta})$ vertices, therefore the total number of
edges in $E(S_{C},S_{C})$ is bounded by
$2cmn^{1-\beta}n^{2}/n^{4\beta}=2cmn^{3-5\beta}\leq\epsilon m$.

######  Lemma A.5 ([4]).

In $\tilde{O}(n^{\beta})$ rounds, the network can for each cluster $C$ with
$|V_{C}|\geq n^{\beta}$ partition $E(N(C)\setminus S^{*}_{C},N(C))$ into sets
$\\{E_{v,C}\\}_{v\in C}$, each of size at most $\tilde{O}(n^{\beta}\deg{v})$,
and have each node $v\in V_{C}$ learn the edges of $E_{v,C}$, and in addition,
each node $v$ in $C\setminus S_{C}$ learns the set
$E^{\prime}_{v,C}=E(N(v)\cap S^{*}_{C},N(v)\cap S^{*}_{C})$.

######  Proof A.6.

In parallel for all clusters $C$, each any node in $u\in N(C)\setminus
S^{*}_{C}$ partitions its edges that have both endpoints in $V\setminus V_{C}$
into sets of size $\Theta(n^{\beta})$, and sends each set to a unique neighbor
in $C$. This is possible due to the fact that
$\deg_{V_{C}}(u)\leq\deg_{V\setminus V_{C}}(u)/n^{\beta}$ and $n^{\beta}\geq
n^{1-\beta}$. Following this, each node $v\in C\setminus S_{c}$ sends to each
of its neighbors in $S^{*}_{C}$ the identifiers of its other neighbors in
$S^{*}_{C}$ using $O(n^{\beta})$ rounds. Then, each neighbor replies using
$O(n^{\beta})$ rounds, and sends to which of the nodes sent to it, it has an
edge to. The returned edges are the set $E^{\prime}_{v,C}$

Finally, we cite another lemma which is used in Section 6.

######  Lemma A.7 ([4], Lemma 4.2).

There is a procedure that terminates after $O(n^{\beta})$ rounds network can
determine whether there is a $K_{p}$-copy which at least one of its nodes is
contained in a cluster of size $|V_{C}|\leq n^{\beta}$.