It may be possible to extend the Grover search algorithm by taking a divide and conquer approach using auxiliary solutions to achieve an exponential speed-up.
Quantum search algorithms, such as the Grover algorithm, are investigated as one of the ways to solve a traveling salesman problem (TSP). In TSP, the quantum search starts from an equal superposition of all feasible solutions. The embedding cost of all feasible solutions is up to exponential, i.e.,O(n!)withncities, and makes it difficult to solve large-scale TSP. Hence, preparing the initial state of TSP at a lower embedding cost is an important issue. Here, we propose a quantum search algorithm based on the divide-and-conquer approach, which divides each constraint term of the TSP into subproblems and applies the quantum search to each subproblem. We investigate the embedding quality of all feasible solutions by comparing our proposed method with the Grover algorithm regarding optimal iterations and success probability. The results show that our quantum divide-and-conquer approach can significantly reduce the embedding cost while the success probability decreases.
One of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under size limitations is thus a key question in the field. In this vein, it was recently shown that a hybrid classical-quantum method can help provide polynomial speed-ups to classical divide-and-conquer algorithms, even when only given access to a quantum computer much smaller than the problem itself. In this work, we study the hybrid divide-and-conquer method in the context of tree search algorithms, and extend it by including quantum backtracking, which allows better results than previous Grover-based methods. Further, we provide general criteria for polynomial speed-ups in the tree search context, and provide a number of examples where polynomial speed ups, using arbitrarily smaller quantum computers, can be obtained. We provide conditions for speedups for the well known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ algorithm (the core of the fastest exact Boolean satisfiability solver) for well-behaved classes of formulas. We also provide a simple example where speed-ups can be obtained in an algorithm-independent fashion, under certain well-studied complexity-theoretical assumptions. Finally, we briefly discuss the fundamental limitations of hybrid methods in providing speed-ups for larger problems.