205 citations · 1k across the 65 of their papers we have counts for
70 papers
Improved Separations between Quantum and Classical Communication Complexity of Total Functions
François Le Gall
We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separatio…
Constant-round quantum advantage in communication complexity for total functions
Atsuya Hasegawa, François Le Gall
We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a se…
An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
Ranitha Mataraarachchi, François Le Gall, Suguru Tamaki
Low-energy estimation and state preparation for general -local Hamiltonians are fundamental challenges in quantum complexity theory. For constant relative accuracy, Buhrman et a…
Multi-Prover Interactive Proof Systems with Leakage
Vahid R. Asadi, Atsuya Hasegawa, François Le Gall
It is known that there exist multi-prover interactive protocols ( protocols) for the complexity class , succinct protocols for $\mathsf{…
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +1
The local Hamiltonian (LH) problem is the canonical -complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that t…
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
Harry Buhrman, Sevag Gharibian, Zeph Landau +3
We present an extremely simple polynomial-space exponential-time -approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomia…
Dequantization and Hardness of Spectral Sum Estimation
Roman Edenhofer, Atsuya Hasegawa, François Le Gall
We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarith…
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 s…
Beating the natural Grover bound for low-energy estimation and state preparation
Harry Buhrman, Sevag Gharibian, Zeph Landau +3
Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this work, we give quantum algorithms which, given any -body Ha…
Faster Rectangular Matrix Multiplication by Combination Loss Analysis
François Le Gall
Duan, Wu and Zhou (FOCS 2023) recently obtained the improved upper bound on the exponent of square matrix multiplication by introducing a new approach to quantify and co…
Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms
François Le Gall
Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been "dequantized" in the past few years. These dequantization res…
Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model
François Le Gall, Ansis Rosmanis
We consider the LOCAL model of distributed computing, where in a single round of communication each node can send to each of its neighbors a message of an arbitrary size. It is kno…
Bounds on oblivious multiparty quantum communication complexity
François Le Gall, Daiki Suruga
The main conceptual contribution of this paper is investigating quantum multiparty communication complexity in the setting where communication is \emph{oblivious}. This requirement…
Distributed Quantum Interactive Proofs
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc…
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…
Improved Hardness Results for the Guided Local Hamiltonian Problem
Chris Cade, Marten Folkertsma, Sevag Gharibian +4
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum alg…
An optimal oracle separation of classical and quantum hybrid schemes
Atsuya Hasegawa, François Le Gall
Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle such that $\mathsf{BQP}^\mathcal{O} \neq (\mathsf{B…
Quantum Approximate Counting for Markov Chains and Application to Collision Counting
François Le Gall, Iu-Iong Ng
In this paper we show how to generalize the quantum approximate counting technique developed by Brassard, Høyer and Tapp [ICALP 1998] to a more general setting: estimating the numb…
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
Sevag Gharibian, François Le Gall
The Quantum Singular Value Transformation (QSVT) is a recent technique that gives a unified framework to describe most quantum algorithms discovered so far, and may lead to the dev…
Lower Bounds for Induced Cycle Detection in Distributed Computing
François Le Gall, Masayuki Miyamoto
The distributed subgraph detection asks, for a fixed graph , whether the -node input graph contains as a subgraph or not. In the standard CONGEST model of distributed com…
Quantum Logarithmic Space and Post-selection
François Le Gall, Harumichi Nishimura, Abuzer Yakaryılmaz
Post-selection, the power of discarding all runs of a computation in which an undesirable event occurs, is an influential concept introduced to the field of quantum complexity theo…
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 tes…
Quantum Advantage with Shallow Circuits Under Arbitrary Corruption
Atsuya Hasegawa, François Le Gall
Recent works by Bravyi, Gosset and König (Science 2018), Bene Watts et al. (STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have shown unconditional separat…
Tight Distributed Listing of Cliques
Keren Censor-Hillel, Yi-Jun Chang, François Le Gall +1
Much progress has recently been made in understanding the complexity landscape of subgraph finding problems in the CONGEST model of distributed computing. However, so far, very few…