Multi-layer quantum search and inclusion of NP into BQP

Shan Jin, Xiaoting Wang, Bo LiarXiv 2020 · DOI · arXiv

TL;DR

This paper introduces a "multi-layer" quantum search algorithm that achieves an exponential speedup over the standard Grover's algorithm. This novel approach allows any NP-complete problem to be solved with polynomial quantum gate complexity, effectively demonstrating that NP is contained within BQP.

What Problem Does This Paper Address?

Quantum computation promises significant speedups for certain problems, with algorithms like Shor's offering exponential advantages and Grover's search providing a quadratic one. However, a key question has been whether exponential speedups are rare or ubiquitous in quantum computation. Grover's algorithm, despite its broad applicability to NP-complete problems and optimization, is fundamentally limited by a quadratic query complexity lower bound for a single layer of operations. This paper tackles the challenge of overcoming this limitation to unlock exponential speedups for Grover's search, thereby expanding the power of quantum computation.

Methods

The core innovation is the "multi-layer oracle search." Instead of a single Grover iteration, the authors propose chaining multiple layers of fixed-point quantum search. Each layer uses a modified Grover iteration, where the standard initial-state inversion is replaced by a target-state inversion from the previous layer. This clever trick allows the construction of the necessary quantum operations even without knowing the intermediate states. The algorithm is built upon the concept of fixed-point quantum search, which converges to the target state after sufficient iterations. The authors then demonstrate how to construct a sequence of oracles for this multi-layer approach, specifically by defining a series of progressively refined solution sets. For NP-complete problems like SAT, they show how to construct these oracles by combining the original Boolean expression with logical AND operations on variables.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithmic development rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Exponential Speedup for Grover's Search: The most significant insight is that by layering Grover iterations, the fundamental quadratic query complexity limit of a single layer can be bypassed to achieve an exponential speedup.
  • NP in BQP: The multi-layer approach provides a concrete method to solve any NP-complete problem with polynomial quantum gate complexity, thus proving NP $\subseteq$ BQP. This is a major theoretical result in quantum complexity theory.
  • Ubiquity of Quantum Speedups: The work suggests that exponential speedups are not exceptional but rather a more common feature of quantum computation, achievable through clever algorithmic design.
  • Practical Implications for Factoring: The method offers an alternative to Shor's algorithm for integer factorization, achieving an exponential speedup, though with a higher polynomial gate complexity.

Key Results

The paper demonstrates that the proposed multi-layer quantum search achieves an exponential speedup in query complexity compared to standard Grover's search. For NP-complete problems like SAT, the overall gate complexity is shown to be polynomial in the problem size (specifically, $O(p(n)n^2)$ where $p(n)$ is the polynomial complexity of evaluating the Boolean function). This result leads to the conclusion that NP $\subseteq$ BQP. For integer factoring, the method provides an exponential speedup, with a gate complexity of $O(p(n)n^2)$, where $p(n)$ is the complexity of integer division.

Limitations and Future Work

The authors acknowledge that while their method achieves an exponential speedup for factoring, it is not as efficient as Shor's algorithm in terms of gate complexity ($O(p(n)n^2)$ vs. $O(n^3)$). They also note that the efficiency of constructing the oracles depends on the classical complexity of evaluating the problem's function. Future work could explore further optimizations of the multi-layer construction and its application to other complex computational problems where Grover's search serves as a building block.

Summary updated

Abstract

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.
BibTeX
@misc{jin2020multi,
  author = {Shan Jin and Xiaoting Wang and Bo Li},
  title = {{Multi-layer quantum search and inclusion of NP into BQP}},
  year = {2020},
  eprint = {2004.11347},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.11347},
}
Figure