How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing

John Kallaugher, Ojas Parekh, Nadezhda Voronova

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 stream…