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:2507.15797

Deterministic Quantum Search via Recursive Oracle Expansion

Burke, John, Ciarán McGoldrick

Published Jul 21, 2025• 2 citations
arXivHTMLPDF

Abstract

We introduce a novel deterministic quantum search algorithm that provides a practical alternative to conventional probabilistic search approaches. Our scheme eliminates the inherent uncertainty of quantum search without relying on arbitrary phase rotations, a key limitation of other deterministic methods. The algorithm achieves certainty by recursively expanding the base oracle so that it marks all states prefixed by the same two bits as the target, encompassing exactly one-quarter of the search space. This enables a step-by-step reduction of the superposition until the target state can be measured with certainty. The algorithm achieves deterministic success with a query complexity of $O(N^{\log_2(3)/2}) \approx O(N^{0.7925})$, falling between Grover's $O(\sqrt{N})$ scaling and the classical $O(N)$. Our approach relies exclusively on two-qubit nearest-neighbour diffusion operators, avoiding global diffusion entirely. We show that, despite the increased query complexity, this design reduces the total number of two-qubit gates required for diffusion by more than an order of magnitude for search spaces up to at least 18 qubits, with even greater advantages on hardware with limited qubit connectivity. The scheme's inherent determinism, reliance on simple nearest-neighbour, low-depth operations, and scalable recursive structure make it well-suited for hardware implementation. Additionally, we show that the algorithm naturally supports partial database search, enabling deterministic identification of selected target bits without requiring a full search, further broadening its applicability.

Related papers

Quantum Search without Global Diffusion

John Burke, Ciaran McGoldrick

Quantum search is among the most important algorithms in quantum computing. At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search by combining two global reflections: the oracle, which marks the target, and the diffusion operator, which reflects about the initial state. We show that this speedup can be preserved when the oracle is the only global operator, with all other operations acting locally on non-overlapping partitions of the search register. We present a recursive construction that, when the initial and target states both decompose as tensor products over these chosen partitions, admits an exact closed-form solution for the algorithm's dynamics. This is enabled by an intriguing degeneracy in the principal angles between successive reflections, which collapse to just two distinct values governed by a single recursively defined angle. Applied to unstructured search, a problem that naturally satisfies the tensor decomposition, the approach retains the $O(\sqrt{N})$ oracle complexity of Grover search when each partition contains at least $\log_2(\log_2 N)$ qubits. On an 18-qubit search problem, partitioning into two stages reduces the non-oracle circuit depth by as much as 51%-96% relative to Grover, requiring up to 9% additional oracle calls. For larger problem sizes this oracle overhead rapidly diminishes, and valuable depth reductions persist when the oracle circuit is substantially deeper than the diffusion operator. More broadly, these results show that a global diffusion operator is not necessary to achieve the quadratic speedup in quantum search, offering a new perspective on this foundational algorithm. Moreover, the scalar reduction at the heart of our analysis inspires and motivates new directions and innovations in quantum algorithm design and evaluation.

quant-pharXiv:2604.15435•Apr 20, 2026•2 citations

Near‐Deterministic Quantum Search Algorithm Without Phase Design

Zhen Wang, Kun Zhang, V. E. Korepin

Abstract Grover's algorithm solves the unstructured search problem. Grover's algorithm can find the target state with certainty only if searching one out of four. Designing the deterministic search algorithm can avoid any repetition of the algorithm, especially when Grover's algorithm is a subroutine in other algorithms. Grover's algorithm can be deterministic if the phase of the oracle or the diffusion operator is delicately designed. The precision of the phases could be a problem. A near‐deterministic quantum search algorithm without the phase design is proposed. The algorithm has the same oracle and diffusion operators as Grover's algorithm. One additional component is the rescaled diffusion operator. It acts partially on the database. The success probability of Grover's algorithm is improved by the partial diffusion operator in two different ways. The possible cost is one or two more queries to the oracle. The deterministic search algorithm is also designed when searching one out of eight, sixteen, and thirty‐two.

arXiv:2407.10748•Advanced Quantum Technologies•Jan 3, 2025•6 citations

Hardware Efficient Quantum Search Algorithm

Ji Liu, Huiyang Zhou

Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

arXiv:2103.14196•Mar 26, 2021•15 citations

Deterministic Grover search with a restricted oracle

Tanay Roy, Liang Jiang, David Schuster

Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms across a broad class of unstructured search problems.The original protocol is probabilistic, returning the desired result with significant probability on each query but, in general, requiring several iterations of the algorithm.We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.Our deterministic, two-parameter "D2p" protocol utilizes generalized phase rotations replacing the phase inversions after a standard oracle query.The D2p protocol achieves a 100% success rate in no more than one additional iteration compared to the optimal number of steps as in the original Grover's search enabling the same quadratic speedup.We also provide a visualization using the Bloch sphere for enhanced geometric intuition.

arXiv:2201.00091•Physical Review Research•Apr 21, 2022•67 citations

Exact and Optimal Recursive Quantum Search via Hilbert-Space Decomposition

John Burke, Ciaran McGoldrick

Current approaches to quantum search fail to deeply exploit extant structure in the underlying Hilbert space. Decomposing the search by this structure empowers new strategies and formulations for quantum search and algorithm design. We present a new decomposition technique acting directly on this structure by recursively decomposing the Hilbert space and constructing the search operator from reflections over the resulting partition. When initial and target states factorise over this partition, dynamics reduce to a single rotation in a two-dimensional plane at each level, with angle given by a scalar recurrence. This recurrence avoids error accumulation from separately bounding success probabilities at each level, yielding an exact state description enabling treatment of the recursion as a whole. We obtain the target state deterministically and derive oracle and non-oracle costs independently of the search setting. For unstructured search, our approach attains the simultaneously optimal $Θ(\sqrt{N})$ oracle and non-oracle gate counts. For spatial search on $d$-dimension grids, it recovers the $O(\sqrt{N})$ time for $d\geq3$ and the $O\bigl(\sqrt{N}(\log N)^{3/2}\bigr)$ bound of Aaronson and Ambainis for $d=2$. The exact description of the recursion extends over our decomposition to new subdivision structures and provides a new approach for applying and analysing recursion in quantum algorithm design.

quant-pharXiv:2608.23002•Aug 25, 2026•1 citation

Deterministic quantum search with adjustable parameters: Implementations and applications

Guanzhong Li, Lvzhou Li

Abstract Grover's algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. The original algorithm is probabilistic, returning a marked element with bounded error. When it is known beforehand there are M marked elements in N elements, there exist several schemes to achieve the exact version that returns a marked element with certainty, by using the generalized Grover's iteration G(α, β) := Sr(β) So(α), where the phase oracle So(α) multiplies a marked state by eiα, and the phase rotation Sr(β) multiplies the initial state |ψ0⟩ (an equal-superposition of all states) by e-iβ.However, in all the existing schemes the value range of α and β is limited; for instance, in the three early schemes α and β are determined by M/N. Thus, a natural question arises: Given the phase oracle So(α) with an arbitrary angle α, or the phase rotation Sr(β) with an arbitrary angle β, can we always construct an exact search algorithm without sacrificing the quadratic speedup advantage? The significance of this problem lies not only in the expansion of mathematical form, but also in its application value. We answer the question affirmatively, by presenting a search framework with adjustable parameters. Technically, we propose the fixed-axis-rotation (FXR) method where each iteration of the search algorithm can be geometrically seen as rotating about a fixed axis on the Bloch sphere. Furthermore, two applications of the proposed search framework are developed: the first is to learn exactly the secret string hidden by the Hamming distance oracle, and the other to solve the element distinctness promise problem deterministically. The two applications correspond to the two different cases where α or β is fixed respectively.

arXiv:2210.12644•Information and Computation•Apr 24, 2023•24 citations
We introduce a novel deterministic quantum search algorithm that provides a practical alternative to conventional probabilistic search approaches. Our scheme eliminates the inherent uncertainty of quantum search without relying on arbitrary phase rotations, a key limitation of other deterministic methods. The algorithm achieves certainty by recursively expanding the base oracle so that it marks all states prefixed by the same two bits as the target, encompassing exactly one-quarter of the search space. This enables a step-by-step reduction of the superposition until the target state can be measured with certainty. The algorithm achieves deterministic success with a query complexity of O(Nlog⁡2(3)/2)≈O(N0.7925)O(N^{\log_2(3)/2}) \approx O(N^{0.7925})O(Nlog2​(3)/2)≈O(N0.7925), falling between Grover's O(N)O(\sqrt{N})O(N​) scaling and the classical O(N)O(N)O(N). Our approach relies exclusively on two-qubit nearest-neighbour diffusion operators, avoiding global diffusion entirely. We show that, despite the increased query complexity, this design reduces the total number of two-qubit gates required for diffusion by more than an order of magnitude for search spaces up to at least 18 qubits, with even greater advantages on hardware with limited qubit connectivity. The scheme's inherent determinism, reliance on simple nearest-neighbour, low-depth operations, and scalable recursive structure make it well-suited for hardware implementation. Additionally, we show that the algorithm naturally supports partial database search, enabling deterministic identification of selected target bits without requiring a full search, further broadening its applicability.
Quantum search is among the most important algorithms in quantum computing. At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search by combining two global reflections: the oracle, which marks the target, and the diffusion operator, which reflects about the initial state. We show that this speedup can be preserved when the oracle is the only global operator, with all other operations acting locally on non-overlapping partitions of the search register. We present a recursive construction that, when the initial and target states both decompose as tensor products over these chosen partitions, admits an exact closed-form solution for the algorithm's dynamics. This is enabled by an intriguing degeneracy in the principal angles between successive reflections, which collapse to just two distinct values governed by a single recursively defined angle. Applied to unstructured search, a problem that naturally satisfies the tensor decomposition, the approach retains the O(N)O(\sqrt{N})O(N​) oracle complexity of Grover search when each partition contains at least log⁡2(log⁡2N)\log_2(\log_2 N)log2​(log2​N) qubits. On an 18-qubit search problem, partitioning into two stages reduces the non-oracle circuit depth by as much as 51%-96% relative to Grover, requiring up to 9% additional oracle calls. For larger problem sizes this oracle overhead rapidly diminishes, and valuable depth reductions persist when the oracle circuit is substantially deeper than the diffusion operator. More broadly, these results show that a global diffusion operator is not necessary to achieve the quadratic speedup in quantum search, offering a new perspective on this foundational algorithm. Moreover, the scalar reduction at the heart of our analysis inspires and motivates new directions and innovations in quantum algorithm design and evaluation.
Abstract Grover's algorithm solves the unstructured search problem. Grover's algorithm can find the target state with certainty only if searching one out of four. Designing the deterministic search algorithm can avoid any repetition of the algorithm, especially when Grover's algorithm is a subroutine in other algorithms. Grover's algorithm can be deterministic if the phase of the oracle or the diffusion operator is delicately designed. The precision of the phases could be a problem. A near‐deterministic quantum search algorithm without the phase design is proposed. The algorithm has the same oracle and diffusion operators as Grover's algorithm. One additional component is the rescaled diffusion operator. It acts partially on the database. The success probability of Grover's algorithm is improved by the partial diffusion operator in two different ways. The possible cost is one or two more queries to the oracle. The deterministic search algorithm is also designed when searching one out of eight, sixteen, and thirty‐two.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.
Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms across a broad class of unstructured search problems.The original protocol is probabilistic, returning the desired result with significant probability on each query but, in general, requiring several iterations of the algorithm.We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.Our deterministic, two-parameter "D2p" protocol utilizes generalized phase rotations replacing the phase inversions after a standard oracle query.The D2p protocol achieves a 100% success rate in no more than one additional iteration compared to the optimal number of steps as in the original Grover's search enabling the same quadratic speedup.We also provide a visualization using the Bloch sphere for enhanced geometric intuition.
Current approaches to quantum search fail to deeply exploit extant structure in the underlying Hilbert space. Decomposing the search by this structure empowers new strategies and formulations for quantum search and algorithm design. We present a new decomposition technique acting directly on this structure by recursively decomposing the Hilbert space and constructing the search operator from reflections over the resulting partition. When initial and target states factorise over this partition, dynamics reduce to a single rotation in a two-dimensional plane at each level, with angle given by a scalar recurrence. This recurrence avoids error accumulation from separately bounding success probabilities at each level, yielding an exact state description enabling treatment of the recursion as a whole. We obtain the target state deterministically and derive oracle and non-oracle costs independently of the search setting. For unstructured search, our approach attains the simultaneously optimal Θ(N)Θ(\sqrt{N})Θ(N​) oracle and non-oracle gate counts. For spatial search on ddd-dimension grids, it recovers the O(N)O(\sqrt{N})O(N​) time for d≥3d\geq3d≥3 and the O(N(log⁡N)3/2)O\bigl(\sqrt{N}(\log N)^{3/2}\bigr)O(N​(logN)3/2) bound of Aaronson and Ambainis for d=2d=2d=2. The exact description of the recursion extends over our decomposition to new subdivision structures and provides a new approach for applying and analysing recursion in quantum algorithm design.
Abstract Grover's algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. The original algorithm is probabilistic, returning a marked element with bounded error. When it is known beforehand there are M marked elements in N elements, there exist several schemes to achieve the exact version that returns a marked element with certainty, by using the generalized Grover's iteration G(α, β) := Sr(β) So(α), where the phase oracle So(α) multiplies a marked state by eiα, and the phase rotation Sr(β) multiplies the initial state |ψ0⟩ (an equal-superposition of all states) by e-iβ.However, in all the existing schemes the value range of α and β is limited; for instance, in the three early schemes α and β are determined by M/N. Thus, a natural question arises: Given the phase oracle So(α) with an arbitrary angle α, or the phase rotation Sr(β) with an arbitrary angle β, can we always construct an exact search algorithm without sacrificing the quadratic speedup advantage? The significance of this problem lies not only in the expansion of mathematical form, but also in its application value. We answer the question affirmatively, by presenting a search framework with adjustable parameters. Technically, we propose the fixed-axis-rotation (FXR) method where each iteration of the search algorithm can be geometrically seen as rotating about a fixed axis on the Bloch sphere. Furthermore, two applications of the proposed search framework are developed: the first is to learn exactly the secret string hidden by the Hamming distance oracle, and the other to solve the element distinctness promise problem deterministically. The two applications correspond to the two different cases where α or β is fixed respectively.