# Quantum algorithms for graph problems with cut queries

Troy Lee Centre for Quantum Software and Information, University of Technology
Sydney. Email<EMAIL_ADDRESS>Miklos Santha CNRS, IRIF, Université de
Paris; Centre for Quantum Technologies and Majulab, National University of
Singapore. Email<EMAIL_ADDRESS>Shengyu Zhang Tencent Quantum
Laboratory. Email<EMAIL_ADDRESS>
###### Abstract

Let $G$ be an $n$-vertex graph with $m$ edges. When asked a subset $S$ of
vertices, a cut query on $G$ returns the number of edges of $G$ that have
exactly one endpoint in $S$. We show that there is a bounded-error quantum
algorithm that determines all connected components of $G$ after making
$O(\log(n)^{6})$ many cut queries. In contrast, it follows from results in
communication complexity that any randomized algorithm even just to decide
whether the graph is connected or not must make at least $\Omega(n/\log(n))$
many cut queries. We further show that with $O(\log(n)^{8})$ many cut queries
a quantum algorithm can with high probability output a spanning forest for
$G$.

En route to proving these results, we design quantum algorithms for learning a
graph using cut queries. We show that a quantum algorithm can learn a graph
with maximum degree $d$ after $O(d\log(n)^{2})$ many cut queries, and can
learn a general graph with $O(\sqrt{m}\log(n)^{3/2})$ many cut queries. These
two upper bounds are tight up to the poly-logarithmic factors, and compare to
$\Omega(dn)$ and $\Omega(m/\log(n))$ lower bounds on the number of cut queries
needed by a randomized algorithm for the same problems, respectively.

The key ingredients in our results are the Bernstein-Vazirani algorithm,
approximate counting with “OR queries”, and learning sparse vectors from inner
products as in compressed sensing.

##  1 Introduction

The _cut_ and _additive_ functions of an $n$-vertex undirected graph $G=(V,E)$
are $c:2^{V}\rightarrow\mathbb{N}$ defined as $c(S)=|E(S,V\setminus S)|$, and
$a:2^{V}\rightarrow\mathbb{N}$ defined as $a(S)=|E(S,S)|$, where $E(S,T)$ is
the set of edges between sets $S,T\subseteq V$. In this paper we study quantum
algorithms for several graph problems when the algorithm has oracle access to
a cut or additive function for the graph. In particular, we look at the
problems of learning all the edges of a graph, determining if the graph is
connected, outputting a spanning tree, and determining properties of the graph
such as if it is bipartite or acyclic.

Motivation to study algorithms with cut or additive query access comes from at
least two different sources. Algorithms with a cut oracle have been studied
for computing the minimum cut of a graph [RSW18, MN20], and the study of graph
algorithms with an additive oracle began in connection with an application to
genomic sequencing [GK98, ABK+04]. We describe the previous works on these
topics and their connection to our results in turn.

Rubinstein et al. [RSW18] give a randomized algorithm that exactly computes
the size of a minimum cut in an $n$-vertex unweighted and undirected graph
with $\widetilde{O}(n)$ many cut queries 111The $\widetilde{O}()$ notation
hides polylogarithmic factors in $n$.. More recently, [MN20] generalizes this
result to also give a randomized $\widetilde{O}(n)$ cut query algorithm to
exactly compute the size of a minimum cut in a weighted and undirected graph.
These results are tight up to the polylogarithmic factors. As observed by
Harvey [Har08], known lower bounds on the communication complexity of
determining if a graph is connected—when divided by $\log(n)$, the number of
bits needed to communicate the answer of a cut query—give lower bounds on the
number of cut queries needed by an algorithm to solve connectivity, and thus
also min-cut. It is known that the deterministic communication complexity of
connectivity is $\Omega(n\log(n))$ [HMT88] and the randomized communication
complexity is $\Omega(n)$ [BFS86], which gives the tightness of the upper
bounds for the cut query complexity claimed above.

Computing the minimum cut with a cut oracle is a special case of the problem
of submodular function minimization with an evaluation oracle. For an
$n$-element set $\Omega$, a function $f:2^{\Omega}\rightarrow\mathbb{R}$ is
submodular if it satisfies $f(S\cap T)+f(S\cup T)\leq f(S)+f(T)$ for all
$S,T\subseteq\Omega$. As the truth table of $f$ is exponentially large in $n$,
submodular functions are often studied assuming access to an _evaluation
oracle_ for $f$, which for any $S\subseteq\Omega$ returns $f(S)$. The
submodular function minimization problem is to compute
$\min_{S\subseteq\Omega}f(S)$. The cut function is a submodular function, thus
computing the minimum cut of a graph with a cut oracle is a special case of
this problem 222The cut function is a symmetric submodular function,
$c(S)=c(V\setminus S)$. For symmetric submodular functions the minimization
problem becomes to find a non-trivial minimizer $\emptyset\subset S\subset
V$.. The ellipsoid method was originally used to show that submodular function
minimization in general can solved in polynomial time with an evaluation
oracle [GLS81, GLS88], and the current record shows that this can be done with
$O(n^{3})$ many calls of the evaluation oracle [Jia20], improving on the bound
of $\widetilde{O}(n^{3})$ by Lee, Sidford, and Wong [LSW15]. If
$M=\max_{A\subseteq V}|f(A)|$ then the current best known weakly polynomial
algorithm makes $O(n^{2}\log(nM))$ many queries [LSW15], and the best pseudo-
polynomial time algorithm makes $O(nM^{3}\log(n))$ many queries [CLSW17]. The
best lower bound on the number of evaluation oracle queries required to find
the minimum value of a submodular function is $\Omega(n)$ for deterministic
algorithms and $\Omega(n/\log(n))$ for randomized algorithms, coming from the
above mentioned communication bounds on determining if a graph is connected.

Quantum algorithms for submodular function minimization have been studied for
approximating $\min_{S\subseteq\Omega}f(S)$ [HRRS19]. For the problem of exact
minimization no quantum algorithm has been considered. Here we study the
problem which is the source of the best known classical lower bounds on
submodular function minimization, the problem of determining if a graph is
connected with a cut oracle. For this special case, we show that there is a
surprisingly efficient quantum algorithm: we give a quantum algorithm that
determines if a graph is connected or not with high probability after
$O(\log(n)^{6})$ many cut queries (Theorem 44). With the same number of
queries the algorithm can output the connected components of the graph, and
can be extended to output a spanning forest after $O(\log(n)^{8})$ many cut
queries (Theorem 51). We leave deciding if minimum cut can also be computed by
a quantum algorithm with a polylogarithmic number of cut queries as a
tantalizing open problem.

Additive queries were originally defined because of an application to genomic
sequencing. One technique for sequencing a genome is to first use shotgun
sequencing to come up with random segments of DNA called _contigs_. To
complete the sequencing of the genome it remains to fill the gaps between the
contigs, and thus also figure out how the contigs are connected to one
another. This can be done through polymerase chain reaction (PCR) techniques.
To do this, one makes primers, short sequences that pair to the end of a
contig. When two contigs are connected by a gap and the primers for each end
of this gap are placed in solution with them, the PCR technique can connect
the contigs by filling in the gap of base pairs between them. If there are $n$
contigs, the process of putting separately all pairs of primers together with
them to find the contigs connected together can take $\binom{n}{2}$ PCR
experiments. This complexity led to the development of multiplex PCR, where
one places many primers together with the contigs at once. The algorithmic
question becomes, what is the best way to add primers to the contigs in order
to fill all gaps between contigs while minimizing the number of multiplex PCR
assays?

Grebinski and Kucherov nicely formalize this algorithmic problem in the
language of graph theory [GK98]. They give several possible models, depending
on exactly what information one assumes to learn from a multiplex PCR assay.
The additive query arises if one assumes that when primers are placed together
with contigs, one can read from the result the number of contigs that were
paired. A weaker model only assumes that when primers are placed together with
contigs, one learns whether or not there is a pairing of contigs. In this
model, when one queries a subset of vertices $S$, one learns whether or not
$|E(S,S)|>0$. We call these _empty subgraph queries_.

In the genomic sequencing application, the primary goal is to learn all the
edges in the graph. Furthermore, for this application the graph is guaranteed
to have degree at most $2$. Grebinski and Kucherov [GK98] show that a
Hamiltonian cycle can be learned by a randomized algorithm with $O(n\log n)$
many empty subgraph queries, and [ABK+04] gives a nonadaptive randomized
algorithm to learn a matching with $O(n\log n)$ many empty subgraph queries.
After these works, the complexity of learning general weighted graphs with
additive queries was also extensively studied [GK00, CK10, Maz10, BM10, BM11].
Notable results are that a graph of maximum degree $d$ can be learned with
$O(dn)$ many additive queries [GK00], and that an $m$-edge graph can be
learned with $O(\frac{m\log n}{\log m})$ many additive queries [CK10, BM11].
Both of these results are tight up to a logarithmic factor in $n$.

We show the additive quantum query complexity of learning a graph with maximum
degree $d$ is $\Theta(d\log(n/d))$ (see Corollary 27 and Corollary 34), and
that a graph with $m$ edges can be learned after $O(\sqrt{m\log n}+\log(n))$
many cut queries (see Corollary 27), which is tight up to logarithmic factors
(see Corollary 33). It is straightforward to show that a cut query can be
simulated by 3 additive queries. Somewhat surprisingly, we show that in
general for weighted graphs simulating an additive query can require
$\Omega(n)$ many cut queries (see Theorem 26). Nonetheless, our algorithms for
learning graphs can also be made to work with cut queries, at the expense of
an additional multiplicative logarithmic factor. The quantum algorithm for
efficiently learning a low degree graph with cut queries is a key subroutine
in our algorithm for connectivity.

###  1.1 Our techniques

We begin by giving an overview of our quantum algorithm for learning a graph
of maximum degree $d$. The high level idea follows the $O(dn)$ classical
algorithm given in [GK00]. The starting point is the basic principle of
compressed sensing: a sparse vector can be learned from its dot product with a
few random vectors. Say $y\in\\{0,1\\}^{n}$ has at most $d$ ones. With high
probability, we can learn $y$ from the values of $x_{1}^{T}y,\dots,x_{k}^{T}y$
for $k=3d\log n$ where each $x_{i}\in\\{0,1\\}^{n}$ is chosen randomly (see
Lemma 1). Moreover, this algorithm is non-adaptive, thus given a matrix
$Y\in\\{0,1\\}^{n\times n}$ where each column has at most $d$ ones, we can
learn $Y$ with high probability from the product $XY$ where
$X\in\\{0,1\\}^{k\times n}$ is chosen randomly with $k=3d\log n$. We can apply
this principle to learn the adjacency matrix $A_{G}$ of a graph $G$ of maximum
degree $d$.

Classically, a single product $x^{T}A_{G}$ can be computed with $O(n)$ cut
queries. We will show how to use the Bernstein-Vazirani algorithm [BV97], to
compute $x^{T}A_{G}$ with a constant number of cut queries, provided the graph
$G$ is bipartite. We can then apply this to learn a general graph $G$ as the
complete graph can be covered by $O(\log n)$ many complete bipartite graphs.
This leads to an overall complexity of $\widetilde{O}(d)$ many cut queries.

These results can be phrased more generally in terms of learning an $m$-by-$n$
matrix $A$ when given the ability to query $x^{T}Ay$ for Boolean vectors
$x\in\\{0,1\\}^{m},y\in\\{0,1\\}^{n}$. We call such queries _matrix cut
queries_ , and they provide a very clean way of formulating our results 333We
term these matrix cut queries because of the relation to the cut norm of a
matrix $A$, defined as $\max_{x\in\\{0,1\\}^{m},y\in\\{0,1\\}^{n}}|x^{T}Ay|$.
The cut norm played a crucial role in the matrix decomposition results of
[FK99] used for efficient approximation algorithms for maximum cut and other
graph problems. Such queries are also used in the classical learning results
[GK00, Maz10, BM11], and we find it useful to make them explicit here.

Our algorithm for connectivity is a contraction based algorithm. If we find an
edge between vertices $u$ and $v$, we can merge $u$ and $v$ into a single
vertex without changing the connectivity of the graph. More generally, if we
know that a set $S_{1}$ of vertices is connected, and a disjoint set $S_{2}$
of vertices is connected, and we learn that there is an edge between a vertex
in $S_{1}$ and a vertex in $S_{2}$, we can merge $S_{1}$ and $S_{2}$ without
changing the connectivity of the graph.

Our algorithm for connectivity proceeds in rounds, and maintains the invariant
of having a partition of the vertex set $V$ into sets $S_{1},\ldots,S_{k}$,
each of which is known to be connected. We call such sets $S_{i}$
supervertices, and the number of $S_{j}$ such that there is an edge between a
vertex in $S_{i}$ and a vertex in $S_{j}$ the _superdegree_ of $S_{i}$. A
round proceeds by first in parallel approximating the superdegree of each
$S_{i}$. For this we use ideas originating with Stockmeyer [Sto83] for
approximately counting the number of ones in a vector $y\in\\{0,1\\}^{n}$ with
OR queries, queries that for a subset $S\subseteq\\{1,\ldots,n\\}$ answer $1$
iff there is an $i\in S$ with $y_{i}=1$. We show that we can efficiently
simulate the OR queries needed in the context of approximating the superdegree
by cut queries. For supervertices whose superdegree is below a threshold—taken
to be $\Theta(\log(n)^{2})$—we learn all of their superneighbors with
polylogarithmically many cut queries using our techniques for learning a
matrix with sparse columns. To take care of the supervertices with superdegree
above the threshold, we randomly sample $k/2$ many of the $S_{j}$. With high
probability every high superdegree supervertex will be connected to at least
one $S_{j}$ in the sample set, and moreover we show that we can learn edges
witnessing this fact with polylogarithmically many cut queries. We then
contract the supervertices according to all the edges learned in the round,
and show that we either learn that the graph is disconnected or arrive at a
new partition of $V$ into at most $k/2$ many connected sets. In this way, the
algorithm terminates in at most $O(\log n)$ many rounds, and as each round
uses polylogarithmically many cut queries we arrive at the polylogarithmic
complexity.

###  1.2 Related work

As far as we are aware, ours is the first work studying quantum algorithms
using a cut or additive query oracle. Quantum algorithms for graph problems
typically use the adjacency matrix or adjacency list input model. Early work
[DHHM06, SYZ04, Zha05] gives tight bounds for many graph problems in these
models. For example, it is shown in [DHHM06] that the quantum query complexity
of connectivity is $\Theta(n^{3/2})$ in the adjacency matrix model and
$\Theta(n)$ in the adjacency list model, the quantum query complexity of
minimum spanning tree is $\Theta(n^{3/2})$ in the adjacency matrix model and
$\Theta(\sqrt{nm})$ in the adjacency list model, for a graph with $m$ edges.
Focusing on the adjacency matrix model, the quantum query complexity of
Bipartiteness and of Graph Matching is $\Omega(n^{3/2})$ [Zha05], and that of
Scorpion graph is $\tilde{\Theta}(\sqrt{n})$ , which is the lowest possible
quantum query complexity for total graph properties [SYZ04]. Also see [MSS07,
Bel12, JKM13, LMS17, Gal14] for triangle finding, [CK12] for general graph
minor-closed graph properties, and [BCG+20] for discussions on partial graph
properties.

In the time complexity model, recent work of Apers and de Wolf [AdW19] shows
that a cut of size at most $(1+\epsilon)$-times that of the minimum cut can be
found in time $\widetilde{O}(\sqrt{mn}/\epsilon)$ given adjacency list access
to the graph. Their work more generally shows that an $\epsilon$-cut
sparsifier of a graph with $\widetilde{O}(n/\epsilon^{2})$ many edges can be
found in time $\widetilde{O}(\sqrt{mn}/\epsilon)$. Originally defined in
[BK96], an $\epsilon$-cut sparsifier of a graph $G$ is a reweighted subgraph
$H$ such that the value of every cut in $H$ is a multiplicative
$(1+\epsilon)$-approximation of the corresponding cut value in $G$.

In the classical setting, a recent work [RWZ20] studies a generalization of
matrix cut queries where for a fixed field $\mathbb{F}$ one can access an
input matrix $A\in\mathbb{F}^{m\times n}$ through queries of the form
$x^{T}Ay$ for $x\in\mathbb{F}^{m},y\in\mathbb{F}^{n}$. They examine the
complexity of an assortment of problems from graph theory, linear algebra, and
statistics in this model.

###  1.3 Organization

The rest of the paper is organized as follows. In Section 2, we set up the
model and notation, and give some algorithmic ingredients such as degree
estimation by OR queries, and a quantum primitive of vector learning that is
used a number of times in later sections. In Section 3 and Section 4 we
introduce several oracles for accessing a matrix or a graph, and discuss their
relative powers. Some intermediate results built on these oracles will be
presented, which lead to the cut oracle algorithms in the next sections:
Section 5 for computing connected components by $O(\log(n)^{6})$ queries, and
Section 6 for computing spanning forest by $O(\log(n)^{8})$ cut queries. Two
applications of the latter algorithm will also be given, which test if a graph
is bipartite or acyclic, also with $O(\log(n)^{8})$ many cut queries. The
paper concludes with several open problems.

##  2 Preliminaries and primitives

For a positive integer $M$, we denote $\\{0,1,2,\ldots,M-1\\}$ by $[M]$. For
two vectors $X,Y\in[M]^{k}$, we denote their dot product over the integers by
$X\cdot Y=\sum_{i=1}^{k}X_{i}Y_{i}.$ For a set $S\subseteq\\{1,\ldots,M\\}$ we
denote the complement of $S$ by $\bar{S}$. For a set $U$, we let
$\tilde{U}=\\{\\{u\\}:u\in U\\}$. For a string $x\in\\{0,1\\}^{n}$ we use
$|x|$ for the Hamming weight of $x$, i.e. the number of ones. Let
$\mathrm{OR}_{n}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ denote the OR function,
i.e. the function such that $\mathrm{OR}_{n}(x)=1$ iff $|x|>0$. Let
$\mathrm{MAJ}_{n}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ denote the Majority
function, i.e. the function such that $\mathrm{MAJ}_{n}(x)=1$ iff
$|x|\geq\left\lceil n/2\right\rceil$. When the input length is clear from
context we will drop the subscript.

In pseudocode for our algorithms we will use some Matlab-like notation. We use
$\mathrm{zeros}(k,\ell)$ and $\mathrm{ones}(k,\ell)$ to denote the
$k$-by-$\ell$ all zeros matrix and all ones matrix, respectively. For $M$ a
$k$-by-$\ell$ matrix and
$H\subseteq\\{1,\ldots,k\\},R\subseteq\\{1,\ldots,\ell\\}$ we use $M(H,R)$ to
refer to the $|H|$-by-$|R|$ submatrix of $M$ given by selecting the rows of
$M$ in $H$ and columns of $M$ in $R$. We will further use the shorthand
$M(i\colon j,k\colon\ell)$ for $M(H,R)$ where $H=\\{i,i+1,\ldots,j\\}$ and
$R=\\{k,k+1,\ldots,\ell\\}$. To denote the $i^{th}$ column of $M$ we will use
$M(:,i)$. Similarly for a vector $x\in\mathbb{R}^{k}$, we use
$x(H)\in\mathbb{R}^{|H|}$ to denote the vector formed by selecting the
coordinates in $H$. For column vectors
$x\in\mathbb{R}^{k},y\in\mathbb{R}^{\ell}$ we use
$[x;y]\in\mathbb{R}^{k+\ell}$ for the column vector formed by vertically
concatenating them. For a vector $x\in\mathbb{R}^{k}$ and $d\leq k$, we say
that $x$ is $d$-sparse if at most $d$ coordinates in $x$ are nonzero. We use
$\ell_{0}(x)$ to denote the sparsity, i.e. the number of nonzero entries, of
vector $x$.

We will frequently encounter the situation where we have a set
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and take a subset
$H\subseteq\mathcal{S}$ where $H=\\{S_{i_{1}},\ldots,S_{i_{t}}\\}$. We use
$\mathrm{ind}(H)=\\{i_{1},\ldots,i_{t}\\}$ to return the indices of the
elements in $H$.

######  Lemma 1.

Let $r,M,d$ be positive integers with $M\geq 2$ and $d\leq r/2$. Let $N\leq
d\binom{r}{d}M^{d}$ be the number of $d$-sparse strings in $[M]^{r}$. Let $A$
be an $N$-by-$r$ matrix whose rows are all the $d$-sparse strings in
$[M]^{r}$. Let $R$ be a random $r$-by-$q$ Boolean matrix, with each entry
chosen independently and uniformly from $\\{0,1\\}$. If $q=\left\lceil
2d\log(eMr/d)+2\log(d)+\log(1/\delta)\right\rceil$ then $AR\bmod M$ will have
distinct rows with probability at least $1-\delta$.

###### Proof.

Let $A_{i},A_{j}$ be two different rows of $A$. Then for a random vector
$z\in\\{0,1\\}^{r}$, $\Pr_{z}[A_{i}z\bmod M=A_{j}z\bmod M]\leq 1/2$. Therefore
$\Pr_{R}[A_{i}R\bmod M=A_{j}R\bmod M]\leq 1/2^{q}$. The result follows by a
union bound over the $\binom{N}{2}$ pairs of distinct rows. ∎

######  Definition 2 (OR query).

For $x\in\\{0,1\\}^{\ell}$ and $S\subseteq\\{1,\ldots,\ell\\}$ an OR query
$\mathrm{OR}(x,S)$ returns $\vee_{i\in S}x_{i}$. For strings
$x^{(1)},\ldots,x^{(k)}\in\\{0,1\\}^{\ell}$ and a subset
$S\subseteq\\{1,\ldots,\ell\\}$, a $k$-OR query returns the string
$a\in\\{0,1\\}^{k}$ where $a_{i}=\mathrm{OR}(x^{i},S)$.

The problem of estimating the Hamming weight of a string $x$ using OR queries
was considered in the seminal work of Stockmeyer [Sto83]. We recount his basic
analysis here, modifying it for our application of using $k$-OR queries to
estimate the Hamming weight of $x^{(1)},\ldots,x^{(k)}$ in parallel.

######  Fact 3.

For all $x\geq 1$

$\left(1-\frac{1}{x}\right)^{x}<\frac{1}{e}<\left(1-\frac{1}{x}\right)^{x-1}$

######  Definition 4.

Let $x\in\\{0,1\\}^{\ell}$. An $r$-out-of-$\ell$ sample consists of uniformly
at random choosing $r$ many elements of $\\{1,\ldots,\ell\\}$ with
replacement. An $r$-test consists of taking an $r$-out-of-$\ell$ sample $S$
and querying $\mathrm{OR}(x,S)$. When $\mathrm{OR}(x,S)=1$, we say that the
$r$-test $S$ succeeds.

######  Lemma 5.

Let $x\in\\{0,1\\}^{\ell}$ and suppose that $|x|=t$. The probability that an
$r$-test $S$ succeeds is

$\Pr_{S}[\mathrm{OR}(x,S)=1]=1-\left(1-\frac{t}{\ell}\right)^{r}\enspace,$

where the probability is taken over the choice of an $r$-out-of-$\ell$ sample
$S$. In particular,

$1-\exp\left(-\frac{rt}{\ell}\right)<\Pr_{S}[\mathrm{OR}(x,S)=1]<1-\exp\left(-\frac{rt}{\ell-t}\right)$

###### Proof.

As $S$ is chosen with replacement, the probability that any element $i\in S$
satisfies $x_{i}=1$ is exactly $\frac{t}{\ell}$. The first statement follows
accordingly. The second statement follows by applying 3 to the first
statement. ∎

Algorithm 1 Approximate Count$(\delta)$

Input: $k$-OR oracle for strings $x^{(1)},\ldots,x^{(k)}\in\\{0,1\\}^{\ell}$,
error bound $\delta$
Output: A vector $b\in\mathbb{R}^{k}$ that is a good estimate of
$(|x^{(1)}|,\ldots,|x^{(k)}|)$ with probability $1-\delta$.

1:$a\leftarrow
200\left\lceil\log\left(\frac{k(\left\lceil\log\ell\right\rceil+1)}{\delta}\right)\right\rceil$

2:for $j=0$ to $\left\lceil\log\ell\right\rceil$ do

3: for $q=1$ to $a$ do

4: $S_{q}\leftarrow$ randomly choose $\min(2^{j},\ell)$ many elements from
$\\{1,\ldots,\ell\\}$ with replacement

5:
$\mathrm{ans}_{q}\leftarrow(\mathrm{OR}(x^{(1)},S_{q}),\ldots,\mathrm{OR}(x^{(k)},S_{q}))$

6: end for

7: for $i=1$ to $k$ do

8:
$B(i,j)\leftarrow\mathrm{MAJ}(\mathrm{ans}_{1}(i),\ldots,\mathrm{ans}_{a}(i))$

9: end for

10:end for

11:for $i=1$ to $k$ do

12: $s\leftarrow\operatorname*{argmin}_{j}\\{B(i,j)=1\\}$

13: $b(i)\leftarrow\frac{\ell}{2^{s}}$

14:end for

######  Definition 6 (Good estimate).

We say that $b\in\mathbb{R}^{k}$ is a _good estimate_ of $c\in\mathbb{R}^{k}$
if $b(i)/4\leq c(i)\leq 2b(i)$ for all $i\in\\{1,\ldots,k\\}$.

Next we see how to use $k$-OR queries to estimate the Hamming weights of $k$
given strings.

######  Lemma 7.

Let $x^{(1)},\ldots,x^{(k)}\in\\{0,1\\}^{\ell}$. Taking
$a=200\left\lceil\log\left(\frac{k(\left\lceil\log\ell\right\rceil+1)}{\delta}\right)\right\rceil$,
Algorithm 1 outputs a vector $b$ that is a good estimate of
$(|x^{(1)}|,\ldots,|x^{(k)}|)$ with probability at least $1-\delta$ after
making
$O\left((\log(\ell)+1)\log\left(\frac{k(\log(\ell)+1)}{\delta}\right)\right)$
many $k$-OR queries.

###### Proof.

First we argue about the complexity. There are
$\left\lceil\log\ell\right\rceil+1$ iterations of the outer for loop, and
inside the loop we make $a$ many $k$-OR queries. Thus the total number of
$k$-OR queries is

$O(a(\log(\ell)+1))=O\left((\log(\ell)+1)\log\left(\frac{k(\log(\ell)+1)}{\delta}\right)\right)\enspace.$

Now we argue about the error probability. Fix some $x^{(i)}$, which will
henceforth be called $x$. Say the estimate the algorithm gives for $|x|$ is
$\alpha$. We will upper bound the probability that $\alpha$ is a bad estimate
for $|x|$, and then use a union bound over the $k$ many strings to get the
final result.

Suppose that $r=2^{j}$ is such that $r\geq\ell/|x|$. Then if $S$ is a $r$-out-
of-$\ell$ sample, by Lemma 5

$\Pr_{S}[\mathrm{OR}(x,S)=1]>1-\exp\left(-\frac{r|x|}{\ell}\right)\geq
1-\frac{1}{e}>0.6\enspace.$

Thus by a Chernoff bound, the probability that the majority of $a$ many
$r$-tests is $0$ is at most $\exp(-a/200)$. As the algorithm must perform an
$r$-test for an $r$ satisfying $\ell/|x|\leq r\leq 2\ell/|x|$, this means our
estimate $\alpha$ will satisfy $|x|\leq 2\alpha$, except with probability at
most $\exp(-a/200)$.

To bound the probability that our estimate is too large, we first need to
treat the special case where $|x|\geq\ell/2$. In this case, the probability
that the majority of $a$ many $2$-tests is $1$ is at least $1-\exp(-a/200)$.
The algorithm is therefore correct in this case with at least this probability
as it outputs a valid answer if either a majority of $1$-tests or a $2$-tests
succeeds.

For the remainder of the proof, therefore, we assume that $|x|<\ell/2$.
Suppose that $r=2^{j}$ is such that $\ell/r>4|x|$. Then if $S$ is an $r$-out-
of-$\ell$ sample, by Lemma 5

$\Pr_{S}[\mathrm{OR}(x,S)=1]<1-\exp\left(-\frac{r|x|}{\ell-|x|}\right)\leq
1-\exp\left(-\frac{2r|x|}{\ell}\right)\leq 1-\exp(-1/2)\leq 0.4\enspace.$

Thus by a Chernoff bound, the probability that the majority of $a$ many
$r$-tests is $1$ is at most $\exp(-a/200)$. By a union bound, the probability
that an $r$-test will be $1$ for any $r=2^{j}$ with $r<\ell/(4|x|)$ is at most
$\left\lceil\log\ell\right\rceil\exp(-a/200)$. Thus, our estimate $\alpha$
will satisfy $\alpha/4\leq|x|$ except with probability
$\left\lceil\log\ell\right\rceil\exp(-a/200)$. Thus by a union bound, overall
we will produce an estimate $\alpha$ satisfying $\alpha/4\leq|x|\leq 2\alpha$
except with probability $(\left\lceil\log\ell\right\rceil+1)\exp(-a/200)$.

Finally, by a union bound over the $k$ many strings the total failure
probability will be at most
$k(\left\lceil\log\ell\right\rceil+1)\exp(-a/200)$, giving the lemma. ∎

######  Lemma 8.

Let $x^{(1)},\ldots,x^{(k)}\in\\{0,1\\}^{\ell}$ be such that
$t/8\leq|x^{(i)}|\leq 2t$ for all $i\in\\{1,\ldots,k\\}$. For $\delta>0$,
sample with replacement $\frac{8\ell\ln(k/\delta)}{t}$ elements of
$\\{1,\ldots,\ell\\}$, and call the resulting set $R$. Then

  * •

$\Pr_{R}[\exists i\in\\{1,\ldots,k\\}:|x^{(i)}(R)|=0]\leq\delta$,

  * •

$\Pr_{R}[\exists
i\in\\{1,\ldots,k\\}:|x^{(i)}(R)|>64\ln(k/\delta)]\leq\delta$.

###### Proof.

Let $x\in\\{0,1\\}^{\ell}$ with $t/8\leq|x|\leq 2t$. The probability that
$|x(R)|=0$ is at most $\delta/k$ by Lemma 5. Thus the first item holds by a
union bound over the $k$ many strings $x^{(1)},\ldots,x^{(k)}$.

For the second item, note $\ln(k/\delta)\leq\mathbb{E}_{R}[|x(R)|]\leq
16\ln(k/\delta)$. By a Chernoff bound, the probability that $|x(R)|$ is a
factor $c$ larger than its expectation is at most
$\exp(-(c-1)\ln(k/\delta)/3)$. Thus taking $c=4$ the probability that
$|x(R)|>64\ln(k/\delta)$ is at most $\delta/k$. The second item then holds by
a union bound over the $k$ many strings $x^{(1)},\ldots,x^{(k)}$. ∎

Next we give our quantum primitive algorithm for learning a vector from subset
sums. Note that different than state learning in many previous work, here we
aim to learn all entries of the vector precisely and correctly. This algorithm
will be repeatedly used in various forms in later sections.

######  Lemma 9.

Let $x\in[M]^{k}$ and suppose we have an oracle that for any subset
$S\subseteq[k]$ returns $\sum_{i\in S}x_{i}\bmod M$. Then there is a quantum
algorithm which learns $x$ with $m=\left\lceil\log(M)\right\rceil$ queries
without any error.

###### Proof.

We can represent all the elements of $[M]$ using $m$ bits. We first describe
how we can use the oracle to compute $t\cdot x\bmod M$ for any $t\in[M]^{k}$.
Let $t=(t_{1},\ldots,t_{k})$ and let $t_{i}=\sum_{j=0}^{m-1}2^{j}t_{i}(j)$,
where $t_{i}(j)\in\\{0,1\\}$. Then

$t\cdot x\bmod M=\sum_{j=0}^{m-1}2^{j}(t(j)\cdot x\bmod M)\bmod M$

where $t(j)=(t_{1}(j),t_{2}(j),\ldots,t_{k}(j))\in\\{0,1\\}^{k}$. Now
$t(j)\cdot x\bmod M$ can be computed with one call to the oracle, thus $t\cdot
x\bmod M$ can be computed with $m$ calls to the oracle.

With a quantum algorithm we can do this in superposition over all $t$.
Combining this with the phase kickback trick allows us to compute the inverse
quantum Fourier transform of $x$ over $(\mathbb{Z}_{M})^{k}$. Similarly to the
Bernstein-Vazirani algorithm, we can then learn $x$ by applying the quantum
Fourier transform.

More precisely, we will work with two quantum registers. In the first register
we are computing over the group $(\mathbb{Z}_{M})^{k}$, and in the second
register over $\mathbb{Z}_{M}$. We will use in the second register the
auxiliary state

$|\xi_{M}\rangle=\frac{1}{\sqrt{M}}\sum_{j=0}^{M-1}\omega_{M}^{j}|j\rangle,$

where $\omega_{M}$ is a primitive $M$th root of the unity. In the first
register we create the uniform superposition, therefore we start with the
state

$\frac{1}{\sqrt{M^{k}}}\sum_{t\in[M]^{k}}|t\rangle|\xi_{M}\rangle.$

With $m$ queries to the oracle we compute $t\cdot x\bmod M$ that we add to the
second register, creating

$\frac{1}{\sqrt{M^{k}}}\sum_{t\in[M]^{k}}\omega_{M}^{-t\cdot
x}|t\rangle|\xi_{M}\rangle.$

Applying the quantum Fourier transform over $(\mathbb{Z}_{M})^{k}$, we can
find in the first register $x.$ Overall the quantum algorithm uses $m$
queries. ∎

##  3 Learning a matrix

Let $n$ be a positive integer, and $V$ an ordered set of size $n$. For a
subset $S$ of $V$, we denote by $\chi_{S}\in\\{0,1\\}^{n}$ is the
characteristic vector of $S$.

######  Definition 10 (Matrix cut oracle).

Given a matrix $A\in\mathbb{N}^{k\times\ell},$ the matrix cut oracle for $A$
is the function
$m_{A}:\\{0,1\\}^{k}\times\\{0,1\\}^{\ell}\rightarrow\mathbb{N}$ satisfying
$m_{A}(x,y)=x^{T}Ay$.

######  Lemma 11.

Let $\alpha,M\in\mathbb{N}$ and $A\in[\alpha]^{k\times\ell}$ be a matrix.
There is a quantum algorithm making $\left\lceil\log(M)\right\rceil$ many
matrix cut queries to $A$ that perfectly computes $(Ay)\bmod M$ for any
$y\in\\{0,1\\}^{\ell}$.

###### Proof.

Let $S\subseteq\\{1,\ldots,k\\}$. For any $y\in\\{0,1\\}^{\ell}$ we have
$\sum_{i\in S}(Ay)_{i}\bmod M=\chi_{S}^{T}Ay\bmod M$, thus we can compute
$\sum_{i\in S}(Ay)_{i}\bmod M$ with one matrix cut query. The result then
follows from Lemma 9. ∎

######  Corollary 12.

Let $A\in[M]^{k\times\ell}$. There is a quantum algorithm that perfectly
learns $A$ after $\min\\{k,\ell\\}\cdot\left\lceil\log(M)\right\rceil$ many
matrix cut queries.

###### Proof.

If $\ell\leq k$ define $B=A$, otherwise let $B=A^{T}$. Let
$m=\min\\{k,\ell\\}$ be the number of columns in $B$. For each standard basis
vector $e_{1},\ldots,e_{m}$, we can learn $Be_{i}=Be_{i}\bmod M$ with
$\left\lceil\log(M)\right\rceil$ matrix cut queries by Lemma 11. This tells us
the $i^{th}$ column of $B$. Thus we can learn $B$ entirely with
$m\left\lceil\log(M)\right\rceil$ many matrix cut queries. ∎

######  Lemma 13.

Let $A\in[M]^{k\times\ell}$ be a matrix with $d$-sparse rows. There is a
quantum algorithm that learns $A$ with probability at least $1-\delta$ after
making
$(4d\left\lceil\log(M\ell/d)\right\rceil+\left\lceil\log(1/\delta)\right\rceil)\left\lceil\log(M)\right\rceil$
many matrix cut queries.

###### Proof.

If $d\geq\ell/2$ then we use Corollary 12 to learn $A$ perfectly with
$\ell\left\lceil\log(M)\right\rceil\leq
4d\left\lceil\log(M\ell/d)\right\rceil$ many matrix cut queries.

Now assume $d<\ell/2$. By Lemma 1, taking
$q=4d\left\lceil\log(M\ell/d)\right\rceil+\left\lceil\log(1/\delta)\right\rceil$
and computing $AZ\bmod M$ for a random $\ell$-by-$q$ Boolean matrix $Z$ allows
us to learn $A$ with probability at least $1-\delta$. By Lemma 11 we can
compute $AZ_{i}\bmod M$ with $\left\lceil\log(M)\right\rceil$ matrix cut
queries, where $Z_{i}$ the $i^{th}$ column of $Z$. Thus we can learn $A$ after
$q\left\lceil\log(M)\right\rceil$ many matrix cut queries. ∎

######  Definition 14 (degree sequence).

Let $A\in[M]^{k\times\ell}$ be a matrix. The degree sequence of $A$ is the
vector $x\in\mathbb{N}^{k}$ such that $x_{i}$ is the number of nonzero entries
in the $i^{th}$ row of $A$, for all $i=1,\ldots,k$.

######  Lemma 15 (Approximate degree sequence).

Let $M,k,\ell$ be positive integers and $A\in[M]^{k\times\ell}$ be a matrix.
There is a quantum algorithm, making $O(\log(\ell
M)(\log(\ell)+1)\log(\frac{k(\log(\ell)+1)}{\delta}))$ many matrix cut
queries, that with probability at least $1-\delta$ outputs
$\vec{g}\in\mathbb{R}^{k}$ that is a good estimate of the degree sequence of
$A$. If $M=2$ then there is a quantum algorithm that outputs the degree
sequence of $A$ perfectly after $\left\lceil\log(\ell+1)\right\rceil$ many
matrix cut queries.

###### Proof.

Define $x^{(1)},\ldots,x^{(k)}\in\\{0,1\\}^{\ell}$ by $x^{(i)}(j)=1$ if
$A(i,j)>0$ and $x^{(i)}(j)=0$ otherwise. The degree sequence of $A$ is then
$(|x^{(1)}|,\ldots,|x^{(k)}|)$. We apply Lemma 7 to approximate
$(|x^{(1)}|,\ldots,|x^{(k)}|)$ and therefore the degree sequence of $A$. To do
this, for a subset $S\subseteq\\{1,\ldots,\ell\\}$, we need to serve the
$k$-OR query $(\mathrm{OR}(x^{(1)},S),\ldots,\mathrm{OR}(x^{(k)},S))$. Let
$\chi_{S}$ be the characteristic vector of $S$. As the entries of $A$ are at
most $M-1$ in magnitude, the entries of $A\chi_{S}$ are at most $\ell(M-1)$.
Therefore $A\chi_{S}=A\chi_{S}\bmod(\ell(M-1)+1)$. We can thus compute
$A\chi_{S}$ with $\left\lceil\log((\ell(M-1)+1)\right\rceil$ many queries by
Lemma 11. Computing $A\chi_{S}$ suffices to serve the $k$-OR query since
$(\mathrm{OR}(x^{(1)},S),\ldots,\mathrm{OR}(x^{(k)},S))=(\min\\{(A\chi_{S})_{1},1\\},\ldots,\min\\{(A\chi_{S})_{k},1\\})$.
Thus by Lemma 7 we can output a good estimate of the degree sequence of $A$
with probability at least $1-\delta$ after $O\left(\log(\ell
M)(\log(\ell)+1)\log\left(\frac{k(\log(\ell)+1)}{\delta}\right)\right)$ many
matrix cut queries.

For the case $M=2$, note that the degree sequence of $A$ is the vector
$A\vec{1}$, where $\vec{1}$ is the vector of all ones. As the entries of
$A\vec{1}$ are at most $\ell$ by Lemma 11 we can compute the degree sequence
with $\left\lceil\log(\ell+1)\right\rceil$ many matrix cut queries. ∎

######  Theorem 16.

Let $A\in[M]^{k\times\ell}$ be a matrix with $m$ many nonzero entries. There
is a quantum algorithm to learn $A$ with probability at least $1-\delta$ after
making

$O\left(\sqrt{m\log(M\ell)}\log(M)+\log(\ell
M)(\log(\ell)+1)\log\left(\frac{k(\log(\ell)+1)}{\delta}\right)\right)$

many matrix cut queries. When $M=2$, a better bound of
$O(\sqrt{m\log(\ell)}+\log(\ell+1)+\log(1/\delta))$ many matrix cut queries
holds.

###### Proof.

First we use Lemma 15 to compute $g\in\mathbb{R}^{k}$ which is a good
approximation of the degree sequence of $A$ except with probability
$\delta/2$. This takes

$O\left(\log(\ell
M)(\log(\ell)+1)\log\left(\frac{k(\log(\ell)+1)}{\delta}\right)\right)$

many queries. If $M=2$ then we can exactly compute the degree sequence of $A$
with $\left\lceil\log(\ell+1)\right\rceil$ many matrix cut queries. We now
assume that $g$ is a good approximation and add $\delta/2$ to our total error
bound.

Let $d\in\mathbb{N}$ be a degree threshold that will be chosen later, and
define $L=\\{i:g(i)\leq d\\}$ and $H=\\{i:g(i)>d\\}$. As $g$ is a good
approximation of the degree sequence, rows whose indices are in $L$ have at
most $2d$ nonzero entries. We use Lemma 13 to learn the submatrix
$A(L,1\colon\ell)$ with probability at least $1-\delta/2$ with
$O((d\log(M\ell/d)+\log(1/\delta))\log(M))$ many matrix cut queries.

For each $i\in H$, the $i^{th}$ row of $A$ must have at least $d/4$ many
nonzero entries, as $g$ is a good approximation of the degree sequence of $A$.
Thus $|H|\leq 4m/d$. By Corollary 12 we can learn the submatrix
$A(H,1\colon\ell)$ with $4m\left\lceil\log(M)\right\rceil/d$ many matrix cut
queries.

Setting $d=\sqrt{\frac{m}{\log(M\ell)}}$ the total number of queries becomes

$O\left(\sqrt{m\log(M\ell)}\log(M)+\log(\ell
M)(\log(\ell)+1)\log\left(\frac{k(\log(\ell)+1)}{\delta}\right)\right)\enspace.$

In the case $M=2$, the number of queries becomes
$O(\sqrt{m\log(\ell)}+\log(\ell+1)+\log(1/\delta))$. ∎

##  4 Learning graphs

A weighted graph is a couple $G=(V,w)$, where $V$ is the set of vertices,
$V^{(2)}$ is the set of subsets of $V$ with cardinality 2, and
$w:V^{(2)}\rightarrow\mathbb{N}$ is the weight function. We assume that we
have a total ordering $v_{1}<v_{2}<\cdots<v_{|V|}$ on the elements of $V$. The
set of edges is defined as $E=\\{e\in V^{(2)}:w(e)>0\\}$, therefore weighted
graphs are undirected and without self-loops. We can also think of them as
multi-graphs, where the number of edges between vertices $u$ and $v$ is
$w(\\{u,v\\})$. When the range of $w$ is $\\{0,1\\}$ we will call a weighted
graph a simple graph, or just a graph and denote it by $G=(V,E)$. If $G$ is a
weighted graph on $n$ vertices, the _adjacency matrix_ of $G$ is an $n$-by-$n$
matrix $A_{G}$ with zeros on the diagonal and
$A_{G}(i,j)=w(\\{v_{i},v_{j}\\})$, for $i\neq j$. Observe that $A_{G}$ is a
symmetric matrix.

For an edge $e=\\{u,v\\}$, we say that $u$ and $v$ are the endpoints of $e$.
The degree $\deg(v)$ of a vertex $v$ is the number of edges for which $v$ is
an endpoint. For $S,T\subseteq V$ sets of vertices, we denote by $E(S,T)$ the
set of edges with one endpoint in $S$ and the other endpoint in $T$. (More
precisely, $E(S,T)=\\{e\in E:|e\cap(S\cup T)|=2,|e\cap S|\geq 1,|e\cap T|\geq
1\\}$.) We extend the weight function $w$ to sets of vertices $S,T\subseteq V$
by $w(S,T)=\sum_{e\in E(S,T)}w(e)$.

A bipartite weighted graph is a triple $G=(V_{1},V_{2},w)$, where
$V_{1}=\\{v_{1},\ldots,v_{k}\\}$ and $V_{2}=\\{v_{k+1},\ldots,v_{k+\ell}\\}$
are the disjoint sets of respectively left and right vertices, and
$w:V_{1}\times V_{2}\rightarrow\mathbb{N}$ is the bipartite weight function. A
bipartite graph $G=(V_{1},V_{2},w)$ can of course also be viewed as a graph
$G^{\prime}=(V^{\prime},w^{\prime})$ with vertex set $V=V_{1}\cup V_{2}$,
where $V_{1}$ and $V_{2}$ are independent sets, and weight function
$w^{\prime}$ over $V^{(2)}$, where

$w^{\prime}(\\{v_{i},v_{j}\\})=\begin{cases}0,&\mbox{ if }1\leq i,j\leq
k\mbox{ or }k+1\leq i,j\leq k+\ell,\\\
w(v_{\min\\{i,j\\}},v_{\max\\{i,j\\}}),&\mbox{ otherwise }.\end{cases}$

Consistently with the general case, for $V^{\prime}_{1}\subseteq V_{1}$ and
$V^{\prime}_{2}\subseteq V_{2}$, we extend $w$ as
$w(V^{\prime}_{1},V^{\prime}_{2})=\sum_{u\in V^{\prime}_{1},v\in
V^{\prime}_{2}}w(u,v).$ The set of edges is defined as $E=\\{e\in V_{1}\times
V_{2}:w(e)>0\\}$.

The biadjacency matrix of $G$ is a $k\times\ell$ matrix $B_{G}$ where
$B_{G}(i,j-k)=w(\\{v_{i},v_{j}\\})$ for $1\leq i\leq k,k+1\leq j\leq k+\ell$.
Similarly to the bipartite weight function, the biadjacency matrix $B_{G}$ is
a condensed description of the $(k+\ell)\times(k+\ell)$ adjacency matrix
$A_{G}$ of $G$, where $A_{G}(i,j)={w^{\prime}}(\\{v_{i},v_{j}\\})$, for $i\neq
j$.

We will look at four different oracles for accessing a graph, the matrix cut
oracle, the disjoint matrix cut oracle, the additive oracle, and the cut
oracle. The comparison of their definitions and relative power is illustrated
in Fig. 1.

######  Definition 17 (Matrix cut oracle and disjoint matrix cut oracle for a
graph).

Let $G=(V,w)$ be a weighted graph. The matrix cut oracle for $G$ is the matrix
cut oracle for the adjacency matrix $A_{G}$ of $G$. The disjoint matrix cut
oracle for $G$ is the matrix cut oracle for $G$ with the restriction that it
can only be queried on strings $x,y\in\\{0,1\\}^{|V|}$, where $x_{i}y_{i}=0$,
for all $1\leq i\leq n$.

If we consider the strings $x,y\in\\{0,1\\}^{|V|}$ as characteristic vectors
of the sets $X,Y\subseteq V$, the restriction on the domain of the disjoint
matrix cut oracle is that it is only defined if $X\cap Y=\emptyset$, which
explains its name.

Beside the matrix oracles we will look at two more oracle models for accessing
a graph, the additive oracle and the cut oracle.

######  Definition 18 (Additive oracle).

Let $G=(V,w)$ be a weighted graph. The additive oracle
$a:[2]^{V}\rightarrow\mathbb{N}$ returns $a(S)=\sum_{\\{u,v\\}\in
S^{(2)}}w(\\{u,v\\})$ for any subset $S\subseteq V$.

######  Definition 19 (Cut oracle).

Let $G=(V,w)$ be a weighted graph. The cut oracle
$c:[2]^{V}\rightarrow\mathbb{N}$ returns $c(S)=w(S,V\setminus S)$ for any
subset $S\subseteq V$.

Learning graphs with an additive oracle have been extensively studied in the
classical case [GK98, GK00, ABK+04, Maz10, BM10, BM11]. For their proofs many
of these papers actually work with matrix cut queries, and we find it useful
to explicitly define these here. The cut oracle has also been studied in the
classical case in the context of computing the minimum cut of a graph [RSW18,
MN20]. We see in the next section that the cut oracle is the weakest of all
these models, and our main algorithmic results will be for the cut oracle
model.

${\mathrm{general}(S,T)}$${\mathrm{additive}(S,S)}$${\mathrm{disjoint}(S,T)}$$\mathrm{cut}(S,\bar{S})$$\scriptstyle{1}$$\scriptstyle{1}$$\scriptstyle{3}$$\scriptstyle{5}$$\scriptstyle{1}$$\scriptstyle{\Theta(n)}$$\scriptstyle{\Theta(n)}$$\scriptstyle{3}$
Figure 1: Illustration of oracles for comparison. The arrows indicate
reductions, and $A\xrightarrow{s}B$ means that a query to oracle $B$ can be
simulated by $s$ queries to oracle $A$.

###  4.1 Relationships between oracles

In this section we examine the power of the four oracles we have defined for
graphs. In essence we show that if we consider the relative power of these
oracles up to a constant overhead, then the disjoint matrix cut oracle for
graphs and the cut oracle have the same power, the matrix cut oracle for
graphs and the additive oracle have the same power, and the power of the
latter group is greater than the power of the former.

######  Definition 20 (Constant-reduction between oracles).

Let $O_{1}$ and $O_{2}$ be graph oracles. We say that $O_{1}$ is constant-
reducible to $O_{2}$ if there exist a positive integer $k$ such that for every
weighted graph $G=(V,w)$, every query of $O_{1}$ to $G$ can be computed with
$k$ queries of $O_{2}$ to $G$. If $O_{1}$ and $O_{2}$ are mutually constant-
reducible to each other, then they are called constant-equivalent.

The first lemma shows the constant-equivalence of the disjoint matrix cut
oracle for graphs and the cut oracle.

######  Lemma 21.

The disjoint matrix cut oracle for graphs and the cut oracle are constant-
equivalent. In particular, the cut oracle can simulate with $3$ queries a
query of the disjoint matrix cut oracle for graphs.

###### Proof.

The cut oracle is obviously 1-reducible to the disjoint matrix cut oracle. For
the reverse direction, let $G=(V,w)$ be a weighted graph with $|V|=n$ and let
$A_{G}$ be its adjacency matrix. Let $x,y\in\\{0,1\\}^{n}$ be the
characteristic vectors of $X,Y\subseteq V$ where $X$ and $Y$ are disjoint.
Then

$\displaystyle x^{T}A_{G}y$ $\displaystyle=w(X,Y)$
$\displaystyle=\frac{1}{2}\left(c(X)+c(Y)-c(X\cup Y)\right)\enspace.$

∎

######  Lemma 22.

Let $G$ be a bipartite graph. A matrix cut query to the biadjacency matrix of
$G$ can be simulated by $3$ cut queries.

###### Proof.

Let $B_{G}$ be the biadjacency matrix of $G$ with $k$ left and $\ell$ right
vertices, and let $x\in\\{0,1\\}^{k},y\in\\{0,1\\}^{\ell}$. We define the
vectors $\bar{x},\bar{y}\in\\{0,1\\}^{k+\ell}$ as $\bar{x}=[x;0^{\ell}]$ and
$\bar{y}=[0^{k};y]$. Then $x^{T}B_{G}y={\bar{x}}^{T}A_{G}\bar{y}$, where
$A_{G}$ is the adjacency matrix of $G$. Since $x$ and $y$ are the
characteristic vectors of disjoint sets in $V_{1}\cup V_{2}$, by Lemma 21 we
can compute $x^{T}B_{G}y$ with 3 queries to the cut oracle for $G$. ∎

The constant-equivalence of the matrix cut oracle for graphs and the additive
oracle was essentially shown by Grebinski and Kucherov in Theorem 4 of [GK00].
For completeness we reproduce here the proof.

######  Lemma 23.

The matrix cut oracle for graphs and the additive oracle are constant-
equivalent. In particular, the latter oracle can simulate with $5$ queries a
query of the former.

###### Proof.

Let $G=(V,w)$ be a weighted graph on $n$-vertices, and let $A_{G}$ be its
adjacency matrix. The additive oracle is 1-reducible to the matrix cut oracle
for $A_{G}$ because for every set $X\subseteq V$ with characteristic vector
$x\in\\{0,1\\}^{n}$, we have $a(X)=\frac{1}{2}x^{T}A_{G}x$.

For the reverse direction we show that the matrix cut oracle to $A_{G}$ can be
simulated with 5 queries to the additive oracle for $G$. For this let
$X,Y\subseteq V$ be arbitrary sets. We consider the characteristic vectors
$x_{-},y_{-}$ and $z$ of respectively $X\setminus Y,Y\setminus X$ and $X\cap
Y$. Then

$\displaystyle x^{T}A_{G}y$ $\displaystyle=(x_{-}+z)^{T}A_{G}(y_{-}+z)$
$\displaystyle=x_{-}^{T}A_{G}y_{-}+x_{-}^{T}A_{G}z+z^{T}A_{G}y_{-}+z^{T}A_{G}z$
$\displaystyle=\frac{1}{2}\left((x_{-}+y_{-})^{T}A_{G}(x_{-}+y_{-})+x^{T}A_{G}x+y^{T}A_{G}y\right)-x_{-}^{T}A_{G}x_{-}-y_{-}^{T}A_{G}y_{-}\enspace.$

To go from the second line to the last line we used that $A_{G}$ is symmetric,
that the sets $X\setminus Y,Y\setminus X$ and $X\cap Y$ are pairwise disjoint,
and finally the fact that if $u_{1}$ and $u_{2}$ are the characteristic
vectors of the disjoint sets $U_{1},U_{2}\subseteq V$ then
$u_{1}^{T}A_{G}u_{2}=a(U_{1}\cup U_{2})-a(U_{1})-a(U_{2})$.

∎

Since the matrix cut oracle for graphs is by definition at least as strong as
the disjoint matrix cut oracle for graphs, Lemma 21 and Lemma 23 imply that
the cut oracle is constant reducible to the additive oracle. The following
lemma shows that the simulation in fact can be done by 3 queries.

######  Lemma 24.

Let $G=(V,w)$ be a weighted graph. The cut oracle to $G$ is $3$-reducible to
the additive oracle for $G$.

###### Proof.

For any $S\subseteq V$

$c(S)=a(V)-a(S)-a(V\setminus S)\enspace.$

∎

We now turn to the question of simulating an additive oracle with a cut
oracle. In an $n$-vertex weighted graph $G=(V,w)$, we can simulate an additive
oracle with at most $3n$ applications of a cut oracle. This is because for any
$S\subseteq V$,

$a(S)=\frac{1}{2}\sum_{v\in S}w(v,S\setminus\\{v\\})\enspace$

and each $w(v,S\setminus\\{v\\})$ can be computed with $3$ cut queries by
Lemma 21. Note that this algorithm works no matter how large the weights are.
We next show that for weighted graphs with sufficiently large weights this
trivial algorithm is nearly tight, and in the worst case $\Omega(n)$ cut
queries are needed to simulate an additive query.

To do this, we first need a specific form of the Fredholm alternative.

######  Lemma 25 (Fredholm Alternative).

Let $A\in\\{0,1\\}^{N\times k}$ have independent columns, and let
$b\in\\{0,1\\}^{N}$. Suppose that $Ax=b$ has no solution $x\in\mathbb{R}^{k}$.
Then the integer vector
$\hat{y}=\det(A^{T}A)(I-A(A^{T}A)^{-1}A^{T})b\in\mathbb{Z}^{N}$ satisfies

  1. 1.

$\hat{y}^{T}A=\vec{0}\;,$

  2. 2.

$\hat{y}^{T}b\neq 0\;,$ and

  3. 3.

$\|\hat{y}\|_{\infty}\leq N^{k+1/2}k^{k/2}.$

###### Proof.

As $A$ has independent columns, $A^{T}A$ is invertible. Let
$b_{c}=A(A^{T}A)^{-1}A^{T}b$ be the orthogonal projection of $b$ onto the
column space of $A$ and $y=(I-A(A^{T}A)^{-1}A^{T})b$ be the orthogonal
projection onto the left nullspace. Then $b=b_{c}+y$ and, as $Ax=b$ has no
solution, $y\neq\vec{0}$. As $y$ is in the left nullspace, we have
$y^{T}A=\vec{0}$. Also $y^{T}b=y^{T}(b_{c}+y)=\|y\|^{2}\neq 0$ as
$y^{T}b_{c}=0$.

Now $\|y\|\leq\|b\|\leq\sqrt{N}$, thus also $\|y\|_{\infty}\leq\sqrt{N}$. For
an invertible matrix $B$, by Cramer’s rule $B^{-1}=\mathrm{adj}(B)/\det(B)$,
where $\mathrm{adj}(B)$ is the adjugate matrix of $B$. Thus
$\det(A^{T}A)\cdot(A^{T}A)^{-1}=\mathrm{adj}(A^{T}A)$ is an integer matrix and
$\hat{y}=\det(A^{T}A)y$ is an integer vector. As $\hat{y}$ is just a nonzero
scalar factor of $y$, we have $\hat{y}^{T}A=0$ and $\hat{y}^{T}b\neq 0$.
Finally, $\|\hat{y}\|_{\infty}\leq\sqrt{N}\cdot\det(A^{T}A)\leq
N^{k+1/2}k^{k/2}$, as the entries of $A^{T}A$ are at most $N$ and Hadamard’s
inequality gives that $\det(B)\leq N^{k}k^{k/2}$ for a $k$-by-$k$ matrix $B$
whose entries are bounded by $N$. ∎

######  Theorem 26.

Any deterministic cut query algorithm on weighted graphs with vertex set $V$
must make at least $|V|/2$ queries to compute $a(V)$.

###### Proof.

Let $G$ be a weighted graph with vertex set $V$ where $|V|=n$. We will show
that at least $n/2$ cut queries are needed to compute the total edge weight
$a(V)$ in $G$.

Let $\mathrm{Sym}_{n}^{0}$ be the vector space of symmetric $n$-by-$n$
matrices with zeros along the diagonal. Let the map
$\mathrm{symvec}:\mathrm{Sym}_{n}^{0}\to\mathbb{R}^{\binom{n}{2}}$ be defined
by
$\mathrm{symvec}(C)=[C(2\mathbin{:}n,1);C(3\mathbin{:}n,2);\cdots;C(n,n-1)]$,
which is an isomorphism between the two vector spaces.

Let $B=J-I$ where $J$ is the $n$-by-$n$ all ones matrix and $I$ is the
$n$-by-$n$ identity matrix. Let $b=\mathrm{symvec}(B)$. Then
$a(V)=\mathrm{symvec}(A_{G})^{T}b$ where $A_{G}$ is the adjacency matrix of
$G$. For a subset $X\subseteq V$ of the vertices, let $x\in\\{0,1\\}^{n}$ be
the characteristic vector of $X$, and let $\bar{x}\in\\{0,1\\}^{n}$ be the
characteristic vector of $V\setminus X$. Then for the cut value of $X$ we have
$c(X)=\mathrm{symvec}(A_{G})^{T}\mathrm{symvec}(x{\bar{x}}^{T}+\bar{x}x^{T}).$
Observe that the rank of the matrix $x{\bar{x}}^{T}+\bar{x}x^{T}$ is 2.

Consider a deterministic cut query algorithm making $k<n/2$ many queries. Let
$m=n^{2k+1}k^{k/2}$, and let $G_{1}$ be the graph whose adjacency matrix is
$A_{G_{1}}=m\cdot B$. We set $a_{1}=\mathrm{symvec}(A_{G_{1}})$. Suppose that
the algorithm makes queries $X_{1},\ldots,X_{k}\subseteq V$ in $G_{1}$, with
respective characteristic sequences $x_{1},\ldots,x_{k}\in\\{0,1\\}^{n}$. Let
$d_{i}=\mathrm{symvec}(x_{i}{\bar{x}_{i}}^{T}+\bar{x}_{i}x_{i}^{T})$ for
$i=1,\ldots,k$, and let $D$ be the $\binom{n}{2}$-by-$k$ matrix whose $i$th
column is $d_{i}$.

As the rank of $B$ is $n$ and $k<n/2$, there is no solution $x$ to the
equation $Dx=b$, since otherwise we could express $B$ as a linear combination
of $k$ matrices of rank 2. Let $\hat{y}\in\mathbb{Z}^{\binom{n}{2}}$ be the
vector given by Lemma 25 satisfying $\hat{y}^{T}D=\vec{0}$ and
$\hat{y}^{T}b\neq 0$. Then by the choice of $m$ and by Lemma 25,
$a_{1}+\hat{y}$ will be a non-negative integer vector. Let $G_{2}$ be the
weighted graph whose adjacency matrix satisfies
$\mathrm{symvec}(A_{G_{2}})=a_{1}+\hat{y}$.

Now $a_{1}^{T}D=(a_{1}+\hat{y})^{T}D$ means that the graphs $G_{1}$ and
$G_{2}$ give the same answers on all queries. Yet
$a_{1}^{T}b\neq(a_{1}+\hat{y})^{T}b$, meaning that the total sum of weights in
$G_{1}$ and in $G_{2}$ are different. ∎

###  4.2 Learning graphs with an additive oracle

Lemma 23 immediately lets us apply Lemma 13 and Theorem 16 to learning graphs
with additive queries.

######  Corollary 27.

Let $G=(V,w)$ be a weighted graph on $n>1$ vertices.

  1. 1.

If every vertex has degree at most $d$ then there is is a quantum algorithm
that learns $A$ with probability at least $1-\delta$ after making
$O((d\log(Mn/d)+\log(1/\delta))\log(M))$ many additive oracle queries to $G$.

  2. 2.

If $G$ has $m$ edges then there is a quantum algorithm that learns $G$ with
probability at least $1-\delta$ after making

$O\left(\sqrt{m\log(Mn)}\log(M)+\log(Mn)\log(n)\log\left(\frac{n\log(n)}{\delta}\right)\right)$

many additive oracle queries to $G$. When $M=2$, a better bound of
$O(\sqrt{m\log(n)}+\log(n)+\log(1/\delta))$ many additive queries holds.

Note that this result implies that one can learn a matching or Hamiltonian
cycle using $O(\log n)$ quantum additive queries, in contrast to the
$\Theta(n)$ additive queries needed deterministically [GK00].

###  4.3 Learning graphs with a cut oracle

Since by Theorem 26 a cut oracle cannot efficiently simulate an additive
oracle (or a matrix cut oracle), we must do more work to adapt the results
from Section 3 to the case of a cut oracle. We first show how to learn a
general weighted graph with weights bounded by $M$ with $O(n\log(M))$ many cut
queries.

######  Theorem 28.

Let $G=(V,w)$ be a weighted graph with $n$ vertices and edge weights in $[M]$.
There is a quantum algorithm that learns $G$ perfectly after making
$3n\left\lceil\log(M)\right\rceil$ cut queries. In particular, a simple graph
can be learned perfectly by a quantum algorithm making $3n$ cut queries.

###### Proof.

Let $A_{G}$ be the adjacency matrix of $G$, and let $v_{1},\ldots,v_{n}$ be
the order of the vertices labelling the rows and columns. Let
$B_{i}=A_{G}(i,\\{1,\ldots,i-1\\}\cup\\{i+1,\ldots,n\\})$ be the $i^{th}$ row
of $A_{G}$ with the $i^{th}$ entry (which must be $0$) removed. Then
$x^{T}B_{i}y$ can be computed with 3 cut queries by Lemma 22 for any
$x\in\\{0,1\\},y\in\\{0,1\\}^{n-1}$. Thus by Corollary 12 we can learn $B_{i}$
with $3\left\lceil\log M\right\rceil$ many cut queries. Doing this in turn for
each $v_{i}$ gives the result.

The “in particular” statement follows by taking $M=2$. ∎

Next we show how to learn low-degree and sparse graphs more efficiently. We
start out in the bipartite case.

######  Lemma 29.

Let $G=(V_{1},V_{2},w)$ be a weighted bipartite graph with
$|V_{1}|=k,|V_{2}|=\ell$, and edge weights in $[M]$.

  1. 1.

If $\deg(u)\leq d$ for every $u\in L$ then there is a quantum algorithm that
learns $G$ with probability at least $1-\delta$ after making
$O((d\log(M\ell/d)+\log(1/\delta))\log M)$ many cut queries.

  2. 2.

If $G$ has $m$ edges then there is a quantum algorithm that learns $G$ with
probability at least $1-\delta$ after making

$O\left(\sqrt{m\log(M\ell)}\log(M)+\log(\ell
M)(\log(\ell)+1)\log\left(\frac{k(\log(\ell)+1)}{\delta}\right)\right)$

many cut queries. When $M=2$, a better bound of
$O(\sqrt{m\log(\ell)}+\log(\ell+1)+\log(1/\delta))$ many cut queries holds.

###### Proof.

By Lemma 22 any matrix cut query to the biadjacency matrix of $G$ can be
computed by 3 queries to the cut oracle for $G$. Item (1) therefore follows
from Lemma 13 and item (2) follows from Theorem 16. ∎

Now we extend the bipartite algorithms to the general case.

######  Theorem 30.

Let $G=(V,w)$ be a weighted $n$-vertex graph, $n>1$, with edge weights in
$[M]$.

  1. 1.

If $\deg(v)\leq d$ for every $v\in V$ then there is a quantum algorithm that
learns $G$ with probability at least $1-\delta$ after making
$O((d\log(Mn/d)+\log(\log(n)/\delta))\log(M)\log(n))$ many cut queries.

  2. 2.

If $G$ has $m$ edges then there is a quantum algorithm that learns $G$ with
probability at least $1-\delta$ after making

$O\left(\left(\sqrt{m\log(Mn)}\log(M)+\log(Mn)(\log(n))\log\left(\frac{n\log(n)}{\delta}\right)\right)\log(n)\right)$

many cut oracle queries to $G$. When $M=2$, a better bound of
$O((\sqrt{m\log(n)}+\log(n)+\log(\log(n)/\delta))\log(n))$ many cut queries
holds.

###### Proof.

Let $r=\left\lceil\log(n)\right\rceil$. We suppose that the vertices are
labeled with $r$-bit binary strings. We define $r$ many weighted bipartite
graphs $G_{i}=(L_{i},R_{i},w_{i})$, for $i=1,\ldots,r$, derived from $G$ as
follows. $L_{i}$ consists of the vertices of $V$ whose $i^{th}$ bit is 0,
whereas $R_{i}$ consists of the vertices whose $i^{th}$ bit is 1. The weight
function $w_{i}$ in $G_{i}$ is defined as

$w_{i}(u,v)=\begin{cases}w(u,v)&\mbox{ if }(u,v)\in L_{i}\times R_{i}\\\
0&\mbox{ otherwise}\enspace.\end{cases}$

Let $B_{G_{i}}$ be the biadjacency matrix of $G_{i}$. Let
$x\in\\{0,1\\}^{|L_{i}|},y\in\\{0,1\\}^{|R_{i}|}$ and $X=\\{v\in
V:x_{i}(v)=1\\},Y=\\{v\in V:y_{i}(v)=1\\}$, and let $\chi_{X}$ and $\chi_{Y}$
be the characteristic sequence of respectively $X$ and $Y$ in $V$. Then
$x^{T}B_{G_{i}}y=\chi_{X}^{T}A_{G_{i}}\chi_{Y}$, and since $X$ and $Y$ are
disjoint sets in $V$ we can compute it with $3$ cut queries to $G$ by Lemma
21.

We first prove item (1). As $G$ has degree at most $d$, each $B_{i}$ will also
have degree at most $d$. Therefore by applying the first item of Lemma 29 with
error bound $\delta/r$ we can learn $B_{i}$ with
$O((d\log(Mn/d)+\log(\log(n)/\delta))\log(M))$ many cut queries. Doing this
for each $B_{i}$ in turn gives item (1).

Similarly for item (2), as $G$ has at most $m$ edges so will each $B_{i}$.
Learning each $B_{i}$ in turn by the second item of Lemma 29 with error bound
$\delta/r$ gives the bound in item (2). ∎

###  4.4 Lower bounds

In the classical case, an $\Omega(n)$ lower bound is known on the number of
cut queries needed by a deterministic algorithm to determine if a graph is
connected. As observed by Harvey (Theorem 5.9 in [Har08]), an $\Omega(n)$ cut
query lower bound for connectivity follows from the deterministic
communication complexity lower bound of $\Omega(n\log n)$ for connectivity by
[HMT88], and the fact that the answers to cut queries can be communicated with
$O(\log n)$ bits. Clearly this lower bound applies to all 4 of the graph
oracles we have discussed, as all of them have answers that can be
communicated with $O(\log(n))$ bits. For randomized communication protocols a
$\Omega(n)$ lower bound is known for connectivity [BFS86], giving an
$\Omega(n/\log(n))$ lower bound on the number of cut queries needed to solve
connectivity.

The quantum case behaves differently. There is an analogous communication
complexity result: [IKL+12] show that the bounded-error quantum communication
complexity of connectivity is $\Omega(n)$. However, the standard way to turn a
query algorithm into a communication protocol, developed by Buhrman, Cleve,
and Wigderson (BCW) [BCW98], involves Alice and Bob sending back and forth the
query and answer state. In the case of cut queries, this is a state of the
form $\sum_{S\subseteq\\{0,1\\}^{n}}\alpha_{S}|S\rangle|b_{S}\rangle$ that is
$n+\log(n)$-qubits. Thus a $k$-cut query quantum algorithm for connectivity
gives a $kn$ qubit communication protocol for connectivity via the BCW
simulation. Our polylogarithmic cut query algorithm for connectivity shows an
example of a (partial) function where this blow-up from the BCW simulation is
nearly optimal. We note that Chakraborty et al. [CCMP19] recently gave the
first example of a _total_ function showing that the BCW blow-up can be
necessary.

We now show that our quantum algorithms for learning a general graph with
$O(n)$ cut queries Theorem 28, a graph of maximum degree $d$ with
$\widetilde{O}(d)$ cut queries, and an $m$-edge graph with
$\widetilde{O}(\sqrt{m})$ cut queries Theorem 30 are all tight, even if the
algorithms are equipped with the stronger additive oracle.

Recall that the inner product function
$\mathrm{IP}_{N}:\\{0,1\\}^{N}\times\\{0,1\\}^{N}\rightarrow\\{0,1\\}$ on
strings of length $N$ is defined as
$\mathrm{IP}_{N}(x,y)=\mathrm{PARITY}(x\wedge y)$. The bounded-error quantum
communication complexity of $\mathrm{IP}_{N}$ is $\Omega(N)$ [Kre95].

######  Lemma 31.

Suppose there is a bounded-error quantum query algorithm that learns a graph
on $n$ vertices with $k$ many additive queries. Then there is a bounded-error
quantum communication protocol for $\mathrm{IP}_{\binom{n}{2}}$ with $O(kn)$
qubits of communication.

###### Proof.

We consider $[n]^{(2)}$, the set of possible edges in a graph with vertex set
$[n]$. Alice and Bob first agree on a bijective mapping
$f:[\binom{n}{2}]\rightarrow[n]^{(2)}$. Now say that Alice receives
$x\in\\{0,1\\}^{\binom{n}{2}}$ and Bob receives
$y\in\\{0,1\\}^{\binom{n}{2}}$, and they wish to compute
$IP_{\binom{n}{2}}(x,y)$. Bob first creates a graph $G_{y}$ with vertex set
$[n]$ and edge set $E=\\{f(e):y_{e}=1\\}$. Alice now runs the quantum query
algorithm to learn $G_{y}$ by sending the query states to Bob, who serves each
query and sends the state back to Alice. As the query state is $n+\log(n)$
qubits, this will take communication $O(kn)$ if there are $k$ queries. ∎

######  Theorem 32.

Any quantum algorithm to learn an $n$-vertex graph with bounded-error must
make $\Omega(n)$ many additive queries.

###### Proof.

The theorem is immediate from Lemma 31 and Kremer’s $\Omega(n^{2})$ lower
bound on the quantum communication complexity of the inner product on
$\binom{n}{2}$ bits. ∎

######  Corollary 33.

For any $n$ and $m\leq\binom{n}{2}$ there is a family of $n$-vertex graphs
$\mathcal{G}_{n,m}$ with at most $m$ edges such that any quantum algorithm
requires $\Omega(\sqrt{m})$ many additive queries to learn a graph from
$\mathcal{G}_{n,m}$ with bounded-error.

###### Proof.

Let $\mathcal{G}_{n,m}$ be the family of graphs that are arbitrary among the
first $k$ vertices, where $k$ is the smallest integer such that
$\binom{k}{2}\geq m$, and all remaining $n-k$ vertices are isolated. By
Theorem 32 $\Omega(k)=\Omega(\sqrt{m})$ many additive queries are needed to
learn a graph from this family. ∎

######  Corollary 34.

For any $n$ and $d\leq n$ there is a family of $n$-vertex graphs
$\mathcal{G}_{n,d}$ with each vertex having degree at most $d$ such that any
quantum algorithm requires $\Omega(d\log(n/d))$ many additive queries to learn
a graph from $\mathcal{G}_{n,d}$ with bounded-error.

###### Proof.

Let $\mathcal{G}_{n,d}$ be the set of all $d$ regular graphs on $n$-vertices.
It is known that $|\mathcal{G}_{n,d}|\geq\left(\frac{n}{2ed}\right)^{nd/2}$
(see the argument above Theorem 4 in [GK00], or the very general results in
[LW19]). Letting
$\ell=\lfloor\frac{nd}{2}\log\left(\frac{n}{2ed}\right)\rfloor$, Alice and Bob
can therefore agree on a bijection between $\\{0,1\\}^{\ell}$ and a subset of
$\mathcal{G}_{n,d}$. As in the proof of Lemma 31, they then can use an
algorithm to learn graphs in $\mathcal{G}_{n,d}$ with $k$ additive queries to
solve $\mathrm{IP}_{\ell}$ with quantum communication complexity $O(kn)$. Thus
$k=\Omega(\ell/n)=\Omega(d\log(n/d))$. ∎

##  5 A quantum algorithm for computing connected components with cut queries

In this section, we give a quantum algorithm that outputs the connected
components of an $n$-vertex graph after making $O(\log(n)^{6})$ cut queries.
By Lemma 24, this implies the same result with respect to additive queries.

We first give a high level overview of the algorithm. Let $G$ be an $n$-vertex
graph with vertex set $V$ and $A_{G}$ its adjacency matrix. For this high
level overview, we will assume that we have matrix cut query access to
$A_{G}$. This case contains all of the conceptual ideas needed and eliminates
several technical issues that arise in the cut query case.

The algorithm proceeds in rounds. In every round, we maintain a partition of
$V$. In a general round, we represent the partition as
$\\{S_{1},\ldots,S_{k},C_{1},\ldots,C_{t}\\}$ and let
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{C}=\\{C_{1},\ldots,C_{t}\\}$. We refer to sets of vertices as
supervertices. The algorithm maintains the invariants that each
$\mathcal{C}_{j}$ is a connected component, i.e. the induced subgraph on
$C_{j}$ is connected and $|E(C_{j},V\setminus C_{j})|=0$, and that for each
$S_{i}$ the induced subgraph on $S_{i}$ is connected. As the sets $C_{j}$ are
connected components, they require no further processing and thus in a round
we focus only on the sets in $\mathcal{S}$. We initially set
$\mathcal{S}=\tilde{V}=\\{\\{v\\}:v\in V\\}$ and $\mathcal{C}=\emptyset$.

An important concept for the algorithm will be the adjacency matrix of the
weighted graph among the sets of $\mathcal{S}$. For
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ define a $k$-by-$k$ matrix
$A_{\mathcal{S}}$ where $A_{\mathcal{S}}(i,j)=|E(S_{i},S_{j})|$. A key fact is
that matrix cut query access to $A_{G}$ allows us to implement matrix cut
queries on $A_{\mathcal{S}}$. For $x,y\in\\{0,1\\}^{k}$ define
$u,v\in\\{0,1\\}^{n}$ to be the characteristic vectors of the sets
$\cup_{i:x_{i}=1}S_{i}$ and $\cup_{i:y_{i}=1}S_{i}$ respectively. Then we have
$x^{T}A_{\mathcal{S}}y=u^{T}A_{G}v$.

A general round proceeds as follows. We take a degree threshold
$d=\Theta(\log(n)^{2})$. The superdegree of a supervertex $S_{i}$ is the
number of $j\neq i$ such that $|E(S_{i},S_{j})|>0$. Supervertices with
superdegree at most $d$ we call low superdegree, and supervertices with
superdegree greater than $d$ we call high superdegree.

  1. 1.

Estimate the superdegree of all supervertices by Lemma 15 ($O(\log(n)^{3})$
queries).

  2. 2.

For low superegree supervertices learn all their neighbors $S_{j}$ by Lemma 13
($O(\log(n)^{4})$ queries taking $d=\Theta(\log(n)^{2})$).

  3. 3.

Randomly sample $\mathcal{R}\subseteq\mathcal{S}$ satisfying
$|\mathcal{R}|\leq|\mathcal{S}|/2$. With high probability for every high
degree supervertex $S_{i}$ there is an $R\in\mathcal{R}$ with
$|E(S_{i},R)|>0$, and we again use Lemma 13 to find such an $R$ for every high
degree $S_{i}$ with $O(\log(n)^{4})$ queries.

  4. 4.

Merge all supervertices $S_{i},S_{j}$ for which we know $|E(S_{i},S_{j})|>0$
and update $\mathcal{S}$ and $\mathcal{C}$ accordingly.

We show that with high probability after this merging step the number of
supervertices in $\mathcal{S}$ is at most half of what it was at the beginning
of the round. This follows because with high probability every high degree
supervertex will be merged with an element of $\mathcal{R}$. For low degree
supervertices, we learn all of their neighbors. Therefore if the connected
component of a low degree supervertex $S_{i}$ only contains low degree
supervertices, this step will learn its entire connected component and we can
add this component to $\mathcal{C}$. Otherwise there is some low degree
supervertex $S_{j}$ in the connected component of $S_{i}$ that is connected to
a high degree supervertex $S_{\ell}$. We will learn this connection in Step
(2), and learn a neighbor of $S_{\ell}$ in $\mathcal{R}$ in step (3). This
means that in Step (4) $S_{i}$ will be merged into a supervertex that also
contains some element of $\mathcal{R}$. Thus every supervertex for which we
have not already learned its connected component will be merged with a
supervertex in $\mathcal{R}$ with high probability and at the end of the round
the total number of supervertices in $\mathcal{S}$ is reduced by at least
half. The algorithm thus terminates after $O(\log n)$ rounds and the total
complexity becomes $O(\log(n)^{5})$ many matrix cut queries.

We have seen that cut queries cannot efficiently simulate matrix cut queries
in general. However, by Lemma 22, cut queries can simulate matrix cut queries
on _bipartite_ weighted graphs. The trick we use to adapt the above algorithm
to the cut query case is to always work with bipartite graphs. For a graph $G$
we associate $\left\lceil\log n\right\rceil$ many bipartite graphs
$(L_{i},R_{i},E_{i})$ for $i\in\left\lceil\log n\right\rceil$, where
$L_{i}=\\{v:v_{i}=0\\},R_{i}=\\{v:v_{i}=1\\}$ and $E_{i}=\\{(u,v)\in V\times
V:\\{u,v\\}\in E,u\in L_{i},v\in R_{i}\\}$. Note that every edge of $G$
appears as an edge in some $(L_{i},R_{i},E_{i})$. We essentially run steps
(1)–(3) above on each $(L_{i},R_{i},E_{i})$ separately, then incorporate all
the information learned in the merge step in (4). Having to iterate over these
$O(\log(n))$ many bipartite graphs results in an extra multiplicative
logarithmic factor in the complexity, resulting in the claimed bound of
$O(\log(n)^{6})$ cut queries.

###  5.1 Auxiliary subroutines

In this subsection we go over some auxiliary subroutines that will be used in
the cut query algorithm for connectivity. We will make use of the following
definition.

######  Definition 35 (Supervertex, Superdegree).

A _supervertex_ is a subset of $S\subseteq V$ of vertices. We say that a
supervertex $S$ is connected if the subgraph induced on $S$ is connected.

We say that a set of supervertices $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ is
_valid_ if $S_{i}\cap S_{j}=\emptyset$ for all $i\neq j$. We say that two
valid sets of supervertices $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$ are _disjoint_ if $S_{i}\cap
T_{j}=\emptyset$ for all $i\in\\{1,\ldots,k\\},j\in\\{1,\ldots,\ell\\}$.

We say that there is a _superedge_ between supervertices $S_{1},S_{2}$ if
$|E(S_{1},S_{2})|>0$. Given two disjoint valid sets of supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$, the _superdegree of $S_{i}$ into
$\mathcal{T}$_, denoted $\deg_{\mathcal{T}}(S_{i})$, is the number of
$j\in[\ell]$ such that $|E(S_{i},T_{j})|>0$.

######  Definition 36.

Let $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$ be disjoint valid sets of
supervertices of an $n$-vertex graph $G$. Define the weighted biadjacency
matrix between $\mathcal{S}$ and $\mathcal{T}$ as the matrix
$B\in[n^{2}]^{k\times\ell}$ where $B(i,j)=|E(S_{i},T_{j})|$.

######  Lemma 37.

Let $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$ be disjoint valid sets of
supervertices of an $n$-vertex graph $G$. Let $B$ be the weighted biadjacency
matrix between $\mathcal{S}$ and $\mathcal{T}$. A matrix cut query to $B$ can
be answered with 3 cut queries to $G$.

###### Proof.

For $x\in\\{0,1\\}^{k},y\in\\{0,1\\}^{\ell}$ we have
$x^{T}By=|E(\cup_{i:x(i)=1}S_{i},\cup_{j:y(j)=1}T_{j})|$ and thus can be
computed with 3 cut queries by Lemma 21. ∎

######  Corollary 38 (Approximate Degree Sequence).

There is a quantum algorithm Approximate Degree
Sequence$(\mathcal{S},\mathcal{T},\delta)$ that takes as input disjoint valid
sets of supervertices $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$ of an $n$-vertex graph $G$ and an
error parameter $\delta$, and with probability at least $1-\delta$ outputs
$\vec{g}\in\mathbb{R}^{k}$ that is a good estimate of
$(\deg_{\mathcal{T}}(S_{1}),\ldots,\deg_{\mathcal{T}}(S_{k}))$. The number of
cut queries made is $O(\log(\ell
n)(\log(\ell)+1)\log(k(\log(\ell)+1)/\delta))$.

###### Proof.

Let $B$ be the weighted biadjacency matrix between $\mathcal{S}$ and
$\mathcal{T}$. By Lemma 37 a matrix cut query to $B$ can be answered by 3 cut
queries to $G$. The result then follows from Lemma 15. ∎

Algorithm 2 Approximate Degree Sequence$(\mathcal{S},\mathcal{T},\delta)$

Input: Disjoint valid sets of supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\},\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$
and an error parameter $\delta$
Output: Vector $\vec{g}\in\mathbb{R}^{k}$ that is a good estimate of
$(\deg_{\mathcal{T}}(S_{1}),\ldots,\deg_{\mathcal{T}}(S_{k}))$.

Algorithm 3 Learn Low$(\mathcal{S},\mathcal{T},h,\delta)$

Input: Disjoint valid sets of supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\},\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$,
a degree parameter $h$ such that $\deg_{\mathcal{T}}(S_{i})\leq h$ for all
$S_{i}\in S$, and an error parameter $\delta$.
Output: A $k$-by-$\ell$ matrix $B$ where $B(i,j)=|E(S_{i},T_{j})|$.

######  Corollary 39 (Learn Low).

There is a quantum algorithm Learn Low$(\mathcal{S},\mathcal{T},h,\delta)$
that takes as input disjoint valid sets of supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$ of an $n$-vertex graph $G$, a degree
parameter $h$ such that $\deg_{\mathcal{T}}(S_{i})\leq h$ for all
$S_{i}\in\mathcal{S}$, and an error parameter $\delta$. With probability at
least $1-\delta$ Learn Low$(\mathcal{S},\mathcal{T},h,\delta)$ outputs the
weighted biadjacency matrix between $\mathcal{S}$ and $\mathcal{T}$. The
number of cut queries made is $O((h\log(n/h)+\log(1/\delta))\log(n))$.

###### Proof.

Let $B$ be the weighted biadjacency matrix between $\mathcal{S}$ and
$\mathcal{T}$. The rows of $B$ have at most $h$ nonzero entries by assumption
and all entries are $O(n^{2})$. By Lemma 37 we can answer a matrix cut query
to $B$ by 3 cut queries to $G$. The result then follows from Lemma 13. ∎

We accomplish Step (3) in the high level description of the algorithm by a
routine called Reduce High. We first need a sampling lemma.

######  Lemma 40.

Let $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$ be disjoint valid sets of
supervertices of an $n$-vertex graph $G$, and suppose
$t/8\leq\deg_{\mathcal{T}}(S_{i})\leq 2t$. Randomly sample with replacement
$\frac{16\ell\ln(kn)}{t}$ many supervertices in $\mathcal{T}$, and call the
resulting set $\mathcal{R}$. Then, except with probability $O(n^{-2})$, the
superdegree of each $S_{i}$ into $\mathcal{R}$ will be at least $1$ and at
most $192\ln(n)$.

###### Proof.

Define $x^{(i)}\in\\{0,1\\}^{\ell}$ for $i\in\\{1,\ldots,k\\}$ by
$x^{(i)}(j)=1$ iff $|E(S_{i},T_{j})|>0$. Then the lemma follows by applying
Lemma 8 to $x^{(1)},\ldots,x^{(k)}$ with $\delta=1/n^{2}$ and using the fact
that $k\leq n$. ∎

######  Lemma 41 (Reduce High).

The quantum algorithm Reduce High$(\mathcal{S},\mathcal{T},d,\vec{g})$
(Algorithm 4) takes as input disjoint valid sets of supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$ of an $n$-vertex graph $G$, a degree
parameter $d$ such that $\deg_{\mathcal{T}}(S_{i})\geq d$ for all
$S_{i}\in\mathcal{S}$, and a vector $\vec{g}\in\mathbb{R}^{k}$ that is a good
estimate of $(\deg_{\mathcal{T}}(S_{1}),\ldots,\deg_{\mathcal{T}}(S_{k}))$.
Reduce High $(\mathcal{S},\mathcal{T},d,\vec{g})$ makes $O(\log(n)^{4})$ many
cut queries and with probability at least $1-O(\log(n)/n^{2})$ outputs a
$k$-by-$\ell$ Boolean matrix $B$ such that

  1. 1.

Every row of $B$ has at least one nonzero entry.

  2. 2.

If $B(i,j)\neq 0$ then $B(i,j)=|E(S_{i},T_{j})|$.

  3. 3.

$B$ has at most $\frac{256\ell\ln(n)}{d}$ many nonzero columns.

###### Proof.

The algorithm is given in Algorithm 4. First we bound the number of queries
made. We do $O(\log n)$ iterations of the for loop, and within each iteration
queries only occur in Line 5, which is a call Learn Low with an $O(\log n)$
degree parameter. Each such call to Learn Low requires $O(\log(n)^{3})$ many
cut queries by Corollary 39 Thus overall the number of queries is
$O(\log(n)^{4})$.

Now we show the correctness. As $\vec{g}\in\mathbb{R}^{k}$ provides good
estimates and $\deg_{\mathcal{T}}(S_{i})\geq d$ for all $S_{i}\in\mathcal{S}$,
we have $g(i)\geq d/2$ for all $i\in\\{1,\ldots,k\\}$. Also $g(i)\leq 4\ell$,
thus each $S_{i}$ will be put into $\mathcal{H}_{q}$ for some value of $q$ in
the loop.

Let us now consider a particular iteration of the for loop when $q=j$. Let
$\mathcal{H}_{j}=\\{S_{i}\in\mathcal{S}:2^{j-1}<g(i)\leq 2^{j}\\}$. As
$\vec{g}$ contains good estimates, this means
$2^{j-3}<\deg_{\mathcal{T}}(S_{i})\leq 2^{j+1}$ for all
$S_{i}\in\mathcal{H}_{j}$. We are thus in the setting of Lemma 8 with
$t=2^{j}$. As $\mathcal{R}_{j}$ is a
$\frac{16\ell\ln(|H_{j}|n)}{2^{j}}$-sample from $\mathcal{T}$ the conclusion
of Lemma 8 gives that the superdegree of every vertex in $\mathcal{H}_{j}$
into $\mathcal{R}_{j}$ is between $1$ and $192\ln(n)$, except with probability
$O(n^{-2})$. We now assume we are in this good case. Then the upper bound on
the degree passed to Learn Low is valid, and Learn Low will return the
weighted biadjacency matrix between $\mathcal{H}_{j}$ and $\mathcal{R}_{j}$
with probability $1-O(n^{-2})$ by Corollary 39

As every $S_{i}$ is in $\mathcal{H}_{q}$ for one call of the for loop, each
row of $B$ will have at least one nonzero entry. Further, as each call to
Learn Low returns a correct weighted biadjacency matrix between
$\mathcal{H}_{q}$ and $\mathcal{R}_{q}$ except with probability $1/n^{2}$, $B$
will satisfy item (2) except with probability at most $O(\log(n)/n^{2})$.

Finally, the only columns of $B$ that can be nonzero are those indexed by sets
that appeared in $\mathcal{R}_{q}$ at some point of the algorithm. As

$\displaystyle|\cup_{q}\mathcal{R}_{q}|$ $\displaystyle\leq
32\ell\ln(n)\cdot\left(\sum_{q=\lfloor\log
d\rfloor-1}^{\left\lceil\log\ell\right\rceil+2}\frac{1}{2^{q}}\right)$
$\displaystyle\leq
32\ell\ln(n)\cdot\frac{4}{d}\sum_{j=0}^{\infty}\frac{1}{2^{j}}$
$\displaystyle\leq\frac{256\ell\ln(n)}{d}\enspace,$

the total number of nonzero columns of $B$ is at most
$\frac{256\ell\ln(n)}{d}$. ∎

Algorithm 4 Reduce High$(\mathcal{S},\mathcal{T},d,\vec{g})$

Input: Disjoint valid sets of supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\},\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$
of an $n$-vertex graph $G$, a degree parameter $d$ such that
$\deg_{\mathcal{T}}(S_{i})\geq d$ for all $S_{i}\in\mathcal{S}$, and a vector
$\vec{g}\in\mathbb{R}^{k}$ such that
$\vec{g}(i)/4\leq\deg_{\mathcal{T}}(S_{i})\leq 2\vec{g}(i)$ for all
$i\in\\{1,\ldots,k\\}$.
Output: A $k$-by-$\ell$ matrix $B$ satisfying the conditions of Lemma 41.

1:$B\leftarrow\mathrm{zeros}(k,\ell)$

2:for $q=\lfloor\log d\rfloor-1$ to $\left\lceil\log\ell\right\rceil+2$ do

3: $\mathcal{H}_{q}=\\{S_{i}\in\mathcal{S}:2^{q-1}<\vec{g}(i)\leq 2^{q}\\}$

4: $\mathcal{R}_{q}\leftarrow$ Randomly choose
$\frac{16\ell\ln(|\mathcal{H}_{q}|n)}{2^{q}}$ supervertices in $\mathcal{T}$,
with replacement

5:
$B(\mathrm{ind}(\mathcal{H}_{q}),\mathrm{ind}(\mathcal{R}_{q}))\leftarrow\text{Learn
Low}(\mathcal{H}_{q},\mathcal{R}_{q},192\ln(n),1/n^{2})$

6:end for

7:return $B$

Algorithm 5 Contract$(\mathcal{S},\mathcal{A},\text{low})$

Input: Valid set of connected supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$, a list of $k$-by-$k$ weighted
adjacency matrices $\mathcal{A}=(A_{1},\ldots,A_{m})$ with rows and columns
labeled by elements of $\mathcal{S}$, a vector $\text{low}\in\\{0,1\\}^{k}$
indicating if each set $S_{i}$ is low.
Output: Sets of supervertices $\mathcal{S}^{\prime},\mathcal{C}$, where each
supervertex in $\mathcal{S}^{\prime},\mathcal{C}$ is connected, and moreover
the supervertices in $\mathcal{C}$ are connected components.

1:$L\leftarrow[(S_{i},\text{low}(i)):S_{i}\in\mathcal{S}]$

2:for $A\in\mathcal{A}$ do

3: for $(i,j)\in[k]^{(2)}$ do

4: if $A(i,j)>0$ then

5: Pop $(U,\text{flag1})\in L$ such that $S_{i}\subseteq U$

6: Pop $(W,\text{flag2})\in L$ such that $S_{j}\subseteq W$

7: $U\leftarrow U\cup W$

8: $\text{lowFlag}=\text{flag1}\wedge\text{flag2}$

9: Append $(U,\text{lowFlag})$ to $L$

10: end if

11: end for

12:end for

13:$\mathcal{S}^{\prime}\leftarrow\emptyset$

14:$\mathcal{C}\leftarrow\emptyset$

15:for $(U,\text{lowFlag})\in L$ do

16: if lowFlag = 0 then

17: $\mathcal{S}^{\prime}\leftarrow\mathcal{S}^{\prime}\cup\\{U\\}$

18: else

19: $\mathcal{C}\leftarrow\mathcal{C}\cup\\{U\\}$

20: end if

21:end for

22:return $\mathcal{S}^{\prime},\mathcal{C}$

Algorithm 6 Shrink$(\mathcal{S},d)$

Input: A valid set of connected supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$, and a degree parameter $d$.
Output: A set of connected supervertices $\mathcal{S}^{\prime}$, and a set
$\mathcal{C}$ of connected components.

1:$\text{low}\leftarrow\mathrm{ones}(k,1)$

2:$\mathcal{A}\leftarrow[\;]$

3:for $j=1$ to $\left\lceil\log(k)\right\rceil$ do

4: for $b\in\\{0,1\\}$ do

5: $\mathcal{L}_{j,b}=\\{S_{t}\in\mathcal{S}:t_{j}=b\\}$

6: $\mathcal{R}_{j,b}=\\{S_{t}\in\mathcal{S}:t_{j}=1-b\\}$

7: $\vec{g}\leftarrow$ Approximate Degree
Sequence$(\mathcal{L}_{j,b},\mathcal{R}_{j,b},1/n)$

8: $\mathcal{H}\leftarrow\\{S_{t}\in\mathcal{L}_{j,b}:\vec{g}(t)\geq d\\}$

9: $\text{low}(\mathrm{ind}(\mathcal{H}))=0$

10: $B_{j,b}\leftarrow\mathrm{zeros}(k,k)$

11:
$B_{j,b}(\mathrm{ind}(\mathcal{H}),\mathrm{ind}(\mathcal{R}_{j,b}))\leftarrow\text{Reduce
High}(\mathcal{H},\mathcal{R}_{j,b},d/4,\vec{g}(\mathrm{ind}(\mathcal{H})))$

12: $\mathcal{L}\leftarrow\\{S_{t}\in\mathcal{L}_{j,b}:\vec{g}(t)<d\\}$

13: $C_{j,b}\leftarrow\mathrm{zeros}(k,k)$

14:
$C_{j,b}(\mathrm{ind}(\mathcal{L}),\mathrm{ind}(\mathcal{R}_{j,b}))\leftarrow\text{Learn
Low}(\mathcal{L},\mathcal{R}_{j,b},2d,1/n)$

15: Append $B_{j,b},C_{j,b}$ to $\mathcal{A}$

16: end for

17:end for

18:$(\mathcal{S}^{\prime},\mathcal{C})\leftarrow$
Contract$(\mathcal{S},\mathcal{A},\text{low})$

19:return $(\mathcal{S}^{\prime},\mathcal{C})$

Algorithm 7 Connectivity algorithm with cut queries

Input: Cut oracle for a graph $G$ on $n$ vertices
Output: Connected components of $G$

1:$\mathcal{S}\leftarrow\tilde{V}$

2:$\text{ConComp}\leftarrow\emptyset$

3:repeat

4: $(\mathcal{S},\mathcal{C})\leftarrow Shrink(\mathcal{S},1024\left\lceil\log
n\right\rceil^{2})$

5: $\text{ConComp}\leftarrow\text{ConComp}\cup\mathcal{C}$

6:until $\mathcal{S}=\emptyset$

7:return ConComp

######  Lemma 42.

Let $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ be a valid set of supervertices,
$\mathcal{A}$ a list of $k$-by-$k$ weighted adjacency matrices, and
$\text{low}\in\\{0,1\\}^{k}$ a Boolean vector with the following properties:

  1. 1.

Every supervertex in $\mathcal{S}$ is connected.

  2. 2.

For every $A\in\mathcal{A}$ if $A(i,j)>0$ there is a superedge between $S_{i}$
and $S_{j}$.

  3. 3.

For every $(i,j)$ such that $\text{low}(i)=1$ and there is a superedge between
$S_{i}$ and $S_{j}$, there is an $A\in\mathcal{A}$ with $A(i,j)>0$.

Then the algorithm Contract$(\mathcal{S},\mathcal{A},\text{low})$ given in
Algorithm 5 outputs sets of supervertices $\mathcal{S}^{\prime},\mathcal{C}$
such that every $U\in\mathcal{S}^{\prime}$ is connected, every
$W\in\mathcal{C}$ is a connected component, and
$\mathcal{S}^{\prime}\cup\mathcal{C}$ is a partition of
$\cup_{S\in\mathcal{S}}S$. Moreover, for every $U\in\mathcal{S}^{\prime}$
there is an $S_{i}\subseteq U$ with $\text{low}(i)=0$.

###### Proof.

We first show that all supervertices in $\mathcal{S}^{\prime},\mathcal{C}$ are
connected. This follows because each $S_{i}\in\mathcal{S}$ is connected and we
only merge two supervertices $U$ and $W$ when there is an $S_{i}\subseteq
U,S_{j}\subseteq W$ and an $A\in\mathcal{A}$ with $A(i,j)>0$. As by hypothesis
$A(i,j)>0$ implies there is a superedge between $S_{i}$ and $S_{j}$ this means
that $U$ and $W$ are in fact connected.

Next we show that every $W\in\mathcal{C}$ is a connected component. Suppose
for a contradiction that this is not the case and therefore there is a $w\in
S_{i}\subseteq W$ and $u\in S_{j}\subseteq(\cup_{t=1}^{k}S_{t})\setminus W$
such that $\\{u,w\\}$ is an edge of $G$. It must be the case that $S_{i}$ is
low, as otherwise the lowFlag for $W$ would have been set to $0$ and $W$ would
have been placed in $\mathcal{S}^{\prime}$. Thus $S_{i}$ must be low and
therefore by hypothesis for some $A\in\mathcal{A}$ it is the case that
$A(i,j)>0$. This means that at some point in Contract a set containing $S_{i}$
would have been merged with a set containing $S_{j}$, a contradiction to the
fact that $S_{j}\subseteq(\cup_{t=1}^{k}S_{t})\setminus W$.

The fact that $\mathcal{S}\cup\mathcal{C}$ is a partition of
$\cup_{S\in\mathcal{S}}S$ follows because at all times $\cup_{(U,flag)\in L}U$
is equal to $\cup_{S\in\mathcal{S}}S$. This is true when $L$ is first defined,
and is preserved when sets are popped from $L$, merged, and put back into $L$.

Finally, the “moreover” statement holds as if $\text{low}(i)=1$ for all
$S_{i}\in U$ then the lowFlag variable for $U$ will be set to $1$ and
therefore $U$ will be placed into $\mathcal{C}$ on Line 21. ∎

###  5.2 The shrink subroutine

We now package Approximate Degree Sequence, Learn Low, Reduce High, and
Contract together into our algorithm for finding the connected components of a
graph.

######  Lemma 43.

Let $\mathcal{S}$ be a valid set of connected supervertices and
$d\in\mathbb{N}$ be a degree parameter given as input to Algorithm 6. Then
except with probability $O(\log(n)/n)$ the following two statements hold.

  1. 1.

Algorithm 6 outputs sets of supervertices $\mathcal{S}^{\prime},\mathcal{C}$
such that

    1. (a)

$|\mathcal{S}^{\prime}|\leq
512\left\lceil\log(|\mathcal{S}|)\right\rceil\ln(n)|\mathcal{S}|/d$.

    2. (b)

All supervertices in $\mathcal{S}^{\prime}$ are connected.

    3. (c)

All supervertices in $\mathcal{C}$ are connected components.

    4. (d)

$\mathcal{S}^{\prime}\cup\mathcal{C}$ is a partition of
$\cup_{S\in\mathcal{S}}S$.

  2. 2.

The total number of cut queries made is $O(\log(n)^{5}+d\log(n)^{3})$.

###### Proof.

All of Approximate Degree Sequence, Reduce High, and Learn Low have error
probability at most $O(1/n)$. As they are called at most $O(\log n)$ times,
with probability at least $1-O(\log n/n)$ they will all return as promised. We
now argue correctness assuming this is the case.

Let us establish that the hypotheses of Lemma 42 hold when Contract is called
on Line 18. By assumption all supervertices in $\mathcal{S}$ are connected,
thus Item (1) holds. Also, as we are in the case where Reduce High and Learn
Low perform correctly, Item (2) holds. If $\text{low}(i)=1$ in the call to
Contract then for all $j,b$ for which $S_{i}\in\mathcal{L}_{j,b}$ it holds
that $\vec{g}(i)<d$, and thus the corresponding call to Learn Low learns all
neighbors of $S_{i}$ in $\mathcal{R}_{j,b}$. As this is true for all $j,b$, we
learn all neighbors of $S_{i}$, meaning that Item (3) also holds. As the
hypotheses to Lemma 42 hold, this means all supervertices in
$\mathcal{S}^{\prime}$ are connected, $\mathcal{C}$ contains connected
components, and $\mathcal{S}^{\prime}\cup\mathcal{C}$ is a partition of
$\cup_{S\in\mathcal{S}}S$, establishing Items 1(b),(c),(d).

We now turn to establish Item 1(a) of the lemma. Let

$\mathcal{R}=\\{S_{i}\in\mathcal{S}:\exists
j\in\\{1,\ldots,\left\lceil\log|\mathcal{S}|\right\rceil\\},b\in\\{0,1\\}\mbox{
such that }B_{j,b}(:,i)\neq\vec{0}\\}\enspace.$

In words, $\mathcal{R}$ is the set of all $S_{i}$ for which the $i^{th}$
column of some $B_{j,b}$ matrix is nonzero. By Lemma 41, $|\mathcal{R}|\leq
512\left\lceil\log(|\mathcal{S}|)\right\rceil\ln(n)|\mathcal{S}|/d$. We show
that for every $U\in\mathcal{S}^{\prime}$ there is an $R\in\mathcal{R}$ with
$R\subseteq U$. This will establish Item 1(a) since $\mathcal{S}^{\prime}$ is
a valid set of supervertices.

By the “moreover” statement of Lemma 42, for every $U\in\mathcal{S}^{\prime}$
there is an $S_{i}\subseteq U$ with $\text{low}(i)=0$. Thus for some $j,b$ it
holds that $S_{i}\in\mathcal{L}_{j,b}$ and the degree of $S_{i}$ into
$\mathcal{R}_{j,b}$ is at least $d/4$. By Lemma 41 the corresponding call to
Reduce High on Line 11 will find a neighbor $R\in\mathcal{R}$ of $S_{i}$.
Therefore, in the call to Contract a set containing $S_{i}$ will be merged
with a set containing $R$ and therefore $R\subseteq U$.

Finally, the total number of iterations from the two for loops is $O(\log n)$.
Let us now look at the complexity of each iteration of the inner for loop.
Approximate Degree Sequence with error probability at most $1/n$ takes
$O(\log(n)^{3})$ many queries by Corollary 38. Each call to Reduce High takes
$O(\log(n)^{4})$ many queries by Lemma 41. Each call to Learn Low with error
probability $1/n$ takes $O(d\log(n)^{2})$ many queries by Corollary 39. This
gives the complexity $O(\log(n)^{5}+d\log(n)^{3})$ as claimed in item (2). ∎

######  Theorem 44.

Let $G$ be a graph with vertex set $V$ where $|V|=n$. There is a quantum
algorithm that outputs the connected components of $G$ with error probability
at most $O(\log(n)^{2}/n)$ after making $O(\log(n)^{6})$ many cut queries. In
particular, the algorithm determines if $G$ is connected or not with the same
number of cut queries.

###### Proof.

The algorithm is given by Algorithm 7. Shrink is called with a degree
parameter $d$ of $1024\left\lceil\log(n)\right\rceil^{2}$, thus by item 1(a)
of Lemma 43 the size of the set $\mathcal{S}$ will decrease by a factor of at
least $2$ in each iteration. Therefore the number of iterations of the repeat
loop will be $O(\log n)$. This, together with item (3) of Lemma 43 gives a
bound on the total number of queries of $O(\log(n)^{6})$.

Now we argue correctness. By Lemma 43, at each stage of the algorithm we
maintain the invariant that $\mathcal{S}$ contains connected supervertices,
ConComp contains connected components, and $\mathcal{S}\cup\text{ConComp}$ is
a partition of $V$. The repeat-until loop will terminate as $|\mathcal{S}|$ is
halved with every iteration. When it does terminate $\mathcal{S}=\emptyset$,
thus at this stage ConComp is a partition of $V$ by sets that are connected
components. ∎

##  6 Spanning forest

In this section we show that Algorithm 7 to find connected components can be
extended to give an algorithm that finds a spanning forest and still only
makes polylogarithmically many cut queries. The key idea for this is to find
witnesses for superedges found in Algorithm 7.

######  Definition 45 (Witness).

Let $G=(V,E)$ be a graph and $S_{i},S_{j}$ two supervertices of $G$ connected
by a superedge. We say that $\\{u,v\\}$ is a witness for this superedge if
$u\in S_{i},v\in S_{j}$ and $\\{u,v\\}\in E$.

Let $T_{1},T_{2}$ be spanning trees for connected supervertices $S_{1},S_{2}$,
and let $\\{u,v\\}$ be a witness for a superedge between $S_{1}$ and $S_{2}$.
Then $T_{1}\cup T_{2}\cup\\{\\{u,v\\}\\}$ is a spanning tree for $S_{1}\cup
S_{2}$. The spanning forest algorithm proceeds in the same framework as
Algorithm 7, but now we maintain a spanning tree for each supervertex in
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and only merge supervertices when we
have a witness for a superedge between them. In this way, we are able to
maintain spanning trees for every supervertex in $\mathcal{S}$ as the
algorithm proceeds. The main new difficulty is to find witnesses for the
superedges discovered in Algorithm 7, as there we only discovered the
existence of an edge between supervertices. However, we show that one can
still manage to find enough witnesses to guarantee the size of $\mathcal{S}$
shrinks by a factor of $1/2$ in each round.

First we show how to find a witness for each superedge in a bipartite graph if
both sides of supervertices have low superdegree.

Algorithm 8 Witness Low-Low$(\mathcal{S},\mathcal{T},h,\delta)$

Input: Disjoint valid sets of supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\},\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$,
a degree parameter $h$ such that $\deg_{\mathcal{T}}(S_{i})\leq h$ for all
$S_{i}\in\mathcal{S}$ and $\deg_{\mathcal{S}}(T_{j})\leq h$ for all
$T_{j}\in\mathcal{T}$, and an error parameter $\delta$.
Output: A $|\cup_{i=1}^{k}S_{i}|$-by-$|\cup_{i=1}^{\ell}T_{i}|$ Boolean matrix
$C$ such that $C(u,v)=1$ implies $\\{u,v\\}\in E$ and for every superedge
$(S_{i},T_{j})$ there is a witness $\\{u,v\\}$ with $C(u,v)=1$.

1:$U\leftarrow\cup_{i=1}^{k}S_{i},U=\\{u_{1},\ldots,u_{|U|}\\}$

2:$Y\leftarrow\cup_{i=1}^{\ell}T_{i}$

3:$C\leftarrow\mathrm{zeros}(|U|,|Y|)$

4:$B\leftarrow\text{Learn Low}(\tilde{U},\mathcal{T},h,\delta/2)$
$\triangleright$ Recall $\tilde{U}=\\{\\{u\\}:u\in U\\}$

5:$X\leftarrow\\{u_{a}\in U:(\exists j~{}(B(a,j)>0)\mbox{ AND }(u_{a}\in
S_{i},u_{b}\in S_{i},b<a)\Rightarrow B(b,j)=0)\\}$

6:$D\leftarrow\text{Learn Low}(\tilde{Y},\tilde{X},h^{2},\delta/2)$

7:$C(\mathrm{ind}(X),:)=D^{T}$

8:return $C$

######  Lemma 46 (Witness Low-Low).

Let
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\},\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$
be disjoint valid sets of supervertices in an $n$-vertex graph $G=(V,E)$.
Suppose that $\deg_{\mathcal{T}}(S_{i})\leq h$ for all $S_{i}\in\mathcal{S}$
and $\deg_{\mathcal{S}}(T_{j})\leq h$ for all $T_{j}\in\mathcal{T}$. Algorithm
Witness Low-Low$(\mathcal{S},\mathcal{T},h,\delta)$ (Algorithm 8) makes
$O((h^{2}\log(n/h)+\log(1/\delta))\log(n))$ many cut queries and finds a
witness for every superedge between $\mathcal{S}$ and $\mathcal{T}$, except
with probability $\delta$.

###### Proof.

Let $U=\cup_{i=1}^{k}S_{i}$, and $Y=\cup_{i=1}^{\ell}T_{i}$. Let
$u_{1}<\cdots<u_{|U|}$ be an ordering of the elements of $U$. Let $B$ be a
$|U|$-by-$\ell$ matrix where $B(a,j)=|E(u_{a},T_{j})|$ for
$a\in\\{1,\ldots,|U|\\},j\in\\{1,\ldots,\ell\\}$. Note that every row of $B$
has at most $h$ nonzero entries. By Corollary 39, Learn
Low$(\tilde{U},\mathcal{T},h,\delta/2)$ will return $B$ except with
probability at most $\delta/2$, and makes
$O((h\log(n/h)+\log(1/\delta))\log(n))$ many cut queries. Now let
$X=\\{u_{a}\in U:\exists j~{}(B(a,j)>0\mbox{ AND }(u_{a}\in S_{i},u_{b}\in
S_{i},b<a)\Rightarrow B(b,j)=0)\\}$. In other words, for every $i,j$ for which
there exists $u_{a}\in S_{i}$ with $B(a,j)>0$ we choose the least such $u_{a}$
to put in the set $X$. Note that $|X\cap S_{i}|\leq h$ for every
$S_{i}\in\mathcal{S}$.

Let $D$ be the $|Y|$-by-$|X|$ biadjacency matrix of the graph between $Y$ and
$X$. Every row will have at most $h^{2}$ ones, since
$\deg_{\mathcal{S}}(T_{j})\leq h$ and $|X\cap S_{i}|\leq h$. Learn
Low$(\tilde{Y},\tilde{X},h^{2},\delta/2)$ learns $D$ with
$O((h^{2}\log(n/h)+\log(1/\delta))\log(n))$ many cut queries with error
probability $\delta/2$. By learning $D$, for every superedge $(S_{i},T_{j})$
we find a $u\in S_{i},v\in T_{j}$ with $\\{u,v\\}\in E$. The total error
probability is at most $\delta$. ∎

Next we show that we can find witnesses for supervertices on the left hand
side of a bipartite graph between supervertices where all supervertices on the
left hand side have low superdegree.

Algorithm 9 Witness Low-High$(\mathcal{S},\mathcal{T},h)$

Input: Disjoint valid sets of supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\},\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$,
a degree parameter $h$ such that $\deg_{\mathcal{T}}(S_{i})\leq h$ for all
$S_{i}\in\mathcal{S}$.
Output: A $|\cup_{i}S_{i}|$-by-$|\cup_{j}T_{j}|$ matrix $C$ such that
$C(a,b)=1$ implies $(u_{a},v_{b})\in E$ and for every $S_{i}$ with
$\deg_{\mathcal{T}}(S_{i})>0$ there is a $u_{a}\in
S_{i},v_{b}\in\cup_{j}T_{j}$ such that $C(a,b)=1$.

1:$U\leftarrow\cup_{i=1}^{k}S_{i}$

2:$Y\leftarrow\cup_{i=1}^{\ell}T_{i}$

3:$C\leftarrow\mathrm{zeros}(|U|,|Y|)$

4:$B\leftarrow\text{Learn Low}(\tilde{U},\mathcal{T},h,1/n)$ $\triangleright$
$\tilde{U}=\\{\\{u\\}:u\in U\\}$

5:$X\leftarrow\\{u_{a}\in U:(\exists j~{}B(a,j)>0)\mbox{ AND }(u_{a}\in
S_{i},u_{b}\in S_{i},b<a)\Rightarrow\forall c~{}B(b,c)=0)\\}$

6:for $u\in X$ do

7: $j^{*}(u_{a})=\operatorname*{arg\,max}_{j\in\\{1,\ldots,\ell\\}}B(a,j)$

8:end for

9:for $q=0,\ldots,\left\lceil\log|Y|\right\rceil$ do

10: $X_{q}\leftarrow\\{u\in X:2^{q-1}<B(u,{j^{*}(u)})\leq 2^{q}\\}$

11: $R_{q}\leftarrow$ Randomly sample $\left\lceil
16|Y|\ln(|X_{q}|n)/2^{q}\right\rceil$ many elements from $Y$ with replacement

12: $C(\mathrm{ind}(X_{q}),\mathrm{ind}(R_{q}))\leftarrow\text{Learn
Low}(X_{q},R_{q},192h\ln(n),1/n)$

13:end for

14:return $C$

######  Lemma 47 (Witness Low-High).

Let $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ and
$\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$ be disjoint valid sets of
supervertices in an $n$-vertex graph $G=(V,E)$, and suppose that
$\deg_{\mathcal{T}}(S_{i})\leq h$ for all $S_{i}\in\mathcal{S}$. Algorithm
Witness Low-High$(\mathcal{S},\mathcal{T},h)$ (Algorithm 9) makes
$O(h\log(n)^{4})$ many cut queries and except with probability $O(\log(n)/n)$
outputs a $|\cup_{i}S_{i}|$-by-$|\cup_{j}T_{j}|$ matrix $C$ such that

  1. 1.

$C(a,b)=1$ implies $\\{u_{a},v_{b}\\}\in E$

  2. 2.

For every $S_{i}$ with $\deg_{\mathcal{T}}(S_{i})>0$ there is a $u_{a}\in
S_{i},v_{b}\in\cup_{j}T_{j}$ such that $C(a,b)=1$.

###### Proof.

Let $U=\cup_{i=1}^{k}S_{i}$ and let $u_{1}<\cdots<u_{|U|}$ be an ordering of
the elements of $U$. The algorithm first performs $B\leftarrow\text{Learn
Low}(\tilde{U},\mathcal{T},h,1/n)$. By the correctness of Learn Low from
Corollary 39, except with probability $1/n$, it will hold that
$B(a,j)=|E(u_{a},T_{j})|$ for all
$a\in\\{1,\ldots,|U|\\},j\in\\{1,\ldots,\ell\\}$. This step takes
$O(h\log(n/h)\log(n))$ cut queries. We henceforth assume that this step was
performed correctly. Define $X=\\{u_{a}\in U:(\exists j~{}B(a,j)>0)\mbox{ AND
}((u_{a}\in S_{i},u_{b}\in S_{i},b<a)\Rightarrow\forall c~{}B(b,c)=0)\\}$. In
other words, for every $S_{i}$ we take the first $u_{a}\in S_{i}$ for which
there is a $j\in\\{1,\ldots,\ell\\}$ such that $B(a,\ell)>0$, if such a
$u_{a}$ exists. Let
$j^{*}(u_{a})=\operatorname*{arg\,max}_{j\in\\{1,\ldots,\ell\\}}B(a,j)$ for
each $u_{a}\in X$. For each $u\in X$, we are going to learn a $v\in
T_{j^{*}(u)}$ such that $\\{u,v\\}\in E$.

Fix a value of $q$ in the for loop starting on line 9. For every $u_{a}\in
X_{q}$ and $j\in\\{1,\ldots,\ell\\}$ we have $B(a,j)\leq B(a,j^{*}(u_{a}))\leq
2^{q}$. For $\delta=1/n^{2}$, $R_{q}$ is formed by randomly sampling with
replacement $\left\lceil 8|Y|\ln(|X_{q}|/\delta)/2^{q}\right\rceil$ elements
of $Y$. Thus by Lemma 8 and a union bound over $j\in\\{1,\ldots,\ell\\}$,
except with probability $1/n$, we have

$|E(u,R_{q}\cap T_{j})|\leq 192\ln(n)\mbox{ for all
}j\in\\{1,\ldots,\ell\\}\mbox{ and }u\in X_{q}\enspace.$ (1)

Similarly, except with probability $1/n$, we also have

$|E(u,R_{q}\cap T_{j})|>0\mbox{ for all }j\in\\{1,\ldots,\ell\\}\mbox{ and
}u\in X_{q}\mbox{ with }2^{q-1}<B(u,j)\enspace.$

In particular, except with probability $1/n$

$|E(u,R_{q}\cap T_{j}^{*}(u))|>0\mbox{ for all }u\in X_{q}\enspace.$ (2)

We now add $O(1/n)$ to the error probability and assume for the rest of the
proof that Eq. 1 and Eq. 2 hold. Next the algorithm performs

$C(\mathrm{ind}(X_{q}),\mathrm{ind}(R_{q}))\leftarrow\text{Learn
Low}(X_{q},R_{q},192h\ln(n),1/n)\enspace.$

By Eq. 1, the upper bound on the degree passed to Learn Low is valid, thus by
Corollary 39 Learn Low returns the biadjacency matrix between $X_{q}$ and
$R_{q}$, except with probability $1/n$. In particular, except with probability
$1/n$, if $C(a,b)=1$ for $a\in\mathrm{ind}(X_{q}),b\in\mathrm{ind}(R_{q})$
then $\\{u_{a},v_{b}\\}\in E$ and by Eq. 2 for every $u_{a}\in X_{q}$ there is
$v_{b}\in R_{q}$ such that $C(a,b)=1$. This step requires
$O(h\log(n)^{2}\log(n/h))$ many cut queries.

Finally, by a union bound over $q=0,\ldots,\left\lceil\log|Y|\right\rceil$,
the probability of an error in any iteration of the for loop is at most
$O(\log(n)/n)$. As every $u\in X$ will be in $X_{q}$ for some value of $q$,
for every $S_{i}$ with $\deg_{T}(S_{i})>0$ we will find a $u\in S_{i}$ and
$v\in Y$ with $\\{u,v\\}\in E$. The total error probability is $O(\log(n)/n)$,
and total number of queries is $O(h\log(n)^{4})$. ∎

Next we show how to find witnesses for supervertices of high superdegree.

Algorithm 10 Witness Reduce High$(\mathcal{S},\mathcal{T},d,\vec{g})$

Input: Disjoint valid sets of supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\},\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$
of an $n$-vertex graph $G$, a degree parameter $d$ such that
$\deg_{\mathcal{T}}(S_{i})\geq d$ for all $S_{i}\in\mathcal{S}$, and a vector
$\vec{g}\in\mathbb{Z}^{k}$ such that
$\vec{g}(i)i/4\leq\deg_{\mathcal{T}}(S_{i})\leq 2\vec{g}(i)$ for all
$i\in\\{1,\ldots,k\\}$.
Output: A $|\cup_{i=1}^{k}S_{i}|$-by-$|\cup_{i=1}^{\ell}T_{i}|$ Boolean matrix
$C$ such that $C(u,v)=1$ implies $\\{u,v\\}\in E$ and for every $S_{i}$ there
is a $u\in S_{i},v\in\cup_{j}T_{j}$ such that $C(u,v)=1$.

1:$C\leftarrow\mathrm{zeros}(|\cup_{i=1}^{k}S_{i}|,|\cup_{i=1}^{\ell}T_{i}|)$

2:for $q=\lfloor\log d\rfloor-1$ to $\left\lceil\log\ell\right\rceil+2$ do

3: $\mathcal{H}_{q}=\\{S_{i}\in\mathcal{S}:2^{q-1}<\vec{g}(i)\leq 2^{q}\\}$

4: $\mathcal{R}_{q}\leftarrow$ Randomly choose
$\frac{16\ell\ln(|\mathcal{H}_{q}|n)}{2^{q}}$ supervertices in $\mathcal{T}$,
with replacement

5: $C(\mathrm{ind}(\mathcal{H}_{q}),\mathrm{ind}(\mathcal{R}_{q}))\leftarrow$
Witness Low-High$(\mathcal{H}_{q},\mathcal{R}_{q},192\ln(n))$

6:end for

7:return $B$

######  Lemma 48 (Witness Reduce High).

Let
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\},\mathcal{T}=\\{T_{1},\ldots,T_{\ell}\\}$
be disjoint valid sets of supervertices of an $n$-vertex graph $G$. Let
$d\in\mathbb{N}$ be a degree parameter and $\vec{g}\in\mathbb{R}^{k}$ be a
good estimate of
$(\deg_{\mathcal{T}}(S_{1}),\ldots,\deg_{\mathcal{T}}(S_{k}))$. Further
suppose that $\deg_{\mathcal{T}}(S_{i})\geq d$ for all $S_{i}\in\mathcal{S}$.
On input $\mathcal{S},\mathcal{T},d,\vec{g}$, Witness Reduce High (Algorithm
10) makes $O(\log(n)^{5})$ many cut queries and with probability at least
$1-O(\log(n)^{2}/n)$ outputs a $|\cup_{i}S_{i}|$-by-$|\cup_{j}T_{j}|$ Boolean
matrix $C$ such that

  1. 1.

For every $S_{i}\in\mathcal{S}$, there exists $u\in S_{i}$ and
$v\in\cup_{j}T_{j}$ such that $C(u,v)=1$.

  2. 2.

If $C(u,v)=1$ then $\\{u,v\\}\in E$.

  3. 3.

$|\\{T_{j}:\exists u\in\cup_{i}S_{i},\exists v\in
T_{j}:C(u,v)=1\\}|\leq\frac{256\ell\log(n)}{d}$.

###### Proof.

We first show item (2). By Lemma 47, except with probability $O(\log(n)/n)$,
the call to Witness Low-High on Line 5 will only return valid edges in $G$. As
there are $O(\log n)$ iterations of the for loop, item (2) will therefore hold
except with probability $O(\log(n)^{2}/n)$.

We now show items (1) and (3), assuming that all calls to Witness Low-High
return correctly. The only difference between Reduce High and Witness Reduce
High is that in Line 5 of Witness Reduce-High we call Witness Low-High instead
of Learn Low. As Witness Low-High returns correctly, by Lemma 47 this means we
find a witness for every superedge found by Learn Low, and therefore a witness
for every superedge found by Reduce High. By Item (1) of Lemma 41 for every
$S_{i}\in\mathcal{S}$ Reduce High finds a $T_{j}\in\mathcal{T}$ such that
$(S_{i},T_{j})$ is a superedge. Finding a witness for each of these superedges
gives Item (1) here.

Furthermore, we do not find witnesses for any superedges not found in Reduce
High. Thus Item (3) of Lemma 41 implies Item (3) here.

Finally, we bound the number of queries made. There are $O(\log n)$ iterations
of the for loop, and in each iteration queries are only made in the call to
Witness Low-High. Each of these calls take $O(\log(n)^{4})$ cut queries, thus
the total number of cut queries is $O(\log(n)^{5})$. ∎

Next we show how to contract supervertices by using the edges found so far.

######  Lemma 49.

Let $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ be a valid set of supervertices
with $N=|\cup_{i=1}^{k}S_{i}|$, $\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$ a set
of spanning trees, $\mathcal{A}$ a list of $N$-by-$N$ weighted adjacency
matrices, and $low\in\\{0,1\\}^{k}$ a Boolean vector with the following
properties:

  1. 1.

Every supervertex in $\mathcal{S}$ is connected, and a spanning tree for
$S_{i}\in\mathcal{S}$ is given by $P_{i}\in\mathcal{P}$.

  2. 2.

For every $A\in\mathcal{A}$ if $A(u,v)=1$ then $\\{u,v\\}\in E$.

  3. 3.

For every $i\in\\{1,\ldots,k\\}$ with $low(i)=1$, it holds that for every
$j\in\\{1,\ldots,k\\}$ such that there is a superedge between $S_{i}$ and
$S_{j}$, there is a $u\in S_{i},v\in S_{j}$ and $A\in\mathcal{A}$ with
$A(u,v)=1$.

The algorithm Witness Contract$(\mathcal{S},\mathcal{P},\mathcal{A},low)$
given in Algorithm 11 makes no queries and outputs sets of supervertices
$\mathcal{S}^{\prime}=\\{S_{1}^{\prime},\ldots,S_{\ell}^{\prime}\\},\mathcal{C}=\\{C_{1},\ldots,C_{t}\\}$
and sets of spanning trees
$\mathcal{P}_{\mathcal{S}^{\prime}}=\\{P_{1}^{\prime},\ldots,P_{\ell}^{\prime}\\},\mathcal{P}_{\mathcal{C}}=\\{Q_{1},\ldots,Q_{t}\\}$
such that

  * •

Each $S_{i}^{\prime}\in\mathcal{S}^{\prime}$ is connected and a spanning tree
for it is given by $P_{i}^{\prime}\in\mathcal{P}_{\mathcal{S}^{\prime}}$.

  * •

Each $C_{i}\in\mathcal{C}$ is a connected component and a spanning tree for it
is given by $Q_{i}\in\mathcal{P}_{\mathcal{C}}$.

  * •

$\mathcal{S}^{\prime}\cup\mathcal{C}$ is a partition of
$\cup_{S\in\mathcal{S}}S$.

  * •

For every $U\in\mathcal{S}^{\prime}$ there is an $S_{i}\subseteq U$ with
$low(i)=0$.

Algorithm 11 Witness Contract$(\mathcal{S},\mathcal{P},\mathcal{A},low)$

Input: Valid set of connected supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$, a set of spanning trees
$\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$, a list of $N$-by-$N$ weighted
adjacency matrices $\mathcal{A}=(A_{1},\ldots,A_{m})$ with rows and columns
labeled by elements of $[N]$, a vector $low\in\\{0,1\\}^{k}$ indicating if
each set $S_{i}$ is low.
Output: Sets of supervertices $\mathcal{S}^{\prime},\mathcal{C}$ and sets of
spanning trees for them
$\mathcal{P}_{\mathcal{S}^{\prime}},\mathcal{P}_{\mathcal{C}}$, where each
supervertex in $\mathcal{S}^{\prime},\mathcal{C}$ is connected, and moreover
the supervertices in $\mathcal{C}$ are connected components.

1:$L\leftarrow[(S_{i},P_{i},low(i)):i\in\\{1,\ldots,k\\}]$

2:for $A\in\mathcal{A}$ do

3: for $\\{u,v\\}\in[N]^{(2)}$ do

4: if $A(u,v)=1$ then

5: Pop $(U,T_{1},flag1)\in L$ such that $u\in S_{i}\subseteq U$

6: Pop $(W,T_{2},flag2)\in L$ such that $v\in S_{j}\subseteq W$

7: $U\leftarrow U\cup W$

8: $T=T_{1}\cup T_{2}\cup\\{\\{u,v\\}\\}$

9: $lowFlag=flag1\wedge flag2$

10: Append $(U,T,lowFlag)$ to $L$

11: end if

12: end for

13:end for

14:$\mathcal{S}^{\prime}\leftarrow\emptyset,\mathcal{P}_{\mathcal{S}^{\prime}}\leftarrow\emptyset$

15:$\mathcal{C}\leftarrow\emptyset,\mathcal{P}_{\mathcal{C}}\leftarrow\emptyset$

16:for $(U,T,lowFlag)\in L$ do

17: if lowFlag = 0 then

18: $\mathcal{S}^{\prime}\leftarrow\mathcal{S}^{\prime}\cup\\{U\\}$

19:
$\mathcal{P}_{\mathcal{S}^{\prime}}\leftarrow\mathcal{P}_{\mathcal{S}^{\prime}}\cup\\{T\\}$

20: else

21: $\mathcal{C}\leftarrow\mathcal{C}\cup\\{U\\}$

22: $\mathcal{P}_{\mathcal{C}}\leftarrow\mathcal{P}_{\mathcal{C}}\cup\\{T\\}$

23: end if

24:end for

25:return
$\mathcal{S}^{\prime},\mathcal{P}_{\mathcal{S}^{\prime}},\mathcal{C},\mathcal{P}_{\mathcal{C}}$

Algorithm 12 Witness Shrink$(\mathcal{S},\mathcal{P},d)$

Input: A valid set of connected supervertices
$\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$, a set of spanning trees
$\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$ where $P_{i}$ is a spanning tree for
$S_{i}$, and a degree parameter $d$.
Output: Sets of supervertices $\mathcal{S},\mathcal{C}$ and corresponding sets
of spanning trees $\mathcal{P}_{\mathcal{S}},\mathcal{P}_{\mathcal{C}}$.

1:$low\leftarrow\mathrm{ones}(k,1)$

2:$\mathcal{A}\leftarrow[\;]$

3:$N\leftarrow|\cup_{i=1}^{k}S_{i}|$

4:for $j=1$ to $\left\lceil\log(k)\right\rceil$ do

5: for $b\in\\{0,1\\}$ do

6: $\mathcal{L}_{j,b}=\\{S_{t}\in\mathcal{S}:t_{j}=b\\}$

7: $\mathcal{R}_{j,b}=\\{S_{t}\in\mathcal{S}:t_{j}=1-b\\}$

8: $\vec{g}\leftarrow$ Approximate Degree
Sequence$(\mathcal{L}_{j,b},\mathcal{R}_{j,b},1/n^{2})$

9: $\mathcal{H}\leftarrow\\{S_{t}\in\mathcal{L}_{j,b}:\vec{g}(t)\geq d\\}$

10: $low(\mathrm{ind}(\mathcal{H}))=0$

11: $B_{j,b}\leftarrow\mathrm{zeros}(N,N)$

12:
$B_{j,b}(\cup_{S_{t}\in\mathcal{H}}S_{t},\cup_{S_{t}\in\mathcal{R}_{j,b}}S_{t})\leftarrow$
Witness Reduce High
$(\mathcal{H},\mathcal{R}_{j,b},d/4,\vec{g}(\mathrm{ind}(\mathcal{H})))$

13: $\mathcal{L}\leftarrow\\{S_{t}\in\mathcal{L}_{j,b}:\vec{g}(t)<d\\}$

14: $\vec{f}\leftarrow$ Approximate Degree
Sequence$(\mathcal{R}_{j,b},\mathcal{L},1/n^{2})$

15: $R_{j,b}^{+}\leftarrow\\{S_{t}\in\mathcal{R}_{j,b}:\vec{f}(t)\geq 16d\\}$

16: $R_{j,b}^{-}\leftarrow\\{S_{t}\in\mathcal{R}_{j,b}:\vec{f}(t)<16d\\}$

17:
$C_{j,b}^{+}(\cup_{S_{t}\in\mathcal{L}}S_{t},\cup_{S_{t}\in\mathcal{R}_{j,b}^{+}}S_{t})\leftarrow$
Witness Low-High$(\mathcal{L},\mathcal{R}_{j,b}^{+},2d)$

18: $HasHighNeighbor\leftarrow\\{i:\exists u\in S_{i}\in\mathcal{L},\exists
v\colon C_{j,b}^{+}(u,v)=1\\}$

19: $low(HasHighNeighbor)=0$

20:
$C_{j,b}^{-}(\cup_{S_{t}\in\mathcal{L}}S_{t},\cup_{S_{t}\in\mathcal{R}_{j,b}^{-}}S_{t})\leftarrow$
Witness Low-Low$(\mathcal{L},\mathcal{R}_{j,b}^{-},32d,1/n)$

21: Append $B_{j,b},C_{j,b}^{+},$ and $C_{j,b}^{-}$ to $\mathcal{A}$.

22: end for

23:end for

24:$\mathcal{S},\mathcal{P},\mathcal{C},\mathcal{P}_{\mathcal{C}}\leftarrow$
Witness Contract$(\mathcal{S},\mathcal{P},\mathcal{A})$

25:return $\mathcal{S},\mathcal{P},\mathcal{C},\mathcal{P}_{\mathcal{C}}$

###### Proof.

We first show that each $S_{i}^{\prime}\in\mathcal{S}^{\prime}$ is connected
and a spanning tree for it is given by
$P_{i}^{\prime}\in\mathcal{P}_{\mathcal{S}}$. By assumption each
$S_{i}\in\mathcal{S}$ is connected with a spanning tree given by
$P_{i}\in\mathcal{P}$. We maintain this invariant because we only merge two
supervertices $U,W$ when there is a $u\in U,w\in W$ and a $A\in\mathcal{A}$
with $A(u,w)=1$. By assumption if $A(u,w)=1$ then $\\{u,w\\}\in E$ and thus
$U\cup W$ is connected when $U,W$ are. Furthermore, if $T_{1}$ is a spanning
tree for $U$ and $T_{2}$ is a spanning tree for $W$ then $T_{1}\cup
T_{2}\cup\\{\\{u,w\\}\\}$ is a spanning tree for $U\cup W$.

The same argument shows that each $C_{i}\in\mathcal{C}$ is connected with a
spanning tree given by $P_{i}\in\mathcal{P}_{\mathcal{C}}$.

Next we show that every $W\in\mathcal{C}$ is a connected component. Suppose
for a contradiction that this is not the case and therefore there is a $w\in
S_{i}\subseteq W$ and $u\in S_{j}\subseteq(\cup_{t=1}^{k}S_{t})\setminus W$
such that $\\{u,w\\}$ is an edge of $G$. It must be the case that $S_{i}$ is
low, as otherwise the lowFlag for $W$ would have been set to $0$ and $W$ would
have been placed in $\mathcal{S}^{\prime}$. Thus $S_{i}$ must be low and
therefore by hypothesis for some $w^{\prime}\in S_{i},u^{\prime}\in S_{j}$ and
$A\in\mathcal{A}$ it is the case that $A(w^{\prime},u^{\prime})=1$. This means
that at some point in Witness Contract a set containing $S_{i}$ would have
been merged with a set containing $S_{j}$, a contradiction to the fact that
$S_{j}\subseteq(\cup_{t=1}^{k}S_{t})\setminus W$.

The fact that $\mathcal{S}\cup\mathcal{C}$ is a partition of
$\cup_{S\in\mathcal{S}}S$ follows because at all times $\cup_{(U,T,flag)\in
L}U$ is equal to $\cup_{S\in\mathcal{S}}S$. This is true when $L$ is first
defined, and is preserved when sets are popped from $L$, merged, and put back
into $L$.

Finally, the “moreover” statement holds as if $low(i)=1$ for all $S_{i}\in U$
then the lowFlag variable for $U$ will be set to $1$ and therefore $U$ will be
placed into $\mathcal{C}$ on Line 21. ∎

The last lemma guarantees the shrinkage of the number of supervertices.

######  Lemma 50.

Let $\mathcal{S}=\\{S_{1},\ldots,S_{k}\\}$ be a valid set of connected
supervertices, $\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$ be a set of spanning
trees where $P_{i}$ is a spanning tree for $S_{i}$, and $d\in\mathbb{N}$ be a
degree parameter. Witness Shrink$(\mathcal{S},\mathcal{P},d)$ given by
Algorithm 12 has the following properties:

  1. 1.

Except with probability $O(\log(n)^{3}/n)$, it outputs sets of supervertices
$\mathcal{S}^{\prime},\mathcal{C}$ and sets of spanning trees
$\mathcal{P}_{\mathcal{S}^{\prime}},\mathcal{P}_{\mathcal{C}}$ such that

    1. (a)

$|\mathcal{S}^{\prime}|\leq
512\left\lceil\log(|\mathcal{S}|)\right\rceil\ln(n)|\mathcal{S}|/d$.

    2. (b)

For every supervertex in $\mathcal{S}^{\prime}$ there is a spanning tree for
it in $\mathcal{P}_{\mathcal{S}^{\prime}}$.

    3. (c)

Every supervertex in $\mathcal{C}$ is a connected component and has a spanning
tree for it in $\mathcal{P}_{\mathcal{C}}$.

    4. (d)

$\mathcal{S}^{\prime}\cup\mathcal{C}$ is a partition of
$\cup_{S\in\mathcal{S}}S$.

  2. 2.

The total number of cut queries made is $O(d\log(n)^{5}+d^{2}\log(n)^{3})$.

###### Proof.

We first prove item (2). Queries are only made in the calls to Approximate
Degree Sequence, Witness Reduce High, Witness Low-High, and Witness Low-Low.
Each of these routines is called
$2\left\lceil\log|\mathcal{S}|\right\rceil=O(\log n)$ many times. The query
cost is dominated by Witness Low-High, which takes $O(d\log(n)^{4})$ many
queries, and Witness Low-Low which requires $O(d^{2}\log(n)^{2})$ queries,
resulting in a total of $O(d\log(n)^{5}+d^{2}\log(n)^{3})$ cut queries.

The error probability of the call to Approximate Degree Sequence is $1/n^{2}$,
Witness Reduce High is $O(\log(n)^{2}/n)$, Witness Low-High is $O(\log(n)/n)$,
and Witness Low-Low is $1/n$. Thus the probability that an error occurs in any
of these routines over the course of Witness Shrink is $O(\log(n)^{3}/n)$. We
now argue the points in item (1) hold assuming all of these routines always
return correctly.

We first establish that the hypotheses of Lemma 49 hold when Witness Contract
is called on Line 24. By assumption the supervertices in $\mathcal{S}$ are
connected and spanning trees for them are given in $\mathcal{P}$. The matrices
in $\mathcal{A}$ are produced in calls to Witness Reduce High, Witness Low-
High, and Witness Low-Low. As we are in the case that all of these algorithms
return correctly it follows by Lemma 46,Lemma 47, and Lemma 48 that for every
$A\in\mathcal{A}$ if $A(u,v)=1$ then $\\{u,v\\}\in E$. Finally, we need to
establish that if $low(i)=1$ then $\mathcal{A}$ contains a witness for every
superedge of $S_{i}$. Suppose that $low(i)=1$ and $S_{i}$ has a superedge with
$S_{t}$. For some value of $j,b$ in the for loop we will have
$S_{i}\in\mathcal{L}_{j,b},S_{t}\in\mathcal{R}_{j,b}$. As $low(i)=1$ and
Witness Low-High returns correctly, $S_{i}$ has no neighbors in
$\mathcal{R}_{j,b}^{+}$. Thus it must be the case that
$S_{t}\in\mathcal{R}_{j,b}^{-}$. As $\vec{f},\vec{g}$ are good estimates
because Approximate Degree Sequence returns correctly, the degree bound in the
call to Witness Low-Low is valid and therefore by Lemma 46 a witness for the
$(S_{i},S_{t})$ superedge will be found in the call to Witness Low-Low.

We have now established the hypotheses to Lemma 49 and thus can invoke the
conclusion of Lemma 49 which implies Items 1(b),(c),(d) of the current lemma.

It remains to show Item 1(a). Let

$\mathcal{R}=\\{S_{t}\in\mathcal{S}:\exists j\in\\{1,\ldots,\left\lceil\log
k\right\rceil\\},b\in\\{0,1\\},v\in S_{t}\mbox{ such that
}B_{j,b}(:,v)\neq\vec{0}\\}\enspace.$

By Lemma 48, and the fact that the number of iterations of the for loop is
$2\left\lceil\log|\mathcal{S}|\right\rceil$, we have $|\mathcal{R}|\leq
512\left\lceil\log|\mathcal{S}|\right\rceil\log(n)|\mathcal{S}|/d$. In Witness
Contract, a supervertex $W$ will be put into $\mathcal{S}^{\prime}$ iff for
some $S_{i}\in W$ we have $low(i)=0$. In the next paragraph we show that in
that case Witness Shrink finds witnesses to certify that an element of
$\mathcal{R}$ is in the connected component of $S_{i}$. This means that
Witness Contract will merge $S_{i}$ into a set $W$ containing an element of
$\mathcal{R}$ and therefore the number of supervertices in
$\mathcal{S}^{\prime}$ can be upper bounded by $|\mathcal{R}|$ and will give
Item 1(a).

Take an $S_{i}$ with $low(i)=0$ and consider the iteration $j,b$ of the for
loop where $low(i)$ is set to zero. There are two ways this can happen. The
first is if $\vec{g}(S_{i})\geq d$. In this case $S_{i}$ will be placed into
$\mathcal{H}$ and a witness for a neighbor in $\mathcal{R}$ will be found in
the call to Witness Reduce High by Lemma 48. The second case is that a witness
is found for a superedge between $S_{i}$ and an element
$S_{\ell}\in\mathcal{R}_{j,b}^{+}$. In the $j,1-b$ iteration of the for loop,
$S_{\ell}\in\mathcal{L}_{j,1-b}$ and moreover $\vec{g}(\ell)\geq d$, as
$\vec{f}(\ell)\geq 16d$ for $S_{\ell}$ to be placed in $\mathcal{R}_{j,b}^{+}$
and both are good estimates. Therefore by the previous argument a witness for
a neighbor of $S_{\ell}$ with an element of $\mathcal{R}$ will be found in the
call to Witness Reduce High. Thus we have witnesses that $S_{i}$ is connected
to $S_{\ell}$ and that $S_{\ell}$ is connected to an element of $\mathcal{R}$.
∎

Finally we can give the algorithm of finding a spanning forest with
polylogarithmic many cut queries.

Algorithm 13 Spanning Forest with cut queries

Input: Cut oracle for a graph $G$ on $n$ vertices.
Output: A set $\mathcal{P}=\\{P_{1},\ldots,P_{t}\\}$ containing a spanning
tree for every connected component of $G$.

1:$\mathcal{S}\leftarrow\tilde{V},\mathcal{P}_{\mathcal{S}}\leftarrow\tilde{V}$

2:$\mathcal{P}\leftarrow\emptyset,\text{ConComp}\leftarrow\emptyset$

3:repeat

4:
$(\mathcal{S},\mathcal{P}_{\mathcal{S}},\mathcal{C},\mathcal{P}_{\mathcal{C}})\leftarrow
WitnessShrink(\mathcal{S},\mathcal{P}_{\mathcal{S}},1024\left\lceil\log
n\right\rceil^{2})$

5: $\text{ConComp}\leftarrow\text{ConComp}\cup\mathcal{C}$

6: $\mathcal{P}\leftarrow\mathcal{P}\cup\mathcal{P}_{\mathcal{C}}$

7:until $\mathcal{S}=\emptyset$

8:return $\mathcal{P}$

######  Theorem 51.

Given cut query access to an $n$-vertex graph $G$, there is quantum algorithm
(Algorithm 13) making $O(\log(n)^{8})$ queries that outputs a spanning forest
for $G$ with probability $1-O(\log(n)^{4}/n)$.

###### Proof.

We first argue by induction that the $i^{th}$ time Witness Shrink is called
the hypothesis to Lemma 50 is satisfied with probability at least
$1-(i-1)\log(n)^{3}/n$.

The first time Witness Shrink is called, $\mathcal{S}=\tilde{V}$ and
$\mathcal{P}_{\mathcal{S}}=\tilde{V}$. Thus $\mathcal{P}_{\mathcal{S}}$
provides valid spanning trees for each supervertex in $\mathcal{S}$ and the
hypothesis to Lemma 50 is satisfied. Now suppose the inductive assumption
holds the $i^{th}$ time Witness Shrink is called. Then after the call to
Witness Shrink we know that except with probability $\log(n)^{3}/n$ the output
$\mathcal{S},\mathcal{P}$ satisfy that each supervertex in $\mathcal{S}$ is
connected and has a valid spanning tree for it given in $\mathcal{P}$. Thus in
the $(i+1)^{th}$ call to Witness Shrink the hypothesis to Lemma 50 holds with
probability at least $1-i\log(n)^{3}/n$.

If the hypothesis to Lemma 50 holds in the call to Witness Shrink, then by the
choice of the degree parameter $d=1024\left\lceil\log n\right\rceil^{2}$ the
size of $\mathcal{S}$ will reduce by a factor of $1/2$ with every iteration of
the repeat until loop. Thus with probability at least $1-\log(n)^{4}/n$ every
call to Witness Shrink will return correctly and the number of iterations will
be at most $O(\log(n))$. In this case the total number of queries made will be
$O(\log(n)^{8})$.

If every call to Witness Shrink returns correctly, then the algorithm mantains
the invariant that $\mathcal{S}\cup\text{ConComp}$ is a partition of $V$,
every supervertex in ConComp is a connected component and has a valid spanning
tree in $\mathcal{P}_{\mathcal{C}}$. At the end of the algorithm
$\mathcal{S}=\emptyset$ thus ConComp is contains all connected components of
$G$ and $\mathcal{P}_{\mathcal{C}}$ is a spanning forest. ∎

###  6.1 Applications

With the ability to compute a spanning forest we can also easily solve some
other graph problems in the cut query model.

######  Theorem 52.

There is a quantum algorithm to determine if an $n$-vertex graph $G$ is
bipartite that makes $O(\log(n)^{8})$ many cut queries and succeeds with
probability at least $1-O(\log(n)^{4}/n)$.

###### Proof.

We first invoke Theorem 51 to find a spanning forest for $G$ with
$O(\log(n)^{8})$ many cut queries and success probability
$1-O(\log(n)^{4}/n)$. We then color each root of a spanning tree red, and
proceed to color all the remaining vertices blue and red such that no two
vertices connected in a spanning tree have the same color. The graph is then
bipartite if and only if there is no edge of $G$ between two vertices of the
same color.

We can check if there is an edge between two red vertices with $O(\log(n))$
cut queries. Let $S$ be the set of red vertices. We consider $O(\log n)$
bipartite graphs $(L_{i},R_{i},E_{i})$ where $L_{i}=\\{v\in
S:v_{i}=0\\},R_{i}=\\{v\in S:v_{i}=1\\}$ and $E_{i}=\\{(u,v):u\in L_{i},v\in
R_{i},\\{u,v\\}\in E\\}$. Then with 3 cut queries we can check if
$|E(L_{i},R_{i})|>0$. An edge between two red vertices will be present in at
least one of these bipartite graphs, thus this process will determine if there
is an edge between two red vertices. We then do the same procedure for the
blue vertices. ∎

Similarly we can check if a graph is acyclic.

######  Theorem 53.

There is a quantum algorithm to determine if an $n$-vertex graph $G$ is
acyclic that makes $O(\log(n)^{8})$ many cut queries and succeeds with
probability at least $1-O(\log(n)^{4}/n)$.

###### Proof.

We first check that the graph is bipartite, i.e. that it has no odd cycles,
using Theorem 52. If it is bipartite, then it remains to check that it also
has no even cycles.

To check for even cycles we do the same procedure as in the proof of Theorem
52: we find a spanning forest and color the vertices of the spanning trees red
and blue. Then the graph will have no even cycles if and only if there are no
additional edges between red and blue vertices than those present in the
spanning trees. Let the set of red vertices be $R$ and the set of blue
vertices be $B$. With three cut queries we determine $|E(B,R)|$. We then
compare this to the number of edges between blue and red vertices that in the
spanning forest. There is no even cycle if and only if these numbers are the
same. ∎

#### Remark

In both applications, after finding a spanning forest, the problem essentially
becomes testing graph emptiness: In bipartite testing we need to check the
vertices of the same color form an empty graph, and in acyclic graph testing
we need to check that there is no edge other than those in the found spanning
forest. If a small constant error is tolerated (as opposed to the
$\tilde{O}(1/n)$ one obtained in the above two proofs), then testing graph
emptiness can be done in a constant number of queries. Indeed, a query
$E(S,V\setminus S)$ for a random subset $S\subseteq V$ returns a positive
integer as long as one edge exists, and repeating this
$\lceil\log(1/\epsilon)\rceil$ times gives an error probability of at most
$\epsilon$.

##  7 Concluding remarks

In this paper we investigate the power of additive and cut queries on graphs,
and demonstrate that quantum algorithms using these oracles that can solve
certain graph problems with surprisingly low query cost. Some open questions
are left for future investigation, and we list a few of them here.

  1. 1.

The most pressing problem left open by this work is the quantum complexity of
minimum cut with a cut oracle. Can this be solved with a polylogarithmic
number of queries?

  2. 2.

Classically, the best known lower bounds on the query complexity of minimizing
a submodular function with an evaluation oracle can be shown via the
connectivity problem. We have ruled connectivity out as a candidate for a good
quantum lower bound, and in fact we do not know of any nontrivial lower bound
on the quantum query complexity of minimizing a submodular function. As a
modest challenge, can one give an example of a submodular function whose
minimization problem requires $\Omega(n)$ many evaluation queries by a quantum
algorithm?

  3. 3.

Another interesting problem is the maximization of a submodular function. This
problem is NP-hard in general and classically exponentially large query lower
bounds are known. For example, [FMV11] show that $\exp(\epsilon^{2}n/8)$ many
evaluation oracle queries can be needed by a randomized algorithm even to find
a $(\frac{1}{2}+\epsilon)$-approximation to the maximum value of a submodular
function. What is the quantum query complexity of submodular function
maximization?

## Acknowledgments

We would like to thank Jon Allcock for helpful discussions during the course
of this work and Tongyang Li for useful comments on an earlier version of the
paper. M.S. thanks Yassine Hamoudi for helpful conversations on submodular
function oracles. T.L. thanks the Centre for Quantum Technologies, Singapore
for supporting a visit where this work began. T.L. is supported in part by the
Australian Research Council Grant No: DP200100950. Research at CQT is funded
by the National Research Foundation, the Prime Minister’s Office, and the
Ministry of Education, Singapore under the Research Centres of Excellence
programme’s research grant R-710-000-012-135. In addition, this work has been
supported in part by the QuantERA ERA-NET Cofund project QuantAlgo and the ANR
project ANR-18-CE47-0010 QUDATA.

## References

  * [ABK+04] Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov.  Learning a hidden matching.  SIAM J. Comput., 33(2):487–501, 2004.
  * [AdW19] Simon Apers and Ronald de Wolf.  Quantum speedup for graph sparsification, cut approximation and Laplacian solving.  CoRR, abs/1911.07306, 2019.
  * [BCG+20] Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang.  Symmetries, graph properties, and quantum speedups.  CoRR, abs/2006.12760, 2020.
  * [BCW98] Harry Buhrman, Richard Cleve, and Avi Wigderson.  Quantum vs. classical communication and computation.  In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 63–68. ACM, 1998.
  * [Bel12] Aleksandrs Belovs.  Span programs for functions with constant-sized 1-certificates: extended abstract.  In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 77–84. ACM, 2012.
  * [BFS86] László Babai, Peter Frankl, and Janos Simon.  Complexity classes in communication complexity theory (preliminary version).  In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 337–347, 1986.
  * [BK96] András Benczúr and David R. Karger.  Approximating $s-t$ minimum cuts in $o(n^{2})$ time.  In Proccedings of the 28th Annual ACM SIGACT Symposium on Theory of Computing, STOC 1996, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47–55, 1996.
  * [BM10] Nader H. Bshouty and Hanna Mazzawi.  Toward a deterministic polynomial time algorithm with optimal additive query complexity.  In Petr Hlinený and Antonín Kucera, editors, Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, volume 6281 of Lecture Notes in Computer Science, pages 221–232. Springer, 2010.
  * [BM11] Nader H. Bshouty and Hanna Mazzawi.  Reconstructing weighted graphs with minimal query complexity.  Theor. Comput. Sci., 412(19):1782–1790, 2011.
  * [BV97] Ethan Bernstein and Umesh V. Vazirani.  Quantum complexity theory.  SIAM J. Comput., 26(5):1411–1473, 1997.
  * [CCMP19] Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, and Manaswi Paraashar.  Quantum query-to-communication simulation needs a logarithmic overhead.  CoRR, abs/1909.10428, 2019.
  * [CK10] Sung-Soon Choi and Jeong Han Kim.  Optimal query complexity bounds for finding graphs.  Artif. Intell., 174(9-10):551–569, 2010.