5 citations · 10 across the 13 of their papers we have counts for
15 papers
Dequantizing Short-Path Quantum Algorithms
François Le Gall, Suguru Tamaki
The short-path quantum algorithm introduced by Hastings (Quantum 2018, 2019) is a variant of adiabatic quantum algorithms that enables an easier worst-case analysis by avoiding the…
A slightly improved upper bound for quantum statistical zero-knowledge
François Le Gall, Yupan Liu, Qisheng Wang
The complexity class Quantum Statistical Zero-Knowledge (), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper b…
Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
François Le Gall, Maël Luce, Joseph Marchand +1
We investigate how much quantum distributed algorithms can outperform classical distributed algorithms with respect to the message complexity (the overall amount of communication u…
Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
Atsuya Hasegawa, François Le Gall, Augusto Modanese
We present relation problems whose input size is such that they can be solved with no communication for entanglement-assisted quantum communication models, but require q…
Does there exist a quantum fingerprinting protocol without coherent measurements?
Atsuya Hasegawa, Srijita Kundu, François Le Gall +2
Buhrman, Cleve, Watrous, and de Wolf (PRL 2001) discovered the quantum fingerprinting protocol, which is the quantum SMP protocol with qubits communication for the equa…
Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries
François Le Gall, Oran Nadler, Harumichi Nishimura +1
In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public random…
Distributed Quantum Advantage for Local Problems
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy +10
We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prio…
Classical versus quantum queries in quantum PCPs with classical proofs
Harry Buhrman, François Le Gall, Jordi Weggemans
We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for quantum queries to a polynomially-sized classical proof ($\mat…
Space-bounded quantum interactive proof systems
François Le Gall, Yupan Liu, Harumichi Nishimura +1
We introduce two models of space-bounded quantum interactive proof systems, and . The model, a space-bounded variant of quantu…
Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
François Le Gall
We construct classical algorithms computing an approximation of the ground state energy of an arbitrary -local Hamiltonian acting on qubits. We first consider the setting wh…
Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
Hugo Delavenne, François Le Gall
This work investigates the relationships between quantum state synthesis complexity classes (a recent concept in computational complexity that focuses on the complexity of preparin…
Space-bounded quantum state testing via space-efficient quantum singular value transformation
François Le Gall, Yupan Liu, Qisheng Wang
Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which enco…
No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala +7
We give an almost complete characterization of the hardness of -coloring -chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. I…
Quantum Merlin-Arthur proof systems for synthesizing quantum states
Hugo Delavenne, François Le Gall, Yupan Liu +1
Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it i…
Quantum Distributed Algorithms for Detection of Cliques
Keren Censor-Hillel, Orr Fischer, François Le Gall +2
The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed a…