标题： 量子组合与征服及其在次线性量子凸包和最大集构造中的应用 显示英文标题

标题： Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction

摘要： 我们引入了一种称为“合并与征服”的量子算法设计范式，这是 Kirkpatrick 和 Seidel 的“先婚配后征服”技术的量子版本。 在量子合并与征服算法中，人们在避免递归的情况下，在征服步骤之前执行量子分而治之算法的合并步骤的核心计算。 由于其非递归性质，此模型更适合量子设置。 我们通过提供适用于已排序点集的二维最大值集合和凸包问题的量子算法展示了这种方法的实用性，这些算法以高概率在 $\tilde{O}(\sqrt{nh})$ 时间内运行，其中 $h$ 是输出的大小。 显示英文摘要

摘要： We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in $\tilde{O}(\sqrt{nh})$ time, w.h.p., where $h$ is the size of the output.