Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search
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_ | 1866918426099843072 |
|---|---|
| author | Lai, Zhijian An, Dong Hu, Jiang Wen, Zaiwen |
| author_facet | Lai, Zhijian An, Dong Hu, Jiang Wen, Zaiwen |
| contents | Grover's algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems of size $N$. Recent studies have reformulated this task as a maximization problem on the unitary manifold and solved it via linearly convergent Riemannian gradient ascent (RGA) methods, resulting in a complexity of $O(\sqrt{N/M} \log (1/\varepsilon))$, where $M$ denotes the number of target items. In this work, we adopt the Riemannian modified Newton (RMN) method to solve the quantum search problem, under the assumption that the ratio $ M/N$ is known. We show that, in this setting, the Riemannian Newton direction is collinear with the Riemannian gradient in the sense that the Riemannian gradient is always an eigenvector of the corresponding Riemannian Hessian. As a result, without additional overhead, the proposed RMN method numerically achieves a quadratic convergence rate with respect to the error $\varepsilon$, implying a complexity of $O(\sqrt{N/M} \log\log (1/\varepsilon))$. Furthermore, our approach remains Grover-compatible, namely, it relies exclusively on the standard Grover diffusion and oracle operators to ensure algorithmic implementability, and its parameter update process can be efficiently precomputed on classical computers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26039 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search Lai, Zhijian An, Dong Hu, Jiang Wen, Zaiwen Quantum Physics Mathematical Physics Optimization and Control 81P68, 90C26, 65K10 F.2.2; G.1.6 Grover's algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems of size $N$. Recent studies have reformulated this task as a maximization problem on the unitary manifold and solved it via linearly convergent Riemannian gradient ascent (RGA) methods, resulting in a complexity of $O(\sqrt{N/M} \log (1/\varepsilon))$, where $M$ denotes the number of target items. In this work, we adopt the Riemannian modified Newton (RMN) method to solve the quantum search problem, under the assumption that the ratio $ M/N$ is known. We show that, in this setting, the Riemannian Newton direction is collinear with the Riemannian gradient in the sense that the Riemannian gradient is always an eigenvector of the corresponding Riemannian Hessian. As a result, without additional overhead, the proposed RMN method numerically achieves a quadratic convergence rate with respect to the error $\varepsilon$, implying a complexity of $O(\sqrt{N/M} \log\log (1/\varepsilon))$. Furthermore, our approach remains Grover-compatible, namely, it relies exclusively on the standard Grover diffusion and oracle operators to ensure algorithmic implementability, and its parameter update process can be efficiently precomputed on classical computers. |
| title | Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search |
| topic | Quantum Physics Mathematical Physics Optimization and Control 81P68, 90C26, 65K10 F.2.2; G.1.6 |
| url | https://arxiv.org/abs/2603.26039 |