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

A new algorithm for directed quantum search

Tathagat Tulsi, Lov K. Grover, Apoorva D. Patel

Published May 2, 2005• 5 citations
OpenAlex

Abstract

Quantum searching requires precise knowledge of problem parameters (such as the fraction of target states) for efficient operation. Recently an algorithm has been discovered, referred to as the Phase-$\\pi/3$ search algorithm, which gets around this limitation. This algorithm can search a database with the fraction of target states equal to $1-\\epsilon$ so that in $q$ queries it produces a probability of error equal to $\\epsilon^{2q+1}$ which has since been proved to be optimal. This paper gives a different algorithm which has the same worst-case behavior as the Phase-$\\pi/3$ search algorithm but much better average-case behavior. Furthermore the new algorithm gives $\\epsilon^{2q+1}$ convergence for all integral $q$, the Phase-$\\pi/3$ search algorithm, requires $q$ to be $(3^{n}-1)/2$, with $n$ a positive integer. In the new algorithm, the operations are controlled in a special way by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations.

Related papers

A new algorithm for fixed point quantum search

Tathagat Tulsi, Lov K. Grover, Apoorva D. Patel

The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-$π/3$ search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from $ε$ to $ε^{2q+1}$ using $q$ oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-$π/3$ search algorithm but much better average-case behavior. Furthermore the new algorithm gives $ε^{2q+1}$ convergence for all integral $q$, whereas the Phase-$π/3$ search algorithm requires $q$ to be $(3^{n}-1)/2$ with $n$ a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing.

arXiv:quant-ph/0505007•May 2, 2005•0 citations

A new algorithm for fixed point quantum search

Tathagat Tulsi, Lov K. Grover, Apoorva D. Patel

The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-\pi/3 search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from \epsilon to \epsilon^{2q+1} using q oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-\pi/3 search algorithm but much better average-case behavior. Furthermore the new algorithm gives \epsilon^{2q+1} convergence for all integral q, whereas the Phase-\pi/3 search algorithm requires q to be (3^{n}-1)/2 with n a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing.

Quantum Information and Computation•Sep 1, 2006•14 citations

Optimal Quantum Algorithms for Ordered Search

Joseph Carolan, Andrew M. Childs

Ordered search is the problem of locating a target element in a sorted list of size $n$ using comparison queries. Classically, binary search requires $\lceil \log_2 n\rceil$ queries, which is optimal. Quantum algorithms offer a constant-factor speedup, but the precise constant has been a longstanding open question. We close this gap by exhibiting two new quantum algorithms for ordered search, each using the optimal $\frac{1}π\ln n+o(\log n)$ queries. The first, discovered by Claude Fable 5, is a simple zero-error algorithm derived from a continuum relaxation of the problem. The second, discovered by GPT-5.6-Sol (informed by Claude's zero-error algorithm), is an exact algorithm based on an analytic solution of the polynomial program of Farhi, Goldstone, Gutmann, and Sipser.

quant-pharXiv:2609.34293•Sep 29, 2026•0 citations

Quantum Algorithms with Fixed Points: The Case of Database Search

Lov K. Grover, Apoorva D. Patel, Tathagat Tulsi

The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of $\fracπ{3}$. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using $q$ oracle queries, these variations reduce the probability of finding a non-target state from $ε$ to $ε^{2q+1}$, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.

arXiv:quant-ph/0603132•Mar 15, 2006•3 citations

Fixed-Point Quantum Search

Lov K. Grover

The quantum search algorithm consists of an iterative sequence of selective inversions and diffusion type operations, as a result of which it is able to find a state with desired properties (target state) in an unsorted database of size N in only sqrt[N] queries. This is achieved by designing the iterative transformations in a way that each iteration results in a small rotation of the state vector in a two-dimensional Hilbert space that includes the target state; if we choose the right number of iterative steps, we will stop just at the target state. This Letter shows that by replacing the selective inversions by selective phase shifts of pi/3, the algorithm preferentially converges to the target state irrespective of the step size or number of iterations. This feature leads to robust search algorithms and also to new schemes for quantum control and error correction.

arXiv:quant-ph/0503205•Physical Review Letters•Oct 3, 2005•209 citations

Ancilla-mediated fixed-point quantum search using Grover iterations

Yash Prabhat, Snigdha Thakur, Ankur Raina

Grover's quantum search algorithm provides a fundamental quadratic speedup for unstructured datasets, reducing query complexity from $\mathcal{O}(N)$ to $\mathcal{O}(\sqrt{N})$. However, the algorithm's reliance on precise iteration counts leads to the ``soufflé problem,'' where over-rotation results in a sharp decline in success probability. This limitation is particularly restrictive when the number of solution states, $M$, is unknown. In this work, we present an ancilla-mediated fixed-point quantum search algorithm that achieves robust convergence by mapping the solution amplitude to a dedicated ancilla qubit. Unlike existing phase-matching fixed-point methods, our approach utilizes Grover's real-plane reflections, thereby maintaining the intuitive geometric architecture of the original algorithm. We demonstrate that this method achieves a success probability of at least $92.6\%$ with a query complexity of approximately $\mathcal{O}(\sqrt{N/M})$, effectively bridging the gap between standard amplitude amplification and robust fixed-point convergence.

quant-pharXiv:2608.29839•Sep 1, 2026•0 citations
Quantum searching requires precise knowledge of problem parameters (such as the fraction of target states) for efficient operation. Recently an algorithm has been discovered, referred to as the Phase-pi/3\\pi/3pi/3 search algorithm, which gets around this limitation. This algorithm can search a database with the fraction of target states equal to 1−epsilon1-\\epsilon1−epsilon so that in qqq queries it produces a probability of error equal to epsilon2q+1\\epsilon^{2q+1}epsilon2q+1 which has since been proved to be optimal. This paper gives a different algorithm which has the same worst-case behavior as the Phase-pi/3\\pi/3pi/3 search algorithm but much better average-case behavior. Furthermore the new algorithm gives epsilon2q+1\\epsilon^{2q+1}epsilon2q+1 convergence for all integral qqq, the Phase-pi/3\\pi/3pi/3 search algorithm, requires qqq to be (3n−1)/2(3^{n}-1)/2(3n−1)/2, with nnn a positive integer. In the new algorithm, the operations are controlled in a special way by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations.
The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-π/3π/3π/3 search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from εεε to ε2q+1ε^{2q+1}ε2q+1 using qqq oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-π/3π/3π/3 search algorithm but much better average-case behavior. Furthermore the new algorithm gives ε2q+1ε^{2q+1}ε2q+1 convergence for all integral qqq, whereas the Phase-π/3π/3π/3 search algorithm requires qqq to be (3n−1)/2(3^{n}-1)/2(3n−1)/2 with nnn a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing.
The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-\pi/3 search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from \epsilon to \epsilon^{2q+1} using q oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-\pi/3 search algorithm but much better average-case behavior. Furthermore the new algorithm gives \epsilon^{2q+1} convergence for all integral q, whereas the Phase-\pi/3 search algorithm requires q to be (3^{n}-1)/2 with n a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing.
Ordered search is the problem of locating a target element in a sorted list of size nnn using comparison queries. Classically, binary search requires ⌈log⁡2n⌉\lceil \log_2 n\rceil⌈log2​n⌉ queries, which is optimal. Quantum algorithms offer a constant-factor speedup, but the precise constant has been a longstanding open question. We close this gap by exhibiting two new quantum algorithms for ordered search, each using the optimal 1πln⁡n+o(log⁡n)\frac{1}π\ln n+o(\log n)π1​lnn+o(logn) queries. The first, discovered by Claude Fable 5, is a simple zero-error algorithm derived from a continuum relaxation of the problem. The second, discovered by GPT-5.6-Sol (informed by Claude's zero-error algorithm), is an exact algorithm based on an analytic solution of the polynomial program of Farhi, Goldstone, Gutmann, and Sipser.
The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of π3\fracπ{3}3π​. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using qqq oracle queries, these variations reduce the probability of finding a non-target state from εεε to ε2q+1ε^{2q+1}ε2q+1, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.
The quantum search algorithm consists of an iterative sequence of selective inversions and diffusion type operations, as a result of which it is able to find a state with desired properties (target state) in an unsorted database of size N in only sqrt[N] queries. This is achieved by designing the iterative transformations in a way that each iteration results in a small rotation of the state vector in a two-dimensional Hilbert space that includes the target state; if we choose the right number of iterative steps, we will stop just at the target state. This Letter shows that by replacing the selective inversions by selective phase shifts of pi/3, the algorithm preferentially converges to the target state irrespective of the step size or number of iterations. This feature leads to robust search algorithms and also to new schemes for quantum control and error correction.
Grover's quantum search algorithm provides a fundamental quadratic speedup for unstructured datasets, reducing query complexity from O(N)\mathcal{O}(N)O(N) to O(N)\mathcal{O}(\sqrt{N})O(N​). However, the algorithm's reliance on precise iteration counts leads to the ``soufflé problem,'' where over-rotation results in a sharp decline in success probability. This limitation is particularly restrictive when the number of solution states, MMM, is unknown. In this work, we present an ancilla-mediated fixed-point quantum search algorithm that achieves robust convergence by mapping the solution amplitude to a dedicated ancilla qubit. Unlike existing phase-matching fixed-point methods, our approach utilizes Grover's real-plane reflections, thereby maintaining the intuitive geometric architecture of the original algorithm. We demonstrate that this method achieves a success probability of at least 92.6%92.6\%92.6% with a query complexity of approximately O(N/M)\mathcal{O}(\sqrt{N/M})O(N/M​), effectively bridging the gap between standard amplitude amplification and robust fixed-point convergence.