We study the query complexity of determining if a graph is connected with global queries. The first model we look at is matrix-vector multiplication queries to the adjacency matrix. Here, for an $n$-vertex graph with adjacency matrix $A$, one can que
ry a vector $x in {0,1}^n$ and receive the answer $Ax$. We give a randomized algorithm that can output a spanning forest of a weighted graph with constant probability after $O(log^4(n))$ matrix-vector multiplication queries to the adjacency matrix. This complements a result of Sun et al. (ICALP 2019) that gives a randomized algorithm that can output a spanning forest of a graph after $O(log^4(n))$ matrix-vector multiplication queries to the signed vertex-edge incidence matrix of the graph. As an application, we show that a quantum algorithm can output a spanning forest of an unweighted graph after $O(log^5(n))$ cut queries, improving and simplifying a result of Lee, Santha, and Zhang (SODA 2021), which gave the bound $O(log^8(n))$. In the second part of the paper, we turn to showing lower bounds on the linear query complexity of determining if a graph is connected. If $w$ is the weight vector of a graph (viewed as an $binom{n}{2}$ dimensional vector), in a linear query one can query any vector $z in mathbb{R}^{n choose 2}$ and receive the answer $langle z, wrangle$. We show that a zero-error randomized algorithm must make $Omega(n)$ linear queries in expectation to solve connectivity. As far as we are aware, this is the first lower bound of any kind on the unrestricted linear query complexity of connectivity. We show this lower bound by looking at the linear query emph{certificate complexity} of connectivity, and characterize this certificate complexity in a linear algebraic fashion.
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication
matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
The minimum cut problem in an undirected and weighted graph $G$ is to find the minimum total weight of a set of edges whose removal disconnects $G$. We completely characterize the quantum query and time complexity of the minimum cut problem in the ad
jacency matrix model. If $G$ has $n$ vertices and edge weights at least $1$ and at most $tau$, we give a quantum algorithm to solve the minimum cut problem using $tilde O(n^{3/2}sqrt{tau})$ queries and time. Moreover, for every integer $1 le tau le n$ we give an example of a graph $G$ with edge weights $1$ and $tau$ such that solving the minimum cut problem on $G$ requires $Omega(n^{3/2}sqrt{tau})$ many queries to the adjacency matrix of $G$. These results contrast with the classical randomized case where $Omega(n^2)$ queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when $G$ has $m$ edges the classical randomized complexity of the minimum cut problem is $tilde Theta(m)$. We show that the quantum query and time complexity are $tilde O(sqrt{mntau})$ and $tilde O(sqrt{mntau} + n^{3/2})$, respectively, where again the edge weights are between $1$ and $tau$. For dense graphs we give lower bounds on the quantum query complexity of $Omega(n^{3/2})$ for $tau > 1$ and $Omega(tau n)$ for any $1 leq tau leq n$. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Kargers tree packing technique (STOC 1996).
Let $G = (V,w)$ be a weighted undirected graph with $m$ edges. The cut dimension of $G$ is the dimension of the span of the characteristic vectors of the minimum cuts of $G$, viewed as vectors in ${0,1}^m$. For every $n ge 2$ we show that the cut dim
ension of an $n$-vertex graph is at most $2n-3$, and construct graphs realizing this bound. The cut dimension was recently defined by Graur et al. cite{GPRW20}, who show that the maximum cut dimension of an $n$-vertex graph is a lower bound on the number of cut queries needed by a deterministic algorithm to solve the minimum cut problem on $n$-vertex graphs. For every $nge 2$, Graur et al. exhibit a graph on $n$ vertices with cut dimension at least $3n/2 -2$, giving the first lower bound larger than $n$ on the deterministic cut query complexity of computing mincut. We observe that the cut dimension is even a lower bound on the number of emph{linear} queries needed by a deterministic algorithm to solve mincut, where a linear query can ask any vector $x in mathbb{R}^{binom{n}{2}}$ and receives the answer $w^T x$. Our results thus show a lower bound of $2n-3$ on the number of linear queries needed by a deterministic algorithm to solve minimum cut on $n$-vertex graphs, and imply that one cannot show a lower bound larger than this via the cut dimension. We further introduce a generalization of the cut dimension which we call the $ell_1$-approximate cut dimension. The $ell_1$-approximate cut dimension is also a lower bound on the number of linear queries needed by a deterministic algorithm to compute minimum cut. It is always at least as large as the cut dimension, and we construct an infinite family of graphs on $n=3k+1$ vertices with $ell_1$-approximate cut dimension $2n-2$, showing that it can be strictly larger than the cut dimension.
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 a
ll 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.
The negative weight adversary method, $mathrm{ADV}^pm(g)$, is known to characterize the bounded-error quantum query complexity of any Boolean function $g$, and also obeys a perfect composition theorem $mathrm{ADV}^pm(f circ g^n) = mathrm{ADV}^pm(f) m
athrm{ADV}^pm(g)$. Belovs gave a modified version of the negative weight adversary method, $mathrm{ADV}_{rel}^pm(f)$, that characterizes the bounded-error quantum query complexity of a relation $f subseteq {0,1}^n times [K]$, provided the relation is efficiently verifiable. A relation is efficiently verifiable if $mathrm{ADV}^pm(f_a) = o(mathrm{ADV}_{rel}^pm(f))$ for every $a in [K]$, where $f_a$ is the Boolean function defined as $f_a(x) = 1$ if and only if $(x,a) in f$. In this note we show a perfect composition theorem for the composition of a relation $f$ with a Boolean function $g$ [ mathrm{ADV}_{rel}^pm(f circ g^n) = mathrm{ADV}_{rel}^pm(f) mathrm{ADV}^pm(g) enspace . ] For an efficiently verifiable relation $f$ this means $Q(f circ g^n) = Theta( mathrm{ADV}_{rel}^pm(f) mathrm{ADV}^pm(g) )$.
Let $R_epsilon(cdot)$ stand for the bounded-error randomized query complexity with error $epsilon > 0$. For any relation $f subseteq {0,1}^n times S$ and partial Boolean function $g subseteq {0,1}^m times {0,1}$, we show that $R_{1/3}(f circ g^n) in
Omega(R_{4/9}(f) cdot sqrt{R_{1/3}(g)})$, where $f circ g^n subseteq ({0,1}^m)^n times S$ is the composition of $f$ and $g$. We give an example of a relation $f$ and partial Boolean function $g$ for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity $bar chi(g)$ of a partial Boolean function $g$. We show $bar chi(g) in Omega(sqrt{R_{1/3}(g)})$ for any (partial) function $g$ and $R_{1/3}(f circ g^n) in Omega(R_{4/9}(f) cdot bar chi(g))$; these two bounds imply our composition result. We further show that $bar chi(g)$ is always at least as large as the sabotage complexity of $g$, introduced by Ben-David and Kothari.
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a $k$-Fourier-sparse $n$-bit Boolean function from $O(k^{1.5}(log k)^2)$ uniform quantum examples for that function. This improves over the boun
d of $widetilde{Theta}(kn)$ uniformly random classical examples (Haviv and Regev, CCC15). Our main tool is an improvement of Changs lemma for the special case of sparse functions. Second, we show that if a concept class $mathcal{C}$ can be exactly learned using $Q$ quantum membership queries, then it can also be learned using $Oleft(frac{Q^2}{log Q}log|mathcal{C}|right)$ classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP04) by a $log Q$-factor.
We initiate the study of quantum races, games where two or more quantum computers compete to solve a computational problem. While the problem of dueling algorithms has been studied for classical deterministic algorithms, the quantum case presents add
itional sources of uncertainty for the players. The foremost among these is that players do not know if they have solved the problem until they measure their quantum state. This question of `when to measure? presents a very interesting strategic problem. We develop a game-theoretic model of a multiplayer quantum race, and find an approximate Nash equilibrium where all players play the same strategy. In the two-party case, we further show that this strategy is nearly optimal in terms of payoff among all symmetric Nash equilibria. A key role in our analysis of quantum races is played by a more tractable version of the game where there is no payout on a tie; for such races we completely characterize the Nash equilibria in the two-party case. One application of our results is to the stability of the Bitcoin protocol when mining is done by quantum computers. Bitcoin mining is a race to solve a computational search problem, with the winner gaining the right to create a new block. Our results inform the strategies that eventual quantum miners should use, and also indicate that the collision probability---the probability that two miners find a new block at the same time---would not be too high in the case of quantum miners. Such collisions are undesirable as they lead to forking of the Bitcoin blockchain.
Let $fsubseteq{0,1}^ntimesXi$ be a relation and $g:{0,1}^mto{0,1,*}$ be a promise function. This work investigates the randomised query complexity of the relation $fcirc g^nsubseteq{0,1}^{mcdot n}timesXi$, which can be viewed as one of the most gener
al cases of composition in the query model (letting $g$ be a relation seems to result in a rather unnatural definition of $fcirc g^n$). We show that for every such $f$ and $g$, $$mathcal R(fcirc g^n) in Omega(mathcal R(f)cdotsqrt{mathcal R(g)}),$$ where $mathcal R$ denotes the randomised query complexity. On the other hand, we demonstrate a relation $f_0$ and a promise function $g_0$, such that $mathcal R(f_0)inTheta(sqrt n)$, $mathcal R(g_0)inTheta(n)$ and $mathcal R(f_0circ g_0^n)inTheta(n)$ $-$ that is, our composition statement is tight. To the best of our knowledge, there was no known composition theorem for the randomised query complexity of relations or promise functions (and for the special case of total functions our lower bound gives multiplicative improvement of $sqrt{log n}$).
