Circuit-depth optimization of quantum partial-search algorithms
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.
Related
- Towards Reproducible Evaluation of Distributed Quantum Circuit Partitioning Algorithms
- Quantum algorithms for the exponentiation of Toeplitz matrices and applications in partial differential equations
- Optimal Quantum Algorithms for Ordered Search
- Circuit Synthesis for Variational Quantum Algorithms: The Depth of Algebra and Geometry
- When is global evolutionary search useful for variational quantum algorithms? A landscape-first study
BibTeX
@misc{jiang2026circuitdepth,
title = {{Circuit-depth optimization of quantum partial-search algorithms}},
author = {Yan-Bo Jiang and Xiao-Hui Wang and Kun Zhang and Vladimir Korepin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28147},
eprint = {2609.28147},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28147},
}
RIS
TY - UNPB
TI - Circuit-depth optimization of quantum partial-search algorithms
AU - Yan-Bo Jiang
AU - Xiao-Hui Wang
AU - Kun Zhang
AU - Vladimir Korepin
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28147
UR - https://arxiv.org/abs/2609.28147
AB - 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.
ER -