Ojas Parekh

The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut

2022 · arXiv (Cornell University)

We investigate the space complexity of two graph streaming problems: Max-Cut and its quantum analogue, Quantum Max-Cut. Previous work by Kapralov and Krachun [STOC `19] resolved the classical complexity of the \emph{classical} problem, showing that …