arXiv:2609.28147
Circuit-depth optimization of quantum partial-search algorithms
Yan-Bo Jiang, Xiao-Hui Wang, Kun Zhang, Vladimir Korepin
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.
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