This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound $O(n)$ to $\tilde O(n^{1/3})$ , where~ $n$ denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in $\tilde O(n^{1/4})$ rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now $\tilde O(n^{1/4})$ and $\tilde Θ(n^{1/3})$ , respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound $O(n)$ to $\tilde O(n^{1/3})$, where~$n$ denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in $\tilde O(n^{1/4})$ rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now $\tilde O(n^{1/4})$ and $\tilde Θ(n^{1/3})$, respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.

arXiv:1908.11488Aug 30, 201916 citations

Quantum Advantage for the LOCAL Model in Distributed Computing

François Le Gall, Harumichi Nishimura, Ansis Rosmanis

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 two computational tasks that can be solved in a constant number of rounds in the quantum setting but require Omega(n) rounds in the classical (randomized) setting, where n denotes the size of the network.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 two computational tasks that can be solved in a constant number of rounds in the quantum setting but require Omega(n) rounds in the classical (randomized) setting, where n denotes the size of the network.

arXiv:1810.10838Leibniz international proceedings in informaticsOct 25, 201815 citations

Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments

François Le Gall

In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity Õ(n5/4), where n denotes the number of vertices in the graph. This improves the previous upper bound O(n9/7) = O(n1.285) recently obtained by Lee, Magniez and Santha. Our result shows, for the first time, that in the quantum query complexity setting unweighted triangle finding is easier than its edge-weighted version, since for finding an edge-weighted triangle Belovs and Rosmanis proved that any quantum algorithm requires O(n9/7/ √log n) queries. Our result also illustrates some limitations of the non-adaptive learning graph approach used to obtain the previous O(n9/7) upper bound since, even over unweighted graphs, any quantum algorithm for triangle finding obtained using this approach requires v(n9/7/ √log n) queries as well. To bypass the obstacles characterized by these lower bounds, our quantum algorithm uses combinatorial ideas exploiting the graph-theoretic properties of triangle finding, which cannot be used when considering edge-weighted graphs or the non-adaptive learning graph approach.In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity Õ(n5/4), where n denotes the number of vertices in the graph. This improves the previous upper bound O(n9/7) = O(n1.285) recently obtained by Lee, Magniez and Santha. Our result shows, for the first time, that in the quantum query complexity setting unweighted triangle finding is easier than its edge-weighted version, since for finding an edge-weighted triangle Belovs and Rosmanis proved that any quantum algorithm requires O(n9/7/ √log n) queries. Our result also illustrates some limitations of the non-adaptive learning graph approach used to obtain the previous O(n9/7) upper bound since, even over unweighted graphs, any quantum algorithm for triangle finding obtained using this approach requires v(n9/7/ √log n) queries as well. To bypass the obstacles characterized by these lower bounds, our quantum algorithm uses combinatorial ideas exploiting the graph-theoretic properties of triangle finding, which cannot be used when considering edge-weighted graphs or the non-adaptive learning graph approach.

arXiv:1407.0085Annual Symposium on Foundations of Computer ScienceOct 1, 201456 citations

Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model

Taisuke Izumi, François Le Gall

The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(łog n) bits in synchronous rounds, the best known general algorithm for APSP uses Õ(n1/3) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a Õ(n1/4)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(łog n) bits in synchronous rounds, the best known general algorithm for APSP uses Õ(n1/3) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a Õ(n1/4)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.

arXiv:1906.02456ACM Symposium on Principles of Distributed Computing (PODC)Jul 16, 201923 citations

Quantum Distributed Complexity of Set Disjointness on a Line

Frédéric Magniez, Ashwin Nayak

Given x,y ∈ {0,1}ⁿ, Set Disjointness consists in deciding whether x_i = y_i = 1 for some index i ∈ [n]. We study the problem of computing this function in a distributed computing scenario in which the inputs x and y are given to the processors at the two extremities of a path of length d. Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging O(log n) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from 1/2. We call this problem "Set Disjointness on a Line". Set Disjointness on a Line was introduced by Le Gall and Magniez [Le Gall and Magniez, 2018] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of O(log n) qubits. In this work, we prove an unconditional lower bound of Ω̃(∛{n d²} + √n) rounds for Set Disjointness on a Line with d + 1 processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of Ω̃ (∛{nδ²} + √n) on the number of rounds required for computing the diameter δ of any n-node network with quantum messages of size O(log n) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function f (such as Set Disjointness) has access to the inputs x and y through two separate oracles 𝒪_x and 𝒪_y, respectively. The restriction is that the algorithm is required to alternately make d queries to 𝒪_x and d queries to 𝒪_y, with input-independent computation in between queries. The model reflects a "switching delay" of d queries between a "round" of queries to x and the following "round" of queries to y. The technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to this query model. We provide an algorithm for Set Disjointness in this query model with query complexity that matches the round lower bound stated above, up to a polylogarithmic factor. In this sense, the round lower bound we show for Set Disjointness on a Line is optimal.Given x,y ∈ {0,1}ⁿ, Set Disjointness consists in deciding whether x_i = y_i = 1 for some index i ∈ [n]. We study the problem of computing this function in a distributed computing scenario in which the inputs x and y are given to the processors at the two extremities of a path of length d. Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging O(log n) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from 1/2. We call this problem "Set Disjointness on a Line". Set Disjointness on a Line was introduced by Le Gall and Magniez [Le Gall and Magniez, 2018] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of O(log n) qubits. In this work, we prove an unconditional lower bound of Ω̃(∛{n d²} + √n) rounds for Set Disjointness on a Line with d + 1 processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of Ω̃ (∛{nδ²} + √n) on the number of rounds required for computing the diameter δ of any n-node network with quantum messages of size O(log n) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function f (such as Set Disjointness) has access to the inputs x and y through two separate oracles 𝒪_x and 𝒪_y, respectively. The restriction is that the algorithm is required to alternately make d queries to 𝒪_x and d queries to 𝒪_y, with input-independent computation in between queries. The model reflects a "switching delay" of d queries between a "round" of queries to x and the following "round" of queries to y. The technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to this query model. We provide an algorithm for Set Disjointness in this query model with query complexity that matches the round lower bound stated above, up to a polylogarithmic factor. In this sense, the round lower bound we show for Set Disjointness on a Line is optimal.

Jan 1, 20201 citation

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks

François Le Gall, Frédéric Magniez

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 Ω(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 O(√D )-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 Ω(√ ) on the round complexity of any quantum algorithm computing the diameter, and furthermore show a tight lower bound Ω(√D ) for any distributed quantum algorithm in which each node can use only poly(log n) quantum bits of memory.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 Ω(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 O(√D )-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 Ω(√ ) on the round complexity of any quantum algorithm computing the diameter, and furthermore show a tight lower bound Ω(√D ) for any distributed quantum algorithm in which each node can use only poly(log n) quantum bits of memory.

Jan 14, 20190 citations

O(n)

\tilde O(n^{1/3})

, where~

n

denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in

\tilde O(n^{1/4})

rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now

\tilde O(n^{1/4})

and

\tilde Θ(n^{1/3})

, respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.