Yudai Suzuki

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 viewpoint uncovers three key insights. First, we show that the ITE dynamics trace the shortest path between the initial and the solution states in complex projective space. Second, we prove that the geodesic length of ITE determines the query complexity of Grover’s algorithm. This complexity notably aligns with the known optimal scaling for unstructured search. Lastly, utilizing the geodesic structure of ITE, we construct a quantum signal processing formulation for ITE without post-selection, and derive a new set of angles for the fixed-point search. These results collectively establish a deeper understanding of Grover's algorithm and suggest a potential role for thermodynamics and geometry in quantum algorithm design.

Quantum Signal Processing (QSP), a framework for implementing matrix-valued polynomials, is a fundamental primitive in various quantum algorithms. Despite its versatility, a potentially underappreciated challenge is that all systematic protocols for implementing QSP rely on post-selection. This can impose prohibitive costs for tasks when amplitude amplification cannot sufficiently improve the success probability. For example, in the context of ground-state preparation, this occurs when using a too poor initial state. In this work, we introduce a new formula for implementing QSP transformations of Hermitian matrices, which requires neither auxiliary qubits nor post-selection. Rather, using approximation to the exact unitary synthesis, we leverage the theory of the double-bracket quantum algorithms to provide a new quantum algorithm for QSP, termed Double-Bracket QSP (DB-QSP). The algorithm requires the energy and energetic variance of the state to be measured at each step and has a recursive structure, which leads to circuit depths that can grow super exponentially with the degree of the polynomial. With these strengths and caveats in mind, DB-QSP should be viewed as complementing the established QSP toolkit. In particular, DB-QSP can deterministically implement low-degree polynomials to "warm start" QSP methods involving post-selection.

In the quest for quantum advantage, a central question is under what conditions can classical algorithms achieve a performance comparable to quantum algorithms--a concept known as dequantization. Random Fourier features (RFFs) have demonstrated potential for dequantizing certain quantum neural networks (QNNs) applied to regression tasks, but their applicability to other learning problems and architectures remains unexplored. In this work, we derive bounds on the true risk gap between classical RFF models and quantum models for regression and classification tasks with both QNN and quantum kernel architectures. Furthermore, we provide sufficient conditions under which this gap is small and thus the quantum system can be dequantized via the RFF method. We support our findings with numerical experiments that illustrate the practical dequantization of existing quantum kernel-based methods. Our findings not only broaden the applicability of RFF-dequantization but also enhance the understanding of potential quantum advantages in practical machine-learning tasks.