Search

The distributed subgraph detection asks, for a fixed graph $H$, whether the $n$-node input graph contains $H$ as a subgraph or not. In the standard CONGEST model of distributed computing, the complexity of clique/cycle detection and listing has received a lot of attention recently. In this paper we consider the induced variant of subgraph detection, where the goal is to decide whether the $n$-node input graph contains $H$ as an \emph{induced} subgraph or not. We first show a $\tilde{\Omega}(n)$ lower bound for detecting the existence of an induced $k$-cycle for any $k\geq 4$ in the CONGEST model. This lower bound is tight for $k=4$, and shows that the induced variant of $k$-cycle detection is much harder than the non-induced version. This lower bound is proved via a reduction from two-party communication complexity. We complement this result by showing that for $5\leq k\leq 7$, this $\tilde{\Omega}(n)$ lower bound cannot be improved via the two-party communication framework. We then show how to prove stronger lower bounds for larger values of $k$. More precisely, we show that detecting an induced $k$-cycle for any $k\geq 8$ requires $\tilde{\Omega}(n^{2-\Theta{(1/k)}})$ rounds in the CONGEST model, nearly matching the known upper bound $\tilde{O}(n^{2-\Theta{(1/k)}})$ of the general $k$-node subgraph detection (which also applies to the induced version) by Eden, Fiat, Fischer, Kuhn, and Oshman~[DISC 2019]. Finally, we investigate the case where $H$ is the diamond (the diamond is obtained by adding an edge to a 4-cycle, or equivalently removing an edge from a 4-clique), and show non-trivial upper and lower bounds on the complexity of the induced version of diamond detecting and listing., Comment: 21 pages. To appear in ISAAC 2021

Recently Brakerski, Christiano, Mahadev, Vazirani and Vidick (FOCS 2018) have shown how to construct a test of quantumness based on the learning with errors (LWE) assumption: a test that can be solved efficiently by a quantum computer but cannot be solved by a classical polynomial-time computer under the LWE assumption. This test has lead to several cryptographic applications. In particular, it has been applied to producing certifiable randomness from a single untrusted quantum device, self-testing a single quantum device and device-independent quantum key distribution. In this paper, we show that this test of quantumness, and essentially all the above applications, can actually be implemented by a very weak class of quantum circuits: constant-depth quantum circuits combined with logarithmic-depth classical computation. This reveals novel complexity-theoretic properties of this fundamental test of quantumness and gives new concrete evidence of the superiority of small-depth quantum circuits over classical computation., LIPIcs, Vol. 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), pages 59:1-59:15

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously known barriers, both in the numerical sense, as well as in its generality. We prove our result using the asymptotic spectrum of tensors. More precisely, we crucially make use of two families of real tensor parameters with special algebraic properties: the quantum functionals and the support functionals. In particular, we prove that any lower bound on the dual exponent of matrix multiplication $\alpha$ via the big Coppersmith-Winograd tensors cannot exceed 0.625.

A recent breakthrough by Ambainis, Balodis, Iraids, Kokainis, Pr\=usis and Vihrovs (SODA'19) showed how to construct faster quantum algorithms for the Traveling Salesman Problem and a few other NP-hard problems by combining in a novel way quantum search with classical dynamic programming. In this paper, we show how to apply this approach to the minimum Steiner tree problem, a well-known NP-hard problem, and construct the first quantum algorithm that solves this problem faster than the best known classical algorithms. More precisely, the complexity of our quantum algorithm is $\mathcal{O}(1.812^k\poly(n))$, where $n$ denotes the number of vertices in the graph and $k$ denotes the number of terminals. In comparison, the best known classical algorithm has complexity $\mathcal{O}(2^k\poly(n))$., Comment: To appear in COCOON 2020

There are two central models considered in (fault-free synchronous) distributed computing: the CONGEST model, in which communication channels have limited bandwidth, and the LOCAL model, in which communication channels have unlimited bandwidth. Very recently, Le Gall and Magniez (PODC 2018) showed the superiority of quantum distributed computing over classical distributed computing in the CONGEST model. In this work we show the superiority of quantum distributed computing in the LOCAL model: we exhibit a computational task that can be solved in a constant number of rounds in the quantum setting but requires $\Omega(n)$ rounds in the classical setting, where $n$ denotes the size of the network., Comment: 14 pages

Recently Bravyi, Gosset and K\"onig (Science 2018) proved an unconditional separation between the computational powers of small-depth quantum and classical circuits for a relation. In this paper we show a similar separation in the average-case setting that gives stronger evidence of the superiority of small-depth quantum computation: we construct a computational task that can be solved on all inputs by a quantum circuit of constant depth with bounded-fanin gates (a "shallow" quantum circuit) and show that any classical circuit with bounded-fanin gates solving this problem on a non-negligible fraction of the inputs must have logarithmic depth. Our results are obtained by introducing a technique to create quantum states exhibiting global quantum correlations from any graph, via a construction that we call the \emph{extended graph}. Similar results have been very recently (and independently) obtained by Coudron, Stark and Vidick (arXiv:1810.04233), and Bene Watts, Kothari, Schaeffer and Tal (STOC 2019)., Comment: 18 pages; accepted to CCC'19; v2: added references, soundness improved (from constant to exponentially small) in the main result; v3: discussion added about the relation with Ref. [BGK18]; v4: corrected typos, footnote 3 removed

The computation of the diameter is one of the most central problems in distributed computation. In the standard CONGEST model, in which two adjacent nodes can exchange $O(\log n)$ bits per round (here $n$ denotes the number of nodes of the network), it is known that exact computation of the diameter requires $\tilde ��(n)$ rounds, even in networks with constant diameter. In this paper we investigate quantum distributed algorithms for this problem in the quantum CONGEST model, where two adjacent nodes can exchange $O(\log n)$ quantum bits per round. Our main result is a $\tilde O(\sqrt{nD})$-round quantum distributed algorithm for exact diameter computation, where $D$ denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model. We also show an unconditional lower bound $\tilde ��(\sqrt{n})$ on the round complexity of any quantum algorithm computing the diameter, and furthermore show a tight lower bound $\tilde ��(\sqrt{nD})$ for any distributed quantum algorithm in which each node can use only $\textrm{poly}(\log n)$ quantum bits of memory., 21 pages; to appear in PODC 2018

In this paper we consider what can be computed by a user interacting with a potentially malicious server, when the server performs polynomial-time quantum computation but the user can only perform polynomial-time classical (i.e., non-quantum) computation. Understanding the computational power of this model, which corresponds to polynomial-time quantum computation that can be efficiently verified classically, is a well-known open problem in quantum computing. Our result shows that computing the order of a solvable group, which is one of the most general problems for which quantum computing exhibits an exponential speed-up with respect to classical computing, can be realized in this model., 13 pages

In the past few years, successive improvements of the asymptotic complexity of square matrix multiplication have been obtained by developing novel methods to analyze the powers of the Coppersmith-Winograd tensor, a basic construction introduced thirty years ago. In this paper we show how to generalize this approach to make progress on the complexity of rectangular matrix multiplication as well, by developing a framework to analyze powers of tensors in an asymmetric way. By applying this methodology to the fourth power of the Coppersmith-Winograd tensor, we succeed in improving the complexity of rectangular matrix multiplication. Let $\alpha$ denote the maximum value such that the product of an $n\times n^\alpha$ matrix by an $n^\alpha\times n$ matrix can be computed with $O(n^{2+\epsilon})$ arithmetic operations for any $\epsilon>0$. By analyzing the fourth power of the Coppersmith-Winograd tensor using our methods, we obtain the new lower bound $\alpha>0.31389$, which improves the previous lower bound $\alpha>0.30298$ obtained five years ago by Le Gall (FOCS'12) from the analysis of the second power of the Coppersmith-Winograd tensor. More generally, we give faster algorithms computing the product of an $n\times n^k$ matrix by an $n^k\times n$ matrix for any value $k\neq 1$. (In the case $k=1$, we recover the bounds recently obtained for square matrix multiplication). These improvements immediately lead to improvements in the complexity of a multitude of fundamental problems for which the bottleneck is rectangular matrix multiplication, such as computing the all-pair shortest paths in directed graphs with bounded weights., Comment: 30 pages

Censor-Hillel et al. [PODC'15] recently showed how to efficiently implement centralized algebraic algorithms for matrix multiplication in the congested clique model, a model of distributed computing that has received increasing attention in the past few years. This paper develops further algebraic techniques for designing algorithms in this model. We present deterministic and randomized algorithms, in the congested clique model, for efficiently computing multiple independent instances of matrix products, computing the determinant, the rank and the inverse of a matrix, and solving systems of linear equations. As applications of these techniques, we obtain more efficient algorithms for the computation, again in the congested clique model, of the all-pairs shortest paths and the diameter in directed and undirected graphs with small weights, improving over Censor-Hillel et al.'s work. We also obtain algorithms for several other graph-theoretic problems such as computing the number of edges in a maximum matching and the Gallai-Edmonds decomposition of a simple graph, and computing a minimum vertex cover of a bipartite graph., 29 pages; accepted to DISC'16

This paper considers the problem of efficiently transmitting quantum states through a network. It has been known for some time that without additional assumptions it is impossible to achieve this task perfectly in general -- indeed, it is impossible even for the simple butterfly network. As additional resource we allow free classical communication between any pair of network nodes. It is shown that perfect quantum network coding is achievable in this model whenever classical network coding is possible over the same network when replacing all quantum capacities by classical capacities. More precisely, it is proved that perfect quantum network coding using free classical communication is possible over a network with $k$ source-target pairs if there exists a classical linear (or even vector linear) coding scheme over a finite ring. Our proof is constructive in that we give explicit quantum coding operations for each network node. This paper also gives an upper bound on the number of classical communication required in terms of $k$, the maximal fan-in of any network node, and the size of the network., 12 pages, 2 figures, generalizes some of the results in arXiv:0902.1299 to the k-pair problem and codes over rings. Appeared in the Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP'09), LNCS 5555, pp. 622-633, 2009