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

While the search for quantum advantage typically focuses on speed­ups 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 restricted to specially-constructed problems Le Gall, SPAA ‘06 or polynomial advantage Kallaugher, FOCS ‘21. We show an exponential quantum space advantage for the maximum directed cut problem. This is the first known exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem in any setting.

Authors

• John Kallaugher
• Ojas Parekh
• Nadezhda Voronova

Keywords

• approximation algorithms
• graph algorithms
• quantum computing
• streaming and sketching
• sublinear algorithms