Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search

Quantum Physics [Submitted on 27 Mar 2026] Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search Zhijian Lai, Dong An, Jiang Hu, Zaiwen Wen 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}\log (1/\varepsilon)). In this work, we adopt the Riemannian modified Newton (RMN) method to solve the quantum search problem. We show that, in the setting of quantum search, 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 error \varepsilon, implying a complexity of O(\sqrt{N}\log\log (1/\varepsilon)), which is double-logarithmic in precision. Furthermore, our approach remains Grover-compatible, namely, it relies exclusively on the standard Grover oracle and diffusion operators to ensure algorithmic implementability, and its parameter update process can be efficiently precomputed on classical computers. Comments: 15 pages, 5 figures Subjects: Quantum Physics (quant-ph); Mathematical Physics (math-ph); Optimization and Control (math.OC) MSC classes: 81P68, 90C26, 65K10 ACM classes: F.2.2; G.1.6 Cite as: arXiv:2603.26039 [quant-ph]   (or arXiv:2603.26039v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2603.26039 Focus to learn more Submission history From: Zhijian Lai [view email] [v1] Fri, 27 Mar 2026 03:19:27 UTC (93 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-03 Change to browse by: math math-ph math.MP math.OC References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)