5 papers · 1 filter
Breaking the quantum barriers for Graph Collision
Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali +3
In the graph collision problem, the task is to decide whether a known graph on vertices contains an edge with both endpoints marked, given query access to the input bits specif…
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…