4 citations · 23 across the 20 of their papers we have counts for
27 papers · 1 filter
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…
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…