François Le Gall

research

∙ 08/09/2023

Space-bounded quantum state testing via space-efficient quantum singular value transformation

Driven by exploring the power of quantum computation with a limited numb...

0 François Le Gall, et al. ∙

research

∙ 07/18/2023

No distributed quantum advantage for approximate graph coloring

We give an almost complete characterization of the hardness of c-colorin...

0 Xavier Coiteux-Roy, et al. ∙

research

∙ 07/13/2023

Faster Rectangular Matrix Multiplication by Combination Loss Analysis

Duan, Wu and Zhou (FOCS 2023) recently obtained the improved upper bound...

0 François Le Gall, et al. ∙

research

∙ 04/11/2023

Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms

Several quantum algorithms for linear algebra problems, and in particula...

0 François Le Gall, et al. ∙

research

∙ 03/03/2023

Quantum Merlin-Arthur proof systems for synthesizing quantum states

Complexity theory typically focuses on the difficulty of solving computa...

0 Hugo Delavenne, et al. ∙

research

∙ 12/06/2022

Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model

We consider the LOCAL model of distributed computing, where in a single ...

0 François Le Gall, et al. ∙

research

∙ 10/04/2022

Distributed Quantum Interactive Proofs

The study of distributed interactive proofs was initiated by Kol, Oshman...

0 François Le Gall, et al. ∙

research

∙ 10/04/2022

Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications

The generation and verification of quantum states are fundamental tasks ...

0 François Le Gall, et al. ∙

research

∙ 07/21/2022

Improved Hardness Results for the Guided Local Hamiltonian Problem

Estimating the ground state energy of a local Hamiltonian is a central p...

0 Sevag Gharibian, et al. ∙

research

∙ 05/10/2022

An optimal oracle separation of classical and quantum hybrid schemes

Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 20...

0 Atsuya Hasegawa, et al. ∙

research

∙ 04/06/2022

Quantum Approximate Counting for Markov Chains and Application to Collision Counting

In this paper we show how to generalize the quantum approximate counting...

0 François Le Gall, et al. ∙

research

∙ 01/09/2022

Quantum Distributed Algorithms for Detection of Cliques

The possibilities offered by quantum computing have drawn attention in t...

0 Keren Censor-Hillel, et al. ∙

research

∙ 11/17/2021

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture

The Quantum Singular Value Transformation (QSVT) is a recent technique t...

0 Sevag Gharibian, et al. ∙

research

∙ 10/02/2021

Lower Bounds for Induced Cycle Detection in Distributed Computing

The distributed subgraph detection asks, for a fixed graph H, whether th...

0 François Le Gall, et al. ∙

research

∙ 05/12/2021

Test of Quantumness with Small-Depth Quantum Circuits

Recently Brakerski, Christiano, Mahadev, Vazirani and Vidick (FOCS 2018)...

0 Shuichi Hirahara, et al. ∙

research

∙ 05/06/2021

Quantum Logarithmic Space and Post-selection

Post-selection, the power of discarding all runs of a computation in whi...

0 François Le Gall, et al. ∙

research

∙ 05/03/2021

Quantum Advantage with Shallow Circuits under Arbitrary Corruption

Recent works by Bravyi, Gosset and König (Science 2018), Bene Watts et a...

0 Atsuya Hasegawa, et al. ∙

research

∙ 01/19/2021

Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs

In this paper we give fast distributed graph algorithms for detecting an...

0 Keren Censor-Hillel, et al. ∙

research

∙ 11/14/2020

Tight Distributed Listing of Cliques

Much progress has recently been made in understanding the complexity lan...

0 Keren Censor-Hillel, et al. ∙

research

∙ 10/23/2020

Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems

Longest common substring (LCS), longest palindrome substring (LPS), and ...

0 François Le Gall, et al. ∙

research

∙ 07/10/2020

On Distributed Listing of Cliques

We show an Õ(n^p/(p+2))-round algorithm in the model for listing of K_p ...

0 Keren Censor-Hillel, et al. ∙

research

∙ 06/26/2020

Quantum Communication Complexity of Distribution Testing

The classical communication complexity of testing closeness of discrete ...

0 Aleksandrs Belovs, et al. ∙

research

∙ 03/06/2020

Barriers for rectangular matrix multiplication

We study the algorithmic problem of multiplying large matrices that are ...

0 Matthias Christandl, et al. ∙

research

∙ 02/24/2020

Distributed Quantum Proofs for Replicated Data

The paper tackles the issue of checking that all copies of a large data ...

0 Pierre Fraigniaud, et al. ∙

research

∙ 10/13/2019

Quantum-Inspired Classical Algorithms for Singular Value Transformation

A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the...

0 Dhawal Jethwani, et al. ∙

research

∙ 08/30/2019

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model

This paper considers the triangle finding problem in the CONGEST model o...

0 Taisuke Izumi, et al. ∙

research

∙ 06/06/2019

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

The All-Pairs Shortest Path problem (APSP) is one of the most central pr...

0 Taisuke Izumi, et al. ∙

research

∙ 10/30/2018

Average-Case Quantum Advantage with Shallow Circuits

Recently Bravyi, Gosset and König (Science 2018) proved an unconditional...

0 François Le Gall, et al. ∙

research

∙ 10/25/2018

Quantum Advantage for the LOCAL Model in Distributed Computing

There are two central models considered in (fault-free synchronous) dist...

0 François Le Gall, et al. ∙

research

∙ 05/09/2018

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

In this paper we consider what can be computed by a user interacting wit...

0 François Le Gall, et al. ∙

research

∙ 04/09/2018

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks

The computation of the diameter is one of the most central problems in d...

0 François Le Gall, et al. ∙

research

∙ 08/18/2017

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

In the past few years, successive improvements of the asymptotic complex...

0 François Le Gall, et al. ∙

François Le Gall

Featured Co-authors