Showing quant-phShow all
3 papers · 1 filter
quant-ph2026
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…
quant-ph2025
On the complexity of estimating ground state entanglement and free energy
Sevag Gharibian, Jonas Kamminga
Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error…
quant-ph2024
BQP, meet NP: Search-to-decision reductions and approximate counting
Sevag Gharibian, Jonas Kamminga
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT)…