论文标题
匹配三角形和三角形集合：基于弱量子猜想的硬度
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
论文作者
论文摘要
从经典上讲，对于许多计算问题，人们可以根据一个或多个关键问题的硬度结论时间下限：K-SAT，3SUM和APSP。最近，以K-SAT和3sum的硬度为条件的量子设置中得出了类似的结果。这是使用细粒度减少来完成的，其中的方法是（1）选择一个关键问题$ x $，对于某些功能$ t $，可以猜想任何$ O（t（n）^{1-ε}）$ time AlgorithM可以解决任何常量$ε> 0 $（在固定的计算模型中，并为$ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $ x $时间的时间为他们。 有趣的是，对于三角洲匹配的三角形和三角形的收集，经典的硬度结果是根据所有三个关键问题的硬度而得出的。更确切地说，证明这两个图形问题中的任何一个都意味着K-SAT，3sum和APSP的$ N^{3-ε} $ TIME经典算法将意味着更快的经典算法，这使得匹配三角形和三角形的三角形和三角形收集值得研究。 在本文中，我们表明，对于这两个图形问题中的任何一个，$ n^{1.5-ε} $ time量子算法将暗示K-SAT，3sum和apsp的量子算法更快。我们首先为APSP制定量子硬度猜想，然后从k-Sat，3sum和apsp提出量子降低到达美匹配的三角形和三角形收集。此外，基于量子APSP的猜想，我们还能够证明矩阵问题和许多图形问题证明量子下限。除了需要仔细使用数据结构以及Ambainis的可变时间搜索的量子算法外，大多数匹配的上限都在琐碎的上限遵循。
Classically, for many computational problems one can conclude time lower bounds conditioned on the hardness of one or more of key problems: k-SAT, 3SUM and APSP. More recently, similar results have been derived in the quantum setting conditioned on the hardness of k-SAT and 3SUM. This is done using fine-grained reductions, where the approach is to (1) select a key problem $X$ that, for some function $T$, is conjectured to not be solvable by any $O(T(n)^{1-ε})$ time algorithm for any constant $ε> 0$ (in a fixed model of computation), and (2) reduce $X$ in a fine-grained way to these computational problems, thus giving (mostly) tight conditional time lower bounds for them. Interestingly, for Delta-Matching Triangles and Triangle Collection, classical hardness results have been derived conditioned on hardness of all three mentioned key problems. More precisely, it is proven that an $n^{3-ε}$ time classical algorithm for either of these two graph problems would imply faster classical algorithms for k-SAT, 3SUM and APSP, which makes Delta-Matching Triangles and Triangle Collection worthwhile to study. In this paper, we show that an $n^{1.5-ε}$ time quantum algorithm for either of these two graph problems would imply faster quantum algorithms for k-SAT, 3SUM, and APSP. We first formulate a quantum hardness conjecture for APSP and then present quantum reductions from k-SAT, 3SUM, and APSP to Delta-Matching Triangles and Triangle Collection. Additionally, based on the quantum APSP conjecture, we are also able to prove quantum lower bounds for a matrix problem and many graph problems. The matching upper bounds follow trivially for most of them, except for Delta-Matching Triangles and Triangle Collection for which we present quantum algorithms that require careful use of data structures and Ambainis' variable time search.
