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:2608.02734

Improved constant factors for qubitized Hamiltonian simulation

Matthew Pocrnic, Danial Motlagh

quant-phSubmitted Aug 3, 2026• Announced Aug 5, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum signal processing (QSP) serves as the asymptotically optimal technique for Hamiltonian simulation on a quantum computer. By approximating the time evolution operator via the Jacobi-Anger expansion, the Hamiltonian simulation problem reduces to a problem in polynomial approximation theory: find a sufficient degree-$d$ polynomial series to approximate $e^{-iτx}$ on $[-1,1]$ within error $ε$. While $d\in\tilde{\mathcal{O}}(τ)$ is known to be asymptotically optimal, there exists a gap between state-of-the-art bounds and the optimal constant multiplicative factor, which is approximately equal to 1. Here, we close this gap almost entirely, to the point where possible future improvements will not be of practical significance. Our improvement resides in a careful treatment of the Bessel tail in the Jacobi-Anger series using Kapteyn's and Watson's inequalities, thereby reducing the overhead estimates for all Hamiltonian simulation tasks on quantum computers by a factor of $\approx e/2$.

Comments
8 pages, 1 figure

Related papers

Efficient phase-factor evaluation in quantum signal processing

Yulong Dong, Xiang Meng, K. Birgitta Whaley +1 more

Quantum signal processing (QSP) is a powerful quantum algorithm to exactly implement matrix polynomials on quantum computers. Asymptotic analysis of quantum algorithms based on QSP has shown that asymptotically optimal results can in principle be obtained for a range of tasks, such as Hamiltonian simulation and the quantum linear system problem. A further benefit of QSP is that it uses a minimal number of ancilla qubits, which facilitates its implementation on near-to-intermediate term quantum architectures. However, there is so far no classically stable algorithm allowing computation of the phase factors that are needed to build QSP circuits. Existing methods require the use of variable precision arithmetic and can only be applied to polynomials of a relatively low degree. We present here an optimization-based method that can accurately compute the phase factors using standard double precision arithmetic operations. We demonstrate the performance of this approach with applications to Hamiltonian simulation, eigenvalue filtering, and quantum linear system problems. Our numerical results show that the optimization algorithm can find phase factors to accurately approximate polynomials of a degree larger than $10\phantom{\rule{0.16em}{0ex}}000$ with errors below ${10}^{\ensuremath{-}12}$.

arXiv:2002.11649•Physical Review A•Apr 22, 2021•140 citations

Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing

Joshua M. Courtney

Multivariate quantum signal processing (M-QSP) has recently been shown to be applicable for non-Hermitian Hamiltonian simulation, opening several problems regarding the optimization landscape, angle-finding, and constant-factor analysis. We resolve several of these problems here. We find the anti-Hermitian query complexity $d_I = Θ(\betaI T + \log(1/\varepsilon)/\log\log(1/\varepsilon))$ to be tight, established via Chebyshev coefficient bounds, modified Bessel function asymptotics, and Lambert~$W$ inversion. Fast-forwarding to $d_I = \mathcal{O}(\sqrt{\betaI T})$ is impossible in the bivariate polynomial model, though a linear state-dependent improvement to $d_I = \mathcal{O} β_{\mathrm{eff}} T + \log(1/\varepsilon)/\log\log(1/\varepsilon))$ is achievable. The optimization landscape of M-QSP admits spurious local minima, but a warm-start basin guarantee ensures the two-stage algorithm converges. CRC-exploiting block peeling reduces angle-finding from $\mathcal{O}(d^3)$ to $\mathcal{O}(d^2)$ classical operations, and optimized error allocation yields a leading constant of approximately~$2$ relative to the information-theoretic lower bound. A constant-ratio condition extends to non-identical signal operators, enabling time-dependent non-Hermitian simulation with query complexity $\mathcal{O}(\int_0^T(\alphaR(s) + \betaI(s))\,ds + \log(1/\varepsilon)/\log\log(1/\varepsilon))$. Block-encoding overhead $e^{-2\betaI T}$ holds across all function classes within the walk-operator oracle model, and dilational methods (Schrödingerization) achieve the walk-operator barrier. A precisely characterized direct-access construction achieves the intrinsic barrier $e^{-2ωT}$ (with $ω< \betaI$ for non-commuting Hamiltonians) on a restricted domain, though extension to the full bitorus remains open.

quant-pharXiv:2605.12656•May 14, 2026•0 citations

The Hitchhiker's Guide to QSP pre-processing

Skelton, S. E.

Quantum signal processing (QSP) relies on a historically costly pre-processing step, "QSP-processing/phase-factor finding." QSP-processing is now a developed topic within quantum algorithms literature, and a beginner accessible review of QSP-processing is overdue. This work provides a whirlwind tour through QSP conventions and pre-processing methods, beginning from a pedagogically accessible QSP convention. We then review QSP conventions associated with three common polynomial types: real polynomials with definite parity, sums of reciprocal/anti-reciprocal Chebyshev polynomials, and complex polynomials. We demonstrate how the conventions perform with respect to three criteria: circuit length, polynomial conditions, and pre-processing methods. We then review the recently introduced Wilson method for QSP-processing and give conditions where it can succeed with bound error. Although the resulting bound is not computationally efficient, we demonstrate that the method succeeds with linear error propagation for relevant target polynomials and precision regimes, including the Jacobi-Anger expansion used in Hamiltonian simulation algorithms. We then apply our benchmarks to three QSP-processing methods for QSP circuits and show that a method introduced by Berntson and Sünderhauf outperforms both the Wilson method and the standard optimization strategy for complex polynomials.

arXiv:2501.05977•Jan 10, 2025•0 citations

Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing

Joshua M. Courtney

We achieve query-optimal quantum simulations of non-Hermitian Hamiltonians $H_{\mathrm{eff}} = H_R + iH_I$, where $H_R$ is Hermitian and $H_I \succeq 0$, using a bivariate extension of quantum signal processing (QSP) with non-commuting signal operators. The algorithm encodes the interaction-picture Dyson series as a polynomial on the bitorus, implemented through a structured multivariable QSP (M-QSP) circuit. A constant-ratio condition guarantees scalar angle-finding for M-QSP circuits with arbitrary non-commuting signal operators. A degree-preserving sum-of-squares spectral factorization permits scalar complementary polynomials in two variables. Angles are deterministically calculated in a classical precomputation step, running in $\mathcal{O}(d_R \cdot d_I)$ classical operations. Operator norms $α_R\,,β_I$ contribute additively with query complexity $\mathcal{O}((α_R + β_I)T + \log(1/\varepsilon)/\log\log(1/\varepsilon))$ matching an information-theoretic lower bound in the separate-oracle model, where $H_R$ and $H_I$ are accessed through independent block encodings. The postselection success probability is $e^{-2β_I T}\|e^{-iH_{\mathrm{eff}}T}|ψ_0\rangle\|^2\cdot (1 - \mathcal{O}(\varepsilon))$, decomposing into a state-dependent factor $\|e^{-iH_{\mathrm{eff}}T}|ψ_0\rangle\|^2$ from the intrinsic barrier and an $e^{-2β_I T}$ overhead from polynomial block-encoding.

quant-pharXiv:2605.12450•May 13, 2026•1 citation

Realization of quantum signal processing on a noisy quantum computer

Yuta Kikuchi, Conor Mc Keever, Luuk Coopmans +2 more

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.

arXiv:2303.05533•npj Quantum Information•Sep 23, 2023•41 citations

Efficient Fully-Coherent Hamiltonian Simulation

John M. Martyn, Yuan Liu, Zachary E. Chin +1 more

Hamiltonian simulation is a fundamental problem at the heart of quantum computation, and the associated simulation algorithms are useful building blocks for designing larger quantum algorithms. In order to be successfully concatenated into a larger quantum algorithm, a Hamiltonian simulation algorithm must succeed with arbitrarily high success probability $1-\delta$ while only requiring a single copy of the initial state, a property which we call fully-coherent. Although optimal Hamiltonian simulation has been achieved by quantum signal processing (QSP), with query complexity linear in time $t$ and logarithmic in inverse error $\ln(1/\epsilon)$, the corresponding algorithm is not fully-coherent as it only succeeds with probability close to $1/4$. While this simulation algorithm can be made fully-coherent by employing amplitude amplification at the expense of appending a $\ln(1/\delta)$ multiplicative factor to the query complexity, here we develop a new fully-coherent Hamiltonian simulation algorithm that achieves a query complexity additive in $\ln(1/\delta)$: $\Theta\big( \|\mathcal{H}\| |t| + \ln(1/\epsilon) + \ln(1/\delta)\big)$. We accomplish this by compressing the spectrum of the Hamiltonian with an affine transformation, and applying to it a QSP polynomial that approximates the complex exponential only over the range of the compressed spectrum. We further numerically analyze the complexity of this algorithm and demonstrate its application to the simulation of the Heisenberg model in constant and time-dependent external magnetic fields. We believe that this efficient fully-coherent Hamiltonian simulation algorithm can serve as a useful subroutine in quantum algorithms where maintaining coherence is paramount.

•Oct 21, 2021•1 citation
Quantum signal processing (QSP) serves as the asymptotically optimal technique for Hamiltonian simulation on a quantum computer. By approximating the time evolution operator via the Jacobi-Anger expansion, the Hamiltonian simulation problem reduces to a problem in polynomial approximation theory: find a sufficient degree-ddd polynomial series to approximate e−iτxe^{-iτx}e−iτx on [−1,1][-1,1][−1,1] within error εεε. While d∈O~(τ)d\in\tilde{\mathcal{O}}(τ)d∈O~(τ) is known to be asymptotically optimal, there exists a gap between state-of-the-art bounds and the optimal constant multiplicative factor, which is approximately equal to 1. Here, we close this gap almost entirely, to the point where possible future improvements will not be of practical significance. Our improvement resides in a careful treatment of the Bessel tail in the Jacobi-Anger series using Kapteyn's and Watson's inequalities, thereby reducing the overhead estimates for all Hamiltonian simulation tasks on quantum computers by a factor of ≈e/2\approx e/2≈e/2.
Quantum signal processing (QSP) is a powerful quantum algorithm to exactly implement matrix polynomials on quantum computers. Asymptotic analysis of quantum algorithms based on QSP has shown that asymptotically optimal results can in principle be obtained for a range of tasks, such as Hamiltonian simulation and the quantum linear system problem. A further benefit of QSP is that it uses a minimal number of ancilla qubits, which facilitates its implementation on near-to-intermediate term quantum architectures. However, there is so far no classically stable algorithm allowing computation of the phase factors that are needed to build QSP circuits. Existing methods require the use of variable precision arithmetic and can only be applied to polynomials of a relatively low degree. We present here an optimization-based method that can accurately compute the phase factors using standard double precision arithmetic operations. We demonstrate the performance of this approach with applications to Hamiltonian simulation, eigenvalue filtering, and quantum linear system problems. Our numerical results show that the optimization algorithm can find phase factors to accurately approximate polynomials of a degree larger than 1000010\phantom{\rule{0.16em}{0ex}}00010000 with errors below ${10}^{\ensuremath{-}12}$.
Multivariate quantum signal processing (M-QSP) has recently been shown to be applicable for non-Hermitian Hamiltonian simulation, opening several problems regarding the optimization landscape, angle-finding, and constant-factor analysis. We resolve several of these problems here. We find the anti-Hermitian query complexity $d_I = Θ(\betaI T + \log(1/\varepsilon)/\log\log(1/\varepsilon))$ to be tight, established via Chebyshev coefficient bounds, modified Bessel function asymptotics, and Lambert~WWW inversion. Fast-forwarding to $d_I = \mathcal{O}(\sqrt{\betaI T})$ is impossible in the bivariate polynomial model, though a linear state-dependent improvement to dI=OβeffT+log⁡(1/ε)/log⁡log⁡(1/ε))d_I = \mathcal{O} β_{\mathrm{eff}} T + \log(1/\varepsilon)/\log\log(1/\varepsilon))dI​=Oβeff​T+log(1/ε)/loglog(1/ε)) is achievable. The optimization landscape of M-QSP admits spurious local minima, but a warm-start basin guarantee ensures the two-stage algorithm converges. CRC-exploiting block peeling reduces angle-finding from O(d3)\mathcal{O}(d^3)O(d3) to O(d2)\mathcal{O}(d^2)O(d2) classical operations, and optimized error allocation yields a leading constant of approximately~222 relative to the information-theoretic lower bound. A constant-ratio condition extends to non-identical signal operators, enabling time-dependent non-Hermitian simulation with query complexity $\mathcal{O}(\int_0^T(\alphaR(s) + \betaI(s))\,ds + \log(1/\varepsilon)/\log\log(1/\varepsilon))$. Block-encoding overhead $e^{-2\betaI T}$ holds across all function classes within the walk-operator oracle model, and dilational methods (Schrödingerization) achieve the walk-operator barrier. A precisely characterized direct-access construction achieves the intrinsic barrier e−2ωTe^{-2ωT}e−2ωT (with $ω< \betaI$ for non-commuting Hamiltonians) on a restricted domain, though extension to the full bitorus remains open.
Quantum signal processing (QSP) relies on a historically costly pre-processing step, "QSP-processing/phase-factor finding." QSP-processing is now a developed topic within quantum algorithms literature, and a beginner accessible review of QSP-processing is overdue. This work provides a whirlwind tour through QSP conventions and pre-processing methods, beginning from a pedagogically accessible QSP convention. We then review QSP conventions associated with three common polynomial types: real polynomials with definite parity, sums of reciprocal/anti-reciprocal Chebyshev polynomials, and complex polynomials. We demonstrate how the conventions perform with respect to three criteria: circuit length, polynomial conditions, and pre-processing methods. We then review the recently introduced Wilson method for QSP-processing and give conditions where it can succeed with bound error. Although the resulting bound is not computationally efficient, we demonstrate that the method succeeds with linear error propagation for relevant target polynomials and precision regimes, including the Jacobi-Anger expansion used in Hamiltonian simulation algorithms. We then apply our benchmarks to three QSP-processing methods for QSP circuits and show that a method introduced by Berntson and Sünderhauf outperforms both the Wilson method and the standard optimization strategy for complex polynomials.
We achieve query-optimal quantum simulations of non-Hermitian Hamiltonians Heff=HR+iHIH_{\mathrm{eff}} = H_R + iH_IHeff​=HR​+iHI​, where HRH_RHR​ is Hermitian and HI⪰0H_I \succeq 0HI​⪰0, using a bivariate extension of quantum signal processing (QSP) with non-commuting signal operators. The algorithm encodes the interaction-picture Dyson series as a polynomial on the bitorus, implemented through a structured multivariable QSP (M-QSP) circuit. A constant-ratio condition guarantees scalar angle-finding for M-QSP circuits with arbitrary non-commuting signal operators. A degree-preserving sum-of-squares spectral factorization permits scalar complementary polynomials in two variables. Angles are deterministically calculated in a classical precomputation step, running in O(dR⋅dI)\mathcal{O}(d_R \cdot d_I)O(dR​⋅dI​) classical operations. Operator norms αR ,βIα_R\,,β_IαR​,βI​ contribute additively with query complexity O((αR+βI)T+log⁡(1/ε)/log⁡log⁡(1/ε))\mathcal{O}((α_R + β_I)T + \log(1/\varepsilon)/\log\log(1/\varepsilon))O((αR​+βI​)T+log(1/ε)/loglog(1/ε)) matching an information-theoretic lower bound in the separate-oracle model, where HRH_RHR​ and HIH_IHI​ are accessed through independent block encodings. The postselection success probability is e−2βIT∥e−iHeffT∣ψ0⟩∥2⋅(1−O(ε))e^{-2β_I T}\|e^{-iH_{\mathrm{eff}}T}|ψ_0\rangle\|^2\cdot (1 - \mathcal{O}(\varepsilon))e−2βI​T∥e−iHeff​T∣ψ0​⟩∥2⋅(1−O(ε)), decomposing into a state-dependent factor ∥e−iHeffT∣ψ0⟩∥2\|e^{-iH_{\mathrm{eff}}T}|ψ_0\rangle\|^2∥e−iHeff​T∣ψ0​⟩∥2 from the intrinsic barrier and an e−2βITe^{-2β_I T}e−2βI​T overhead from polynomial block-encoding.
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.
Hamiltonian simulation is a fundamental problem at the heart of quantum computation, and the associated simulation algorithms are useful building blocks for designing larger quantum algorithms. In order to be successfully concatenated into a larger quantum algorithm, a Hamiltonian simulation algorithm must succeed with arbitrarily high success probability 1−δ1-\delta1−δ while only requiring a single copy of the initial state, a property which we call fully-coherent. Although optimal Hamiltonian simulation has been achieved by quantum signal processing (QSP), with query complexity linear in time ttt and logarithmic in inverse error ln⁡(1/ϵ)\ln(1/\epsilon)ln(1/ϵ), the corresponding algorithm is not fully-coherent as it only succeeds with probability close to 1/41/41/4. While this simulation algorithm can be made fully-coherent by employing amplitude amplification at the expense of appending a ln⁡(1/δ)\ln(1/\delta)ln(1/δ) multiplicative factor to the query complexity, here we develop a new fully-coherent Hamiltonian simulation algorithm that achieves a query complexity additive in ln⁡(1/δ)\ln(1/\delta)ln(1/δ): Θ(∥H∥∣t∣+ln⁡(1/ϵ)+ln⁡(1/δ))\Theta\big( \|\mathcal{H}\| |t| + \ln(1/\epsilon) + \ln(1/\delta)\big)Θ(∥H∥∣t∣+ln(1/ϵ)+ln(1/δ)). We accomplish this by compressing the spectrum of the Hamiltonian with an affine transformation, and applying to it a QSP polynomial that approximates the complex exponential only over the range of the compressed spectrum. We further numerically analyze the complexity of this algorithm and demonstrate its application to the simulation of the Heisenberg model in constant and time-dependent external magnetic fields. We believe that this efficient fully-coherent Hamiltonian simulation algorithm can serve as a useful subroutine in quantum algorithms where maintaining coherence is paramount.