5 papers
Improved Quantum Query Bounds for Boolean Matrix Product Verification
Amin Shiraz Gilani, François Le Gall, Xingyu Zhou
We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification (), answering a longstanding open question in quan…
Improved Quantum Algorithms for Black-Box Abelian Group Decomposition
Junrong Luo, Yinan Li, Francois Le Gall
Decomposing finite Abelian black-box groups into cyclic factors is a basic problem in quantum computation. We give a quantum algorithm for decomposing finite Abelian black-box grou…
Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
Atsuya Hasegawa, Jonas Kamminga, François Le Gall +1
The local Hamiltonian problem is the canonical -complete problem, and time classical algorithms and time quantum algorithms are known to solve t…
Near-Optimal Bounds on the Density of Low-Energy States of -Local Hamiltonians and Faster Quantum Algorithms
Sevag Gharibian, François Le Gall, Ranitha Mataraarachchi +1
Low-energy estimation and state preparation for general -local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently…
Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore +8
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-s…