← Back to papers
How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing
John Kallaugher, Ojas Parekh, N. Voronova·October 24, 2024·DOI: 10.48550/arXiv.2410.18922
Computer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
A series of work [GKK+08, Kal22, KPV24] has shown that asymptotic advantages in space complexity are possible for quantum algorithms over their classical counterparts in the streaming model. We give a simple quantum sketch that encompasses all these results, allowing them to be derived from entirely classical algorithms using our quantum sketch as a black box. The quantum sketch and its proof of correctness are designed to be accessible to a reader with no background in quantum computation, relying on only a small number of self-contained quantum postulates.