Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2507.15065

Grover's algorithm is an approximation of imaginary-time evolution

Yudai Suzuki, Marek Gluza, Jeongrak Son, Bi Hong Tiang, Nelly H. Y. Ng, Zoë Holmes

Published Jul 20, 2025• 0 citations
arXivHTMLPDF

Abstract

We reveal the power of Grover's algorithm from thermodynamic and geometric perspectives by showing that it is a product formula approximation of imaginary-time evolution (ITE), a Riemannian gradient flow on the special unitary group. This ITE formulation provides a unified perspective on Grover's algorithm, its variants and extensions to widely used quantum subroutines including amplitude amplification and oblivious amplitude amplification. Specifically, the framework explains the choice of angles in the original Grover's algorithm and $π/3$-algorithm. It also motivates a new $π/2$-algorithm, for cases a modest failure probability is acceptable, that converges faster than the $π/3$-algorithm without overshooting. Our analysis further provides a link between ITE and quantum signal processing, which yields a new implementation of the fixed-point quantum search algorithm. Moreover, the ITE formulation can systematically reproduce widely-used subroutines in modern quantum algorithms, such as (oblivious) amplitude amplification. These results collectively establish a deeper understanding of Grover's algorithm and suggest a potential role for thermodynamics and geometry in quantum algorithm design.

DOI
10.48550/arxiv.2507.15065

Related papers

Equating quantum imaginary time evolution, Riemannian gradient flows, and stochastic implementations

Nathan A. McMahon, Mahum Pervez, Christian Arenz

We identify quantum imaginary time evolution as a Riemannian gradient flow on the unitary group. We develop an upper bound for the error between the two evolutions that can be controlled through the step size of the Riemannian gradient descent that minimizes the energy of the system. We discuss implementations through adaptive quantum algorithms and present a stochastic Riemannian gradient descent algorithm in which each step is efficiently implementable on a quantum computer. We prove that for a sufficiently small step size, the stochastic evolution concentrates around the imaginary time evolution, thereby providing performance guarantees for cooling the system through stochastic Riemannian gradient descent. Finally, we show that Riemannian gradient descent can be understood as an approximation to quantum imaginary time evolution that does not employ classical optimization.

arXiv:2504.06123•Physical Review Research•Feb 25, 2026•4 citations

A Grover-compatible manifold optimization algorithm for quantum search

Zhijian Lai, Dong An, Jiang Hu +1 more

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.

quant-pharXiv:2512.08432•Dec 10, 2025•0 citations

Practical Guide to Quantum Computing: Grover's Algorithm # 4

Mikhail Pavlov

Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.

•Mar 4, 2026•0 citations

Optimizing quantum circuits with Riemannian gradient flow

Roeland Wiersema, Nathan Killoran

Variational quantum algorithms are a promising class of algorithms that can be performed on currently available quantum computers. In most settings, the free parameters of a variational circuit are optimized using a classical optimizer that updates parameters in Euclidean geometry. Since quantum circuits are elements of the special unitary group, we can consider an alternative optimization perspective that depends on the structure of this group. In this work, we investigate a Riemannian optimization scheme over the special unitary group and we discuss its implementation on a quantum computer. We illustrate that the resulting Riemannian gradient-flow algorithm has favorable optimization properties for deep circuits and that an approximate version of this algorithm can be performed on near-term hardware. We highlight the connections of our work with previously proposed heuristics like ADAPT-VQE and show that they can be understood as variants of our algorithm.

arXiv:2202.06976•Physical Review A•Jun 27, 2023•33 citations

Augmenting Imaginary-Time Evolution with Local Geometric Information

Carlos L. Benavides-Riveros, Prachi Sharma, Pietropaolo Frisoni +1 more

Imaginary-time evolution (ITE) underpins a broad family of algorithms for ground-state preparation in quantum simulation and quantum many-body physics. In these methods, convergence is governed by the energy variance of the instantaneous state, causing the flow to approach the ground state only asymptotically. We introduce an augmented imaginary-time evolution (AITE) framework that replaces the standard gradient flow on the energy landscape with a geometrically informed descent along locally optimal directions, which are identified by exploiting the higher-order statistical structure of the instantaneous energy distribution. The resulting flow strictly outperforms standard ITE throughout the entire evolution and exhibits two qualitatively distinct regimes: a superlinear convergence regime, followed by an extinction regime in which the energy error vanishes exactly at a finite value of the imaginary-time flow parameter, in contrast to the asymptotic exponential decay of ITE. Standard ITE is recovered in the zero-skewness limit of AITE, implying that the acceleration extends naturally across the broader ITE algorithmic family.

quant-pharXiv:2606.23934•Jun 24, 2026•0 citations

Amplitude Amplification Algorithms

Mithilesh Kumar, Yusuf Tahir, Daiya, Varun

This survey traces the evolution of quantum amplitude amplification from its geometric origins in Grover’s algorithm to its algebraic formulation within the Quantum Singular Value Transformation (QSVT) framework. We develop a unified mathematical formalism intended to reduce the historical fragmentation of these algorithms. By establishing a consistent notational foundation early on, framing unstructured search as rotation within an invariant two-dimensional subspace, and following the progression through oblivious, fixed-point, and distributed amplification schemes, we aim to clarify how these methods can be interpreted within the broader language of singular-value polynomial synthesis. We additionally introduce a variational template for amplitude amplification based on parameterized phase rotations, connecting amplification primitives to hybrid quantum-classical algorithms suitable for near-term quantum architectures. To support the pedagogical objectives of this survey, we provide a companion website hosting interactive visualizations and implementation details at QuantumAmplitudeAmplification.

•May 6, 2026•0 citations
We reveal the power of Grover's algorithm from thermodynamic and geometric perspectives by showing that it is a product formula approximation of imaginary-time evolution (ITE), a Riemannian gradient flow on the special unitary group. This ITE formulation provides a unified perspective on Grover's algorithm, its variants and extensions to widely used quantum subroutines including amplitude amplification and oblivious amplitude amplification. Specifically, the framework explains the choice of angles in the original Grover's algorithm and π/3π/3π/3-algorithm. It also motivates a new π/2π/2π/2-algorithm, for cases a modest failure probability is acceptable, that converges faster than the π/3π/3π/3-algorithm without overshooting. Our analysis further provides a link between ITE and quantum signal processing, which yields a new implementation of the fixed-point quantum search algorithm. Moreover, the ITE formulation can systematically reproduce widely-used subroutines in modern quantum algorithms, such as (oblivious) amplitude amplification. These results collectively establish a deeper understanding of Grover's algorithm and suggest a potential role for thermodynamics and geometry in quantum algorithm design.
We identify quantum imaginary time evolution as a Riemannian gradient flow on the unitary group. We develop an upper bound for the error between the two evolutions that can be controlled through the step size of the Riemannian gradient descent that minimizes the energy of the system. We discuss implementations through adaptive quantum algorithms and present a stochastic Riemannian gradient descent algorithm in which each step is efficiently implementable on a quantum computer. We prove that for a sufficiently small step size, the stochastic evolution concentrates around the imaginary time evolution, thereby providing performance guarantees for cooling the system through stochastic Riemannian gradient descent. Finally, we show that Riemannian gradient descent can be understood as an approximation to quantum imaginary time evolution that does not employ classical optimization.
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 μ=12μ= \tfrac{1}{2}μ=21​, which yields a linear convergence rate of 1−κ−11 - κ^{-1}1−κ−1 toward the global solution. Here, the condition number κ=LRie/μκ= L_{\mathrm{Rie}} / μκ=LRie​/μ, where LRieL_{\mathrm{Rie}}LRie​ 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 LRie=O(N)L_{\mathrm{Rie}} = O(\sqrt{N})LRie​=O(N​) for problem size N=2nN = 2^nN=2n. Consequently, the resulting iteration complexity is O(Nlog⁡(1/ε))O(\sqrt{N} \log(1/\varepsilon))O(N​log(1/ε)) for attaining an ε\varepsilonε-accurate solution, which matches the quadratic speedup of O(N)O(\sqrt{N})O(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.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.
Variational quantum algorithms are a promising class of algorithms that can be performed on currently available quantum computers. In most settings, the free parameters of a variational circuit are optimized using a classical optimizer that updates parameters in Euclidean geometry. Since quantum circuits are elements of the special unitary group, we can consider an alternative optimization perspective that depends on the structure of this group. In this work, we investigate a Riemannian optimization scheme over the special unitary group and we discuss its implementation on a quantum computer. We illustrate that the resulting Riemannian gradient-flow algorithm has favorable optimization properties for deep circuits and that an approximate version of this algorithm can be performed on near-term hardware. We highlight the connections of our work with previously proposed heuristics like ADAPT-VQE and show that they can be understood as variants of our algorithm.
Imaginary-time evolution (ITE) underpins a broad family of algorithms for ground-state preparation in quantum simulation and quantum many-body physics. In these methods, convergence is governed by the energy variance of the instantaneous state, causing the flow to approach the ground state only asymptotically. We introduce an augmented imaginary-time evolution (AITE) framework that replaces the standard gradient flow on the energy landscape with a geometrically informed descent along locally optimal directions, which are identified by exploiting the higher-order statistical structure of the instantaneous energy distribution. The resulting flow strictly outperforms standard ITE throughout the entire evolution and exhibits two qualitatively distinct regimes: a superlinear convergence regime, followed by an extinction regime in which the energy error vanishes exactly at a finite value of the imaginary-time flow parameter, in contrast to the asymptotic exponential decay of ITE. Standard ITE is recovered in the zero-skewness limit of AITE, implying that the acceleration extends naturally across the broader ITE algorithmic family.
This survey traces the evolution of quantum amplitude amplification from its geometric origins in Grover’s algorithm to its algebraic formulation within the Quantum Singular Value Transformation (QSVT) framework. We develop a unified mathematical formalism intended to reduce the historical fragmentation of these algorithms. By establishing a consistent notational foundation early on, framing unstructured search as rotation within an invariant two-dimensional subspace, and following the progression through oblivious, fixed-point, and distributed amplification schemes, we aim to clarify how these methods can be interpreted within the broader language of singular-value polynomial synthesis. We additionally introduce a variational template for amplitude amplification based on parameterized phase rotations, connecting amplification primitives to hybrid quantum-classical algorithms suitable for near-term quantum architectures. To support the pedagogical objectives of this survey, we provide a companion website hosting interactive visualizations and implementation details at QuantumAmplitudeAmplification.