Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOHN KALLAUGHER:
All reports by Author John Kallaugher:

TR23-189 | 28th November 2023
John Kallaugher, Ojas Parekh, Nadezhda Voronova

Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model

While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been ... more >>>




ISSN 1433-8092 | Imprint