4 papers · 1 filter
QMA(2) with Limited Shared Entanglement
Alex Della Schiava, Ranitha Mataraarachchi
In , two computationally unbounded provers submit unentangled quantum witnesses to a polynomial-time quantum verifier. We ask whether allowing limited shared entan…
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…
New lower bounds for CDS and -routing
Atsuya Hasegawa, Ranitha Mataraarachchi
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case…
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…