Quantum signal processing provides an optimal procedure for simulating Hamiltonian evolution on a quantum computer using calls to a block encoding of the Hamiltonian. In many situations it is possible to control between forward and reverse steps with almost identical cost to a simple controlled operation. We show that it is then possible to reduce the cost of Hamiltonian simulation by a factor of 2 using the recent results of generalized quantum signal processing.
Quantum signal processing provides an optimal procedure for simulating Hamiltonian evolution on a quantum computer using calls to a block encoding of the Hamiltonian. In many situations it is possible to control between forward and reverse steps with almost identical cost to a simple controlled operation. We show that it is then possible to reduce the cost of Hamiltonian simulation by a factor of 2 using the recent results of generalized quantum signal processing.
Quantum signal processing (QSP) and quantum singular value transformation (QSVT) currently stand as the most efficient techniques for implementing functions of block-encoded matrices, a central task that lies at the heart of most prominent quantum algorithms. However, current QSP approaches face several challenges, such as the restrictions imposed on the family of achievable polynomials and the difficulty of calculating the required phase angles for specific transformations. In this paper, we present a generalized quantum signal processing (GQSP) approach, employing general SU(2) rotations as our signal-processing operators, rather than relying solely on rotations in a single basis. Our approach lifts all practical restrictions on the family of achievable transformations, with the sole remaining condition being that |P|≤1 , a restriction necessary due to the unitary nature of quantum computation. Furthermore, GQSP provides a straightforward recursive formula for determining the rotation angles needed to construct the polynomials in cases where P and Q are known. In cases where only P is known, we provide an efficient optimization algorithm capable of identifying in under a minute of GPU time, a corresponding Q for polynomials of degree on the order of 107 . We further illustrate GQSP simplifies QSP-based strategies for Hamiltonian simulation, offer an optimal solution to the ϵ -approximate fractional query problem that requires O((1/δ)+log(1/ϵ)) queries to perform where O(1/δ) is a proved lower bound, and introduces novel approaches for implementing bosonic operators. Moreover, we propose a novel framework for the implementation of normal matrices, demonstrating its applicability through synthesis of diagonal matrices, as well as the development of a new algorithm for convolution through synthesis of circulant matrices using only O(dlogN+log2N) 1 and 2-qubit gates for a filter of lengths d . Published by the American Physical Society 2024
Abstract Quantum signal processing (QSP) is a powerful toolbox for the design of quantum algorithms and can lead to asymptotically optimal computational costs. Its realization on noisy quantum computers without fault tolerance, however, is challenging because it requires a deep quantum circuit in general. We propose a strategy to run an entire QSP protocol on noisy quantum hardware by carefully reducing overhead costs at each step. To illustrate the approach, we consider the application of Hamiltonian simulation for which QSP implements a polynomial approximation of the time evolution operator. We test the protocol by running the algorithm on the Quantinuum H1-1 trapped-ion quantum computer powered by Honeywell. In particular, we compute the time dependence of bipartite entanglement entropies for Ising spin chains and find good agreements with exact numerical simulations. To make the best use of the device, we determine optimal experimental parameters by using a simplified error model for the hardware and numerically studying the trade-off between Hamiltonian simulation time, polynomial degree, and total accuracy. Our results are the first step in the experimental realization of QSP-based quantum algorithms.
The physics of quantum mechanics is the inspiration for, and underlies, quantum computation. As such, one expects physical intuition to be highly influential in the understanding and design of many quantum algorithms, particularly simulation of physical systems. Surprisingly, this has been challenging, with current Hamiltonian simulation algorithms remaining abstract and often the result of sophisticated but unintuitive constructions. We contend that physical intuition can lead to optimal simulation methods by showing that a focus on simple single-qubit rotations elegantly furnishes an optimal algorithm for Hamiltonian simulation, a universal problem that encapsulates all the power of quantum computation. Specifically, we show that the query complexity of implementing time evolution by a d-sparse Hamiltonian H[over ^] for time-interval t with error ε is O[td∥H[over ^]∥_{max}+log(1/ε)/loglog(1/ε)], which matches lower bounds in all parameters. This connection is made through general three-step "quantum signal processing" methodology, comprised of (i) transducing eigenvalues of H[over ^] into a single ancilla qubit, (ii) transforming these eigenvalues through an optimal-length sequence of single-qubit rotations, and (iii) projecting this ancilla with near unity success probability.
Perturbation theory is an important technique for reducing computational cost and providing physical insights in simulating quantum systems with classical computers. Here, we provide a quantum algorithm to obtain perturbative energies on quantum computers. The benefit of using quantum computers is that we can start the perturbation from a Hamiltonian that is classically hard to solve. The proposed algorithm uses quantum signal processing (QSP) to achieve this goal. Along with the perturbation theory, we construct a technique for ground state preparation with detailed computational cost analysis, which can be of independent interest. We also estimate a rough computational cost of the algorithm for simple chemical systems such as water clusters and polyacene molecules. To the best of our knowledge, this is the first of such estimates for practical applications of QSP. Unfortunately, we find that the proposed algorithm, at least in its current form, does not exhibit practical numbers despite of the efficiency of QSP compared to conventional quantum algorithms. However, perturbation theory itself is an attractive direction to explore because of its physical interpretability; it provides us insights about what interaction gives an important contribution to the properties of systems. This is in sharp contrast to the conventional approaches based on the quantum phase estimation algorithm, where we can only obtain values of energy. From this aspect, this work is a first step towards “explainable'' quantum simulation on fault-tolerant quantum computers.
We describe a simple quantum algorithm to simulate time-dependent Hamiltonian, extending the methodology of quantum signal processing. The framework achieves optimal scaling up to some factor with respect to other parameters, and nearly optimal in inverse of error tolerance, which could be improved to optimal scaling under certain input models. As applications, we discuss the problem of simulating generalized lattice system and time-periodic, or Floquet system, showing that our framework provides a neater yet highly efficient solution, achieving optimal/nearly optimal scaling in all parameters. In particular, our method also paves a new way for studying phase transition on quantum computer, extending the reach of quantum simulation.
Quantum signal processing (QSP) is a template for designing algorithms in the quantum circuit model. We consider three facets of this template. First, how to compute the exact circuit for a given algorithm and problem parameters. QSP requires two interrelated pre-processing steps. We give an algorithm for the first step, and compare its performance to recent alternatives. We find that our algorithm, using the Wilson method, is competitive for sparse polynomials away from the near-coherent regime. Next, we give an algorithm for quantum phase or energy estimation (QPE and QEE), designed with QSP. QEE replaces the common oracle access model in QPE with a block-encoding. We use von Neumann's measurement protocol and Hamiltonian simulation with QSP to show that QEE can be solved efficiently. We then show that when the standard QPE oracle is block-encoded, QPE algorithm with logarithmic overhead. We also show that whenever the system of interest is described by a linear combination of Pauli terms, the gate complexity of the entire algorithm is efficient in Clifford and T gates. We then consider how QSP relates to time-evolution. We show that QSP circuits can be understood as the circuits generated by a piecewise continuous time-evolution. Specifically, this evolution fits the bilinear control model, a common model in quantum control theory. Finally, we engineer a continuous time-dependent system for which the quantum adiabatic theorem will hold, which syntactically resembles QSP. We show that in the high-degree and small-signal limit, when the adiabatic schedule is Lipschitz continuous, the quantum adiabatic evolution of an eigenstate of H(0) is close to a QSP circuit applied to the same eigenstate. Crucially, our formalism establishes a direct functional relationship between the adiabatic schedule and the set of phase factors that determine the QSP circuit.