Arrow Research search

Author name cluster

François Le Gall

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
2 author rows

Possible papers

20

FOCS Conference 2025 Conference Paper

Group Order is in QCMA

  • François Le Gall
  • Harumichi Nishimura
  • Dhara Thakkar

In this work, we show that verifying the order of a finite group given as a black-box is in the complexity class QCMA. This solves an open problem asked by Watrous in 2000 in his seminal paper on quantum proofs and directly implies that the Group Non-Membership problem is also in the class QCMA, which further proves a conjecture proposed by Aaronson and Kuperberg in 2006. Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box groups.

Details

STOC Conference 2025 Conference Paper

Online Locality Meets Distributed Quantum Computing

  • Amirreza Akbari
  • Xavier Coiteux-Roy
  • Francesco d'Amore 0001
  • François Le Gall
  • Henrik Lievonen
  • Darya Melnyk
  • Augusto Modanese
  • Shreyas Pai

We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: (1) All LCL problems solvable with locality O (log ⋆ n ) in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality O (1). This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. (2) In rooted trees, if we can solve an LCL problem with locality o (logloglog n ) in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality O (log ⋆ n ) in the classical deterministic LOCAL model. One of many implications is that in rooted trees, O (log ⋆ n ) locality in quantum-LOCAL is not stronger than O (log ⋆ n ) locality in classical LOCAL.

Details

MFCS Conference 2023 Conference Paper

Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications

  • François Le Gall
  • Masayuki Miyamoto
  • Harumichi Nishimura

The generation and verification of quantum states are fundamental tasks for quantum information processing that have recently been investigated by Irani, Natarajan, Nirkhe, Rao and Yuen [CCC 2022], Rosenthal and Yuen [ITCS 2022], Metger and Yuen [QIP 2023] under the term state synthesis. This paper studies this concept from the viewpoint of quantum distributed computing, and especially distributed quantum Merlin-Arthur (dQMA) protocols. We first introduce a novel task, on a line, called state generation with distributed inputs (SGDI). In this task, the goal is to generate the quantum state U|ψ⟩ at the rightmost node of the line, where |ψ⟩ is a quantum state given at the leftmost node and U is a unitary matrix whose description is distributed over the nodes of the line. We give a dQMA protocol for SGDI and utilize this protocol to construct a dQMA protocol for the Set Equality problem studied by Naor, Parter and Yogev [SODA 2020], and complement our protocol by showing classical lower bounds for this problem. Our second contribution is a dQMA protocol, based on a recent work by Zhu and Hayashi [Physical Review A, 2019], to create EPR-pairs between adjacent nodes of a network without quantum communication. As an application of this dQMA protocol, we prove a general result showing how to convert any dQMA protocol on an arbitrary network into another dQMA protocol where the verification stage does not require any quantum communication.

Details

MFCS Conference 2021 Conference Paper

Test of Quantumness with Small-Depth Quantum Circuits

  • Shuichi Hirahara
  • François Le Gall

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.

Details

MFCS Conference 2020 Conference Paper

Quantum-Inspired Classical Algorithms for Singular Value Transformation

  • Dhawal Jethwani
  • François Le Gall
  • Sanjay Kumar Singh 0001

A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC 2019).

Details

SODA Conference 2018 Conference Paper

Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor

  • François Le Gall
  • Florent Urrutia

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 α denote the maximum value such that the product of an n × n α matrix by an n α × n matrix can be computed with O ( n 2+ ∊ ) arithmetic operations for any ∊ > 0. By analyzing the fourth power of the Coppersmith-Winograd tensor using our methods, we obtain the new lower bound α > 0. 31389, which improves the previous lower bound α > 0. 30298 obtained 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 × n k matrix by an n k × n matrix for any value k ≠ 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.

Details

MFCS Conference 2018 Conference Paper

Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups

  • François Le Gall
  • Tomoyuki Morimae
  • Harumichi Nishimura
  • Yuki Takeuchi

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.

Details

MFCS Conference 2016 Conference Paper

Quantum Communication Complexity of Distributed Set Joins

  • Stacey Jeffery
  • François Le Gall

Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the natural model of (classical) two-party communication complexity and obtained tight bounds for the complexity of several important distributed set joins. In this paper we initiate the study of the quantum communication complexity of distributed set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which corresponds to computing the composition join of two databases, showing that the product of two n times n Boolean matrices, each owned by one of two respective parties, can be computed with widetilde-O(sqrt{n} ell^{3/4}) qubits of communication, where ell denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is widetilde-Theta(n sqrt{ell}), our quantum algorithm outperforms classical protocols whenever the output matrix is sparse. We also show a quantum lower bound and a matching classical upper bound on the communication complexity of distributed matrix multiplication over F_2. Besides their applications to database theory, the communication complexity of set joins is interesting due to its connections to direct product theorems in communication complexity. In this work we also introduce a notion of all-pairs product theorem, and relate this notion to standard direct product theorems in communication complexity.

Details

STOC Conference 2015 Conference Paper

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method

  • Andris Ambainis
  • Yuval Filmus
  • François Le Gall

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n 2.3755 ). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le~Gall has led to an improved algorithm running in time O(n 2.3729 ). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n 2.3725 ), and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078}); in particular, this approach cannot prove the conjecture that for every ε > 0, two n x n matrices can be multiplied in time O(n 2+ε ). We describe a new framework extending the original laser method, which is the method underlying the previously mentioned algorithms. Our framework accommodates the algorithms by Coppersmith and Winograd, Stothers, Vassilevska-Williams and Le~Gall. We obtain our main result by analyzing this framework. The framework also explains why taking tensor powers of the Coppersmith--Winograd identity results in faster algorithms.

Details

FOCS Conference 2014 Conference Paper

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 Õ(n 5/4 ), where n denotes the number of vertices in the graph. This improves the previous upper bound O(n 9/7 ) = O(n 1. 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(n 9/7 / √log n) queries. Our result also illustrates some limitations of the non-adaptive learning graph approach used to obtain the previous O(n 9/7 ) upper bound since, even over unweighted graphs, any quantum algorithm for triangle finding obtained using this approach requires v(n 9/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.

Details

FOCS Conference 2012 Conference Paper

Faster Algorithms for Rectangular Matrix Multiplication

  • François Le Gall

Let α be the maximal value such that the product of an n × n α matrix by an n α × n matrix can be computed with n 2+o(1) arithmetic operations. In this paper we show that α >; 0. 30298, which improves the previous record α >; 0. 29462 by Coppersmith (Journal of Complexity, 1997). More generally, we construct a new algorithm for multiplying an n × n k matrix by an n k × n matrix, for any value k ≠ 1. The complexity of this algorithm is better than all known algorithms for rectangular matrix multiplication. In the case of square matrix multiplication (i. e. , for k = 1), we recover exactly the complexity of the algorithm by Coppersmith and Winograd (Journal of Symbolic Computation, 1990). These new upper bounds can be used to improve the time complexity of several known algorithms that rely on rectangular matrix multiplication. For example, we directly obtain a O(n 2. 5302 )-time algorithm for the all-pairs shortest paths problem over directed graphs with small integer weights, where n denotes the number of vertices, and also improve the time complexity of sparse square matrix multiplication.

Details

MFCS Conference 2006 Conference Paper

Quantum Weakly Nondeterministic Communication Complexity

  • François Le Gall

Abstract In this paper we study a weak version of quantum nondeterministic communication complexity, corresponding to the most natural generalization of classical nondeterminism, in which a classical proof has to be checked with probability one by a quantum protocol. We prove that, in the framework of communication complexity, even the weak version of quantum nondeterminism is strictly stronger than classical nondeterminism. More precisely, we show the first separation, for a total function, of quantum weakly nondeterministic and classical nondeterministic communication complexity. This separation is quadratic and shows that classical proofs can be checked more efficiently by quantum protocols than by classical ones.

Details