2 citations · 2 across the 5 of their papers we have counts for
7 papers
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…
Measurement Geometry for Quantum Random Access Codes: Beyond Nayak Bound and Toward Optimality
Seiseki Akibue, Rudy Raymond, Suguru Tamaki +1
Quantum random access codes (QRACs) ask how well N classical bits can be encoded into M qubits while allowing any single bit to be recovered. Although the Nayak bound remains the s…
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…
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 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…
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…