论文标题
计算几何问题的量子算法
Quantum algorithms for computational geometry problems
论文作者
论文摘要
我们研究计算几何学问题的量子算法，例如3线问题。在此问题中，我们给了我们一组行，并要求我们找到一个至少$ 3 $的行的观点。众所周知，3 s-on-3线和许多其他计算几何问题是3sum-hard。也就是说，在经典上解决它们需要时间$ω（n^{2-o（1）}）$，除非对于众所周知的3sum问题有更快的算法（在其中为我们提供了$ n $ integers $ s $ s $ s $ s $，并且必须确定是否存在$ a，b，c \ in s $ a + a + b + b + c = 0 $）。量子，可以使用Grover的量子搜索算法在时间$ o（n \ log n）$中解决3sum。这导致了一个问题：我们可以在$ o（n^c）$ time Quantumally中解决$ o（n^c）$ c <2 $中的$ o（n^c）中的其他3sum-hard问题吗？我们肯定地回答了这个问题，通过构建一种量子算法，该算法在时间$ o（n^{1 + o（1）}）$中求解point-on-3线。该算法结合了递归的振幅扩增和几何思想的使用。我们表明，对于许多3sum-Hard几何问题，相同的想法给出了$ O（n^{1 + o（1））$ time算法。
We study quantum algorithms for problems in computational geometry, such as POINT-ON-3-LINES problem. In this problem, we are given a set of lines and we are asked to find a point that lies on at least $3$ of these lines. POINT-ON-3-LINES and many other computational geometry problems are known to be 3SUM-HARD. That is, solving them classically requires time $Ω(n^{2-o(1)})$, unless there is faster algorithm for the well known 3SUM problem (in which we are given a set $S$ of $n$ integers and have to determine if there are $a, b, c \in S$ such that $a + b + c = 0$). Quantumly, 3SUM can be solved in time $O(n \log n)$ using Grover's quantum search algorithm. This leads to a question: can we solve POINT-ON-3-LINES and other 3SUM-HARD problems in $O(n^c)$ time quantumly, for $c<2$? We answer this question affirmatively, by constructing a quantum algorithm that solves POINT-ON-3-LINES in time $O(n^{1 + o(1)})$. The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give $O(n^{1 + o(1)})$ time algorithm for many 3SUM-HARD geometrical problems.
