Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911601625399296 |
|---|---|
| author | Zhang, Kun Chen, Kang-Yuan Wang, Xiao-Hui Korepin, Vladimir |
| author_facet | Zhang, Kun Chen, Kang-Yuan Wang, Xiao-Hui Korepin, Vladimir |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15886 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm Zhang, Kun Chen, Kang-Yuan Wang, Xiao-Hui Korepin, Vladimir Quantum Physics 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. |
| title | Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2604.15886 |