A Grover-compatible manifold optimization algorithm for quantum search

• URL: http://arxiv.org/abs/2512.08432v2
• Date: Fri, 12 Dec 2025 13:44:28 GMT
• Title: A Grover-compatible manifold optimization algorithm for quantum search
• Authors: Zhijian Lai, Dong An, Jiang Hu, Zaiwen Wen,
• Abstract summary: Grover's algorithm is a fundamental quantum algorithm that offers a quadratic speedup for the unstructured search problem.<n>We show that Grover's algorithm matches the speedup of $O(qrstN)$ achieved by Grover's algorithm.
• Score: 17.013842168748127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Grover's algorithm is a fundamental quantum algorithm that offers a quadratic speedup for the unstructured search problem by alternately applying physically implementable oracle and diffusion operators. In this paper, we reformulate the unstructured search as a maximization problem on the unitary manifold and solve it via the Riemannian gradient ascent (RGA) method. To overcome the difficulty that generic RGA updates do not, in general, correspond to physically implementable quantum operators, we introduce Grover-compatible retractions to restrict RGA updates to valid oracle and diffusion operators. Theoretically, we establish a local Riemannian $μ$-Polyak-Łojasiewicz (PL) inequality with $μ= \tfrac{1}{2}$, which yields a linear convergence rate of $1 - κ^{-1}$ toward the global solution. Here, the condition number $κ= L_{\mathrm{Rie}} / μ$, where $L_{\mathrm{Rie}}$ denotes the Riemannian Lipschitz constant of the gradient. Taking into account both the geometry of the unitary manifold and the special structure of the cost function, we show that $L_{\mathrm{Rie}} = O(\sqrt{N})$ for problem size $N = 2^n$. Consequently, the resulting iteration complexity is $O(\sqrt{N} \log(1/\varepsilon))$ for attaining an $\varepsilon$-accurate solution, which matches the quadratic speedup of $O(\sqrt{N})$ achieved by Grover's algorithm. These results demonstrate that an optimization-based viewpoint can offer fresh conceptual insights and lead to new advances in the design of quantum algorithms.

Related papers

• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank computation.<n>We show that the time complexity of such localized methods is upper bounded by $mintildemathcalO(R2/epsilon2), tildemathcalO(m)$ to obtain an $epsilon$-approximation of the PPR vector.
  arXiv  Detail & Related papers  (2025-10-09T09:47:40Z)
• Quantum Algorithms for Projection-Free Sparse Convex Optimization [32.34794896079469]
  For the vector domain, we propose two quantum algorithms for sparse constraints that find a $varepsilon$-optimal solution with the query complexity of $O(sqrtd/varepsilon)$.<n>For the matrix domain, we propose two quantum algorithms for nuclear norm constraints that improve the time complexity to $tildeO(rd/varepsilon2)$ and $tildeO(sqrtrd/varepsilon3)$.
  arXiv  Detail & Related papers  (2025-07-11T12:43:58Z)
• Quantum Algorithm for the Fixed-Radius Neighbor Search [39.58317527488534]
  We propose a quantum algorithm for the Fixed RAdius Neighbor Search problem (FRANS) based on the fixed-point version of Grover's algorithm.<n>We derive an efficient circuit for solving the FRANS with linear query complexity with the number of particles $N$.<n>We assess the resilience of the model to the readout error, suggesting an error correction-free strategy to check the accuracy of the results.
  arXiv  Detail & Related papers  (2025-07-04T10:01:10Z)
• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  This paper considers the problem for finding the $(,epsilon)$-Goldstein stationary point of Lipschitz continuous objective. We construct a zeroth-order quantum estimator for the surrogate oracle function.
  arXiv  Detail & Related papers  (2024-10-21T16:52:26Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  We propose a new class of fast Krasnoselkii--Mann methods with variance reduction to solve a finite-sum co-coercive equation $Gx = 0$.<n>Our algorithm is single-loop and leverages a new family of unbiased variance-reduced estimators specifically designed for a wider class of root-finding algorithms.<n> numerical experiments validate our algorithms and demonstrate their promising performance compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-06-04T15:23:29Z)
• A quantum central path algorithm for linear optimization [5.450016817940232]
  We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. This approach yields an algorithm for solving linear optimization problems involving $m$ constraints and $n$ variables to $varepsilon$-optimality. In the standard gate model (i.e., without access to quantum RAM), our algorithm can obtain highly-precise solutions to LO problems using at most $$mathcalO left( sqrtm + n textsfnnz (A) fracR_1
  arXiv  Detail & Related papers  (2023-11-07T13:26:20Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Quantum Algorithms for Ground-State Preparation and Green's Function Calculation [5.28670135448572]
  We present projective quantum algorithms for ground-state preparation and calculations of the many-body Green's functions in frequency domain. The algorithms are based on the linear combination of unitary (LCU) operations and essentially only use quantum resources.
  arXiv  Detail & Related papers  (2021-12-10T18:39:55Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.