论文标题
量子和经典最大切割的量子和经典流复杂性
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut
论文作者
论文摘要
我们研究了两个图流问题的空间复杂性：最大切割及其量子类似物，量子最大切割。 Kapralov和Krachun [stoc`19]的先前工作解决了\ emph {经典}问题的经典复杂性，表明任何$（2- \ varepsilon）$ - 近似都需要$ω（n）$ space（$ 2 $ - approximation a appRoximation a a approxial capliagial capliagial capliagial caplivial caplivial capliagial capliagial clivial capliagial capliagial capliagial capliagial a ts $ \ \ \ \ \ \ \ textrm {o）我们概括了这两个限定符，以$（2 - \ varepsilon）$ - 近似最大切割和量子最大切割的$ω（n）$ space下限，即使允许该算法保持量子状态。由于量子最大切割的微不足道近似算法仅给出$ 4 $ - approximation，因此我们使用算法显示紧密度，该算法返回$（2 + \ varepsilon）$ - 在$ \ textrm {o}（\ log nog n）$ space中返回图中图的量子最大值值。我们的工作使用$ \ textrm {o}（n）$ space解决了量子和经典最大切割的量子和经典近似性。 我们通过布尔傅里叶分析的技术证明了我们的下限。我们将这些方法的第一个应用程序用于顺序的单向量子通信，在该通信中，每个玩家都会从上一个播放器接收量子消息，然后可以在将其发送到下一个之前对其进行任意量子操作。为此，我们展示了如何使用傅立叶分析技术来了解量子通道的应用。
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 any $(2 - \varepsilon)$-approximation requires $Ω(n)$ space (a $2$-approximation is trivial with $\textrm{O}(\log n)$ space). We generalize both of these qualifiers, demonstrating $Ω(n)$ space lower bounds for $(2 - \varepsilon)$-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 + \varepsilon)$-approximation to the Quantum Max-Cut value of a graph in $\textrm{O}(\log n)$ space. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using $\textrm{o}(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.
