Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0906.4804

Speeding up the Grover algorithm using auxiliary solutions

Anwar Y. Shiekh

Published Jun 26, 2009• 0 citations
arXivHTMLPDF

Abstract

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.
DOI
10.48550/arxiv.0906.4804

Related papers

Solving Exponential Search Space with Divide and Conquer using Grover

Kaoru Aguilera Katayama

•Sep 7, 2026•0 citations

Embedding All Feasible Solutions of Traveling Salesman Problem by Divide-and-Conquer Quantum Search

Rei Sato, Kazuhiro Saito, Tetsuro Nikuni +1 more

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.,$\mathcal{O}(n!)$with$n$cities, 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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•5 citations

New Optimized Grover's Algorithm Optimization of Grover's algorithm: with quantum simulating

Idhant Sood, Ahaan Sirohia, Arjun Dev Juneja

The paper below shows an optimized algorithm to perform Grover’s Algorithm on classical computers for high no. of states in reasonable times.

•May 23, 2025•0 citations

New Optimized Grover's Algorithm Optimization of Grover's algorithm: with quantum simulating

Idhant Sood, Ahaan Sirohia, Arjun Dev Juneja

The paper below shows an optimized algorithm to perform Grover’s Algorithm on classical computers for high no. of states in reasonable times.

•May 30, 2025•0 citations

Hybrid divide-and-conquer approach for tree search algorithms

Mathys Rennela, Sebastiaan Brand, Alfons Laarman +1 more

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.

arXiv:2007.07040•Quantum•Mar 23, 2023•15 citations

A quantum no-reflection theorem and the speeding up of Grover's search algorithm

K. S. Kumar, Gheorghe Sorin Paraoanu

We prove that it is impossible to built a universal quantum machine that produces reflections about an unknown state. We then point out a connection between this result and the optimality of Grover's search algorithm: if such reflection machines were available, it would be possible to accelerate Grover's search algorithm to exponential speedups.

arXiv:1106.0584•Europhysics Letters (EPL)•Jan 1, 2011•7 citations
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!)\mathcal{O}(n!)O(n!)withnnncities, 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.