2022/06/01 by John Kallaugher, Kallaugher, John, Ojas Parekh +1 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2206.00213
openalex publication_date 2022/06/01 · openalex created_date 2022/06/13 · openalex updated_date 2026/07/28
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 classical problem, showing that any (2 - ε)-approximation requires Ω(n) space (a 2-approximation is trivial with \textrmO(log n) space). We generalize both of these qualifiers, demonstrating Ω(n) space lower bounds for (2 - ε)-approximating Max-Cut and Quantum Max-Cut, even if the algorithm is allowed to maintain a quantum state. As the trivial approximation algorithm for Quantum Max-Cut only gives a 4-approximation, we show tightness with an algorithm that returns a (2 + ε)-approximation to the Quantum Max-Cut value of a graph in \textrmO(log n) space. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using \textrmo(n) space. We prove our lower bounds through the techniques of Boolean Fourier analysis. We give the first application of these methods to sequential one-way quantum communication, in which each player receives a quantum message from the previous player, and can then perform arbitrary quantum operations on it before sending it to the next. To this end, we show how Fourier-analytic techniques may be used to understand the application of a quantum channel.