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

Circuit-depth optimization of quantum partial-search algorithms

Yan-Bo Jiang, Xiao-Hui Wang, Kun Zhang, Vladimir Korepin

quant-phSubmitted Sep 23, 2026• Announced Sep 24, 2026• 0 citations
arXivHTMLPDF

Abstract

Grover's algorithm is optimal in terms of oracle queries. We can trade accuracy for speed, which gives rise to the quantum partial-search algorithm. The partial-search algorithm is implemented using two kinds of Grover operators, global and local, where the former is the standard Grover operator for full search and the latter has a diffusion operator acting on the search subspace. The global-local-global sequence, also known as the Grover-Radhakrishnan-Korepin (GRK) algorithm, has been proved optimal in the oracle-query metric. In this work, we show that the alternating sequence of global and local Grover operators, formed by repeatedly applying a fixed product of global and local Grover operators, can achieve a lower expected circuit depth than the GRK algorithm. Through systematic analysis, we obtain its exact success probability, expected depth, and asymptotically optimal parameters. We derive the boundary, characterized by the ratio between the depths of the oracle and the global diffusion operator, separating the depth-optimal and oracle-optimal partial-search algorithms. When the depths of the oracle and the global diffusion operator are comparable, our proposed alternating partial-search sequence can reduce the minimum expected circuit depth by more than 20\% compared with the GRK algorithm.

AI Summary

Quantum partial search identifies the block containing a marked item rather than the item itself. This paper asks whether the query-optimal Grover–Radhakrishnan–Korepin (GRK) sequence also minimizes expected circuit depth when global and within-block diffusion have different costs. It studies repeated local–global units, $S_{\mathcal A}=(G_nG_m^{\tilde k})^k$, using the metric $\ell(S)/p(S)$ and oracle-to-global-diffusion depth ratio $\alpha$. Exhaustive enumeration at $N=2^{10}$ motivates an alternating family with an additional edge operator. An $O(3)$ analysis of the three-dimensional invariant search subspace gives an exact success probability for the strictly repeated sequence. Asymptotic optimization yields $\tilde k=\Theta((qb)^{1/3})$ and $k=\Theta(\sqrt N(qb)^{-1/3})$, where $b$ is block size and $q=(\ell_n-\ell_m)/(\alpha\ell_n+\ell_m)$, in the regime $b^{-1}\ll q\ll b^{1/2}$. The leading expected depth is $0.6900(\alpha\ell_n+\ell_m)\sqrt N$. Integer-boundary and single-iteration regimes are also analyzed. Comparison with depth-optimized GRK gives crossover equations. Under linear diffusion-depth scaling, $\alpha=1$, $n=20$, and $m=10$, numerical depth reductions are $19.85\%$ for the repeated sequence and $20.73\%$ with edge optimization; the repeated-sequence reduction approaches $25\%$ along $m=n/2$. The depth model adds operator costs and excludes block-verification costs, treated as classical. Global depth optimality beyond the enumerated instances is not proved; unrestricted asymptotic edge optimization remains open, and some crossover formulas are explicitly formal boundary-scale continuations. Multiple targets and nonuniform initial states are left for future work.

Little sign of AI-generated textIncrementalStrong assumptionsOverclaims

Central claim may not hold: The advertised boundary between depth-optimal and oracle-optimal partial search is established only as a comparison between restricted sequence families, without a global depth-optimality theorem. At n=20 and m=10, the reported alternating-versus-GRK crossing is 20.48 while the edge-corrected-family crossing is 511, demonstrating that the alternating-family boundary cannot describe the general transition to GRK optimality. The numerical exclusion bound gives a cutoff of 32 rather than 24 for n=10, m=2, alpha=1, so it does not certify the claimed exhaustive optimization over all potentially improving sequences.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
20 pages, 7 figures

Related papers

Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm

Kun Zhang, Kang-Yuan Chen, Xiao-Hui Wang +1 more

Grover's algorithm is a cornerstone of quantum algorithms and is strictly optimal in oracle-query complexity. While the full search problem admits no further improvement, one may trade accuracy for speed in the partial search problem, where the task is to identify only the block containing the target item. The best known quantum algorithm for the partial search problem is the Grover-Radhakrishnan-Korepin (GRK) algorithm, whose optimality has long been conjectured but not proved. In this work, we prove the optimality of GRK in the large-block limit. We formulate partial search as a time-optimal control problem and apply the Pontryagin maximum principle to derive the switching-function dynamics, establish the bang-bang structure of regular extremals, and exclude non-optimal switching patterns. As a result, we show that the optimal regular extremal has the global-local-global form, which yields a control-theoretic proof of the asymptotic optimality of the GRK algorithm in oracle-query complexity.

quant-pharXiv:2604.15886•Journal of Physics A Mathematical and Theoretical•Apr 20, 2026•1 citation

Asymptotic bounds on quantum partial search algorithm and its applications to parallel search

Yan-Bo Jiang, Xiao-Hui Wang, Kun Zhang +1 more

Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.

quant-pharXiv:2603.01462•Physical Review A•Mar 3, 2026•2 citations

Palindromic structure of depth-efficient quantum search algorithms

Kun Zhang, Hai-Long Shi, Xiao-Hui Wang +1 more

Grover's algorithm is optimal in query complexity, but not necessarily in circuit depth. We formulate unstructured quantum search as a circuit-depth optimization problem and identify a critical depth ratio separating query optimality from depth optimality. The resulting depth-efficient search operators exhibit a palindromic structure, in which shallow diffusion-like operators symmetrically replace selected Grover diffusion layers while preserving efficient amplitude amplification. This structure yields a simple depth-efficiency criterion and an analytic expression for the minimal expected depth. Applying the framework to $X$-type mixers, local diffusion operators, and nested local diffusion operators, we obtain substantial depth reductions over standard Grover search. In particular, nested local constructions reduce the total circuit depth by about $40\%$ when the oracle and Grover diffusion operators have comparable depth. These results reveal the resource-dependent nature of quantum-search optimality and establish palindromic constructions as a systematic route to depth-efficient quantum search algorithms.

quant-pharXiv:2606.00960•Jun 2, 2026•1 citation

HIERARCHICAL QUANTUM SEARCH

V. E. Korepin, YING XU

Database search has wide applications and is used as a subroutine in many important algorithms. In this paper, we will consider a database with a single target item. Quantum algorithm (Grover) locates the target item faster than any classical algorithm. In addition to a full (Grover) search, it frequently occurs that one is looking for a group of items (a block) containing the target item, rather than the target item itself. This problem is known as partial search. As a generalization of the full search, partial search is of particular importance in practice. Partial search trades accuracy for speed, i.e., it works faster than a full search. There exists different versions of partial search. We will study the optimized version of the algorithm discovered by Grover and Radhakrishnan and call it GRK. GRK can be applied successively (in a sequence). First, the database is partitioned into blocks and GRK is applied to find the target block. This target block is then partitioned into subblocks and GRK is used again to find the target subblock. This procedure can be repeated if the database is large enough. (This sequence of GRK's is called a hierarchy.) Another possibility is to partition the database into subblocks directly and use GRK to find the target subblock once. In this paper, we will prove that the latter is faster (makes less queries to the Oracle).

International Journal of Modern Physics B•Dec 20, 2007•9 citations

QUANTUM SEARCH ALGORITHMS

V. E. Korepin, YING XU

This article reviews recent progress in quantum database search algorithms. The subject is presented in a self-contained and pedagogical way. The problem of searching a large database (a Hilbert space) for a target item is performed by the famous Grover algorithm which locates the target item with high probability and a quadratic speed-up compared with the corresponding classical algorithm. If the database is partitioned into blocks and one is searching for the block containing the target item instead of the target item itself, then the problem is referred to as partial search. Partial search trades accuracy for speed and the most efficient version is the Grover–Radhakrishnan–Korepin (GRK) algorithm. The target block can be further partitioned into sub-blocks so that GRK's can be performed in a sequence called a hierarchy. We study the Grover search and GRK partial search in detail and prove that a GRK hierarchy is less efficient than a direct GRK partial search. Both the Grover search and the GRK partial search can be generalized to the case with several target items (or target blocks for a GRK). The GRK partial search algorithm can also be represented in terms of group theory.

International Journal of Modern Physics B•Dec 20, 2009•7 citations

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
Grover's algorithm is optimal in terms of oracle queries. We can trade accuracy for speed, which gives rise to the quantum partial-search algorithm. The partial-search algorithm is implemented using two kinds of Grover operators, global and local, where the former is the standard Grover operator for full search and the latter has a diffusion operator acting on the search subspace. The global-local-global sequence, also known as the Grover-Radhakrishnan-Korepin (GRK) algorithm, has been proved optimal in the oracle-query metric. In this work, we show that the alternating sequence of global and local Grover operators, formed by repeatedly applying a fixed product of global and local Grover operators, can achieve a lower expected circuit depth than the GRK algorithm. Through systematic analysis, we obtain its exact success probability, expected depth, and asymptotically optimal parameters. We derive the boundary, characterized by the ratio between the depths of the oracle and the global diffusion operator, separating the depth-optimal and oracle-optimal partial-search algorithms. When the depths of the oracle and the global diffusion operator are comparable, our proposed alternating partial-search sequence can reduce the minimum expected circuit depth by more than 20% compared with the GRK algorithm.
Quantum partial search identifies the block containing a marked item rather than the item itself. This paper asks whether the query-optimal Grover–Radhakrishnan–Korepin (GRK) sequence also minimizes expected circuit depth when global and within-block diffusion have different costs. It studies repeated local–global units, SA=(GnGmk~)kS_{\mathcal A}=(G_nG_m^{\tilde k})^kSA​=(Gn​Gmk~​)k, using the metric ℓ(S)/p(S)\ell(S)/p(S)ℓ(S)/p(S) and oracle-to-global-diffusion depth ratio α\alphaα.
Exhaustive enumeration at N=210N=2^{10}N=210 motivates an alternating family with an additional edge operator. An O(3)O(3)O(3) analysis of the three-dimensional invariant search subspace gives an exact success probability for the strictly repeated sequence. Asymptotic optimization yields k~=Θ((qb)1/3)\tilde k=\Theta((qb)^{1/3})k~=Θ((qb)1/3) and k=Θ(N(qb)−1/3)k=\Theta(\sqrt N(qb)^{-1/3})k=Θ(N​(qb)−1/3), where bbb is block size and q=(ℓn−ℓm)/(αℓn+ℓm)q=(\ell_n-\ell_m)/(\alpha\ell_n+\ell_m)q=(ℓn​−ℓm​)/(αℓn​+ℓm​), in the regime b−1≪q≪b1/2b^{-1}\ll q\ll b^{1/2}b−1≪q≪b1/2. The leading expected depth is 0.6900(αℓn+ℓm)N0.6900(\alpha\ell_n+\ell_m)\sqrt N0.6900(αℓn​+ℓm​)N​. Integer-boundary and single-iteration regimes are also analyzed.
Comparison with depth-optimized GRK gives crossover equations. Under linear diffusion-depth scaling, α=1\alpha=1α=1, n=20n=20n=20, and m=10m=10m=10, numerical depth reductions are 19.85%19.85\%19.85% for the repeated sequence and 20.73%20.73\%20.73% with edge optimization; the repeated-sequence reduction approaches 25%25\%25% along m=n/2m=n/2m=n/2.
The depth model adds operator costs and excludes block-verification costs, treated as classical. Global depth optimality beyond the enumerated instances is not proved; unrestricted asymptotic edge optimization remains open, and some crossover formulas are explicitly formal boundary-scale continuations. Multiple targets and nonuniform initial states are left for future work.
Grover's algorithm is a cornerstone of quantum algorithms and is strictly optimal in oracle-query complexity. While the full search problem admits no further improvement, one may trade accuracy for speed in the partial search problem, where the task is to identify only the block containing the target item. The best known quantum algorithm for the partial search problem is the Grover-Radhakrishnan-Korepin (GRK) algorithm, whose optimality has long been conjectured but not proved. In this work, we prove the optimality of GRK in the large-block limit. We formulate partial search as a time-optimal control problem and apply the Pontryagin maximum principle to derive the switching-function dynamics, establish the bang-bang structure of regular extremals, and exclude non-optimal switching patterns. As a result, we show that the optimal regular extremal has the global-local-global form, which yields a control-theoretic proof of the asymptotic optimality of the GRK algorithm in oracle-query complexity.
Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.
Grover's algorithm is optimal in query complexity, but not necessarily in circuit depth. We formulate unstructured quantum search as a circuit-depth optimization problem and identify a critical depth ratio separating query optimality from depth optimality. The resulting depth-efficient search operators exhibit a palindromic structure, in which shallow diffusion-like operators symmetrically replace selected Grover diffusion layers while preserving efficient amplitude amplification. This structure yields a simple depth-efficiency criterion and an analytic expression for the minimal expected depth. Applying the framework to XXX-type mixers, local diffusion operators, and nested local diffusion operators, we obtain substantial depth reductions over standard Grover search. In particular, nested local constructions reduce the total circuit depth by about 40%40\%40% when the oracle and Grover diffusion operators have comparable depth. These results reveal the resource-dependent nature of quantum-search optimality and establish palindromic constructions as a systematic route to depth-efficient quantum search algorithms.
Database search has wide applications and is used as a subroutine in many important algorithms. In this paper, we will consider a database with a single target item. Quantum algorithm (Grover) locates the target item faster than any classical algorithm. In addition to a full (Grover) search, it frequently occurs that one is looking for a group of items (a block) containing the target item, rather than the target item itself. This problem is known as partial search. As a generalization of the full search, partial search is of particular importance in practice. Partial search trades accuracy for speed, i.e., it works faster than a full search. There exists different versions of partial search. We will study the optimized version of the algorithm discovered by Grover and Radhakrishnan and call it GRK. GRK can be applied successively (in a sequence). First, the database is partitioned into blocks and GRK is applied to find the target block. This target block is then partitioned into subblocks and GRK is used again to find the target subblock. This procedure can be repeated if the database is large enough. (This sequence of GRK's is called a hierarchy.) Another possibility is to partition the database into subblocks directly and use GRK to find the target subblock once. In this paper, we will prove that the latter is faster (makes less queries to the Oracle).
This article reviews recent progress in quantum database search algorithms. The subject is presented in a self-contained and pedagogical way. The problem of searching a large database (a Hilbert space) for a target item is performed by the famous Grover algorithm which locates the target item with high probability and a quadratic speed-up compared with the corresponding classical algorithm. If the database is partitioned into blocks and one is searching for the block containing the target item instead of the target item itself, then the problem is referred to as partial search. Partial search trades accuracy for speed and the most efficient version is the Grover–Radhakrishnan–Korepin (GRK) algorithm. The target block can be further partitioned into sub-blocks so that GRK's can be performed in a sequence called a hierarchy. We study the Grover search and GRK partial search in detail and prove that a GRK hierarchy is less efficient than a direct GRK partial search. Both the Grover search and the GRK partial search can be generalized to the case with several target items (or target blocks for a GRK). The GRK partial search algorithm can also be represented in terms of group theory.
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.