论文标题
多层量子搜索并将NP纳入BQP
Multi-layer quantum search and inclusion of NP into BQP
论文作者
论文摘要
在这项工作中，我们提出了一种多层量子搜索方法，该方法生成了标准Grover算法的指数加速。作为直接应用，任何NP问题都可以在仅具有多项式栅极复杂性的量子电路上有效解决。特别是，这种多层搜索可以通过指数加速来解决分解问题，从而提供了Shor算法的替代方案。我们的结果表明，量子电路的指数加速无处不在，而Grover的搜索比已经证明的要强大得多。由于这种多层搜索设计完全释放了Grover搜索的巨大潜力，因此与单层查询复杂性的二次最优性无矛盾。
In this work, we present a multi-layer quantum search method that generates an exponential speedup of the standard Grover's algorithm. As direct applications, any NP problems can be solved efficiently on a quantum circuit with only polynomial gate complexity. In particular, such multi-layer search can solve the factoring problem with an exponential speedup, providing an alternative to Shor's algorithm. Our results show that the exponential speedup of quantum circuits is ubiquitous, and Grover's search is much more powerful than that has been demonstrated. With no contradiction to the quadratic optimality of single-layer query complexity, the great potential of Grover's search is fully released by such multi-layer search design.
