论文标题
最小切割的量子复杂性
Quantum complexity of minimum cut
论文作者
论文摘要
无方向性和加权图$ g $中的最小切割问题是找到一组边缘的最小总重量，其拆卸断开了$ g $。我们完全表征了邻接矩阵模型中最小切割问题的量子查询和时间复杂性。如果$ g $具有$ n $的顶点和边缘权重，至少$ 1 $，并且最多只有$τ$，我们会使用$ \ tilde o（n^{3/2} \sqrttτ）$查询和时间来解决量子算法以解决最小切割问题。此外，对于每一个整数$ 1 \leτ\ le n $，我们给出一个图形$ g $，带有边缘重量$ 1 $和$τ$，以便解决$ g $上的最小切割问题需要$ω（n^{3/2}}} \ sqrtt the）$与$ g $ g $的邻接矩阵的许多查询。这些结果与经典的随机情况形成鲜明对比的是，在最坏情况下，需要$ω（n^2）$查询邻接矩阵，即使决定是否连接了未加权的图。 在邻接阵列模型中，当$ g $具有$ m $边缘时，最小切割问题的经典随机复杂性为$ \tildeθ（m）$。我们表明，量子查询和时间复杂性是$ \ tilde o（\ sqrt {mnτ}）$和$ \ tilde o（\ sqrt {mnτ} + n^{3/2}）$，在这里，边缘权重在其中又是$ 1 $ $ 1 $和$τ$。对于密集图，我们在$τ> 1 $和$ω（n^{3/2}）$的量子查询复杂性上给出了$τ> 1 $和$ω（τn）$的量子，对于任何$ 1 \ leq f \ leq n $。 我们的查询算法使用APERS和DE WOLF（焦点2020）的量子算法用于图形稀疏，并将Kawarabayashi和Thorup（STOC 2015）以及Rubinstein，Schramm和Weinberg（ITCS 2018）结构的结构（ITCS 2018）。我们的时间效率实施建立在Karger的树木包装技术的基础上（Stoc 1996）。
The minimum cut problem in an undirected and weighted graph $G$ is to find the minimum total weight of a set of edges whose removal disconnects $G$. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If $G$ has $n$ vertices and edge weights at least $1$ and at most $τ$, we give a quantum algorithm to solve the minimum cut problem using $\tilde O(n^{3/2}\sqrtτ)$ queries and time. Moreover, for every integer $1 \le τ\le n$ we give an example of a graph $G$ with edge weights $1$ and $τ$ such that solving the minimum cut problem on $G$ requires $Ω(n^{3/2}\sqrtτ)$ many queries to the adjacency matrix of $G$. These results contrast with the classical randomized case where $Ω(n^2)$ queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when $G$ has $m$ edges the classical randomized complexity of the minimum cut problem is $\tilde Θ(m)$. We show that the quantum query and time complexity are $\tilde O(\sqrt{mnτ})$ and $\tilde O(\sqrt{mnτ} + n^{3/2})$, respectively, where again the edge weights are between $1$ and $τ$. For dense graphs we give lower bounds on the quantum query complexity of $Ω(n^{3/2})$ for $τ> 1$ and $Ω(τn)$ for any $1 \leq τ\leq n$. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Karger's tree packing technique (STOC 1996).
