论文标题
引入结构以加快量子搜索
Introducing Structure to Expedite Quantum Search
论文作者
论文摘要
我们提出了一种新颖的量子算法，用于用一个标记的元素解决非结构化的搜索问题。我们的算法允许生成比著名的Grover算法使用渐近的额外量子门的量子电路，并且可以在NISQ设备上成功执行。我们证明，我们的算法在基本门的总数中是最佳的，直至乘法常数。由于许多NP硬性问题实际上不是非结构化的，因此我们还描述了利用甲骨文结构并允许查找解决方案所需的基本门数量的\ emph {partial uncompute}技术。结合这些结果使我们可以在各种应用程序中使用比Grover的算法使用渐近的基本门，从而使查询数量的数量基本相同。我们展示了如何应用结果来解决硬组合问题，例如唯一的K-SAT。此外，我们展示了如何渐近地减少用多个标记元素解决非结构化搜索问题所需的基本门数量。
We present a novel quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on NISQ devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are not in fact unstructured, we also describe the \emph{partial uncompute} technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use asymptotically smaller number of elementary gates than the Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example Unique k-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.
