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

Efficient Fully-Coherent Hamiltonian Simulation

John M. Martyn, Yuan Liu, Zachary E. Chin, Isaac L. Chuang

Published Oct 21, 2021• 1 citation
OpenAlex

Abstract

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.

Related papers

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

Efficient fully-coherent quantum signal processing algorithms for real-time dynamics simulation

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

Simulating the unitary dynamics of a quantum system is a fundamental problem of quantum mechanics, in which quantum computers are believed to have significant advantage over their classical counterparts. One prominent such instance is the simulation of electronic dynamics, which plays an essential role in chemical reactions, non-equilibrium dynamics, and material design. These systems are time-dependent, which requires that the corresponding simulation algorithm can be successfully concatenated with itself over different time intervals to reproduce the overall coherent quantum dynamics of the system. In this paper, we quantify such simulation algorithms by the property of being fully-coherent: the algorithm succeeds with arbitrarily high success probability 1 − δ while only requiring a single copy of the initial state. We subsequently develop fully-coherent simulation algorithms based on quantum signal processing (QSP), including a novel algorithm that circumvents the use of amplitude amplification while also achieving a query complexity additive in time t, ln(1/δ), and ln(1/ϵ) for error tolerance ϵ: Θ‖H‖|t|+ln(1/ϵ)+ln(1/δ). Furthermore, we numerically analyze these algorithms by applying them to the simulation of the spin dynamics of the Heisenberg model and the correlated electronic dynamics of an H2 molecule. Since any electronic Hamiltonian can be mapped to a spin Hamiltonian, our algorithm can efficiently simulate time-dependent ab initio electronic dynamics in the circuit model of quantum computation. Accordingly, it is also our hope that the present work serves as a bridge between QSP-based quantum algorithms and chemical dynamics, stimulating a cross-fertilization between these exciting fields.

arXiv:2110.11327•The Journal of Chemical Physics•Jan 10, 2023•54 citations

Improved constant factors for qubitized Hamiltonian simulation

Matthew Pocrnic, Danial Motlagh

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$.

quant-pharXiv:2608.02734•Aug 5, 2026•0 citations

Quantum simulation of slow analytic time-dependent Hamiltonians

Chenhao Zhao, Yinan Li, Dong An

We develop a quantum algorithm for slow analytic Hamiltonians $\widetilde H(t)=H(t/T)$ with $\|H(s)\|\leqα$ that achieves nearly additive query complexity and low gate overhead. Our main technical contribution is a periodic Gevrey extension of $H(s)$, together with Fourier component decay and truncation bounds that enable an efficient finite-dimensional simulation. Combined with Floquet embedding and optimal time-independent Hamiltonian simulation technique, this gives query complexity $\widetilde{\mathcal O}\!\left(αT+\log(1/\varepsilon)\right)$ and additional gate complexity $\widetilde{\mathcal O}\!\left((αT+\log(1/\varepsilon))^2\log(1/\varepsilon)\right)$, assuming coherent access to $H'(s)$ and endpoint derivatives. For slow analytic control Hamiltonians, only block encodings of the time-independent control operators are required, with the same query complexity and lower gate overhead. Our method also extends to Gevrey Hamiltonians and improves the precision dependence for simulating slow analytic semi-dissipative linear differential equations.

quant-pharXiv:2608.17653•Aug 19, 2026•0 citations

Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation

Boyang Chen, Minbo Gao, Zhengfeng Ji +3 more

The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right) $$ queries to $\mathrm{HAM\mbox{-}T}$ within $\varepsilon$ error for a Lipschitz-continuous time-dependent Hamiltonian $H(t)$ on $[0,T]$ satisfying $\left\lVert H(t)\right\rVert\leqα$. However, its direct circuit implementation incurs a substantially larger gate overhead. In this note, we give an implementation of the same algorithm that retains its optimal query complexity and uses $$ O\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right] $$ one- and two-qubit gates, where $a$ is the number of block-encoding ancilla qubits and $β$ is the Lipschitz constant of $H$. The main ingredient is an exact dyadic factorization of the ordered update product in the underlying one-query transducer.

quant-pharXiv:2608.30629•Sep 1, 2026•0 citations

Query-optimal quantum simulation of Lindblad evolution

Chunhao Wang, Christopher Ye

For the problem of simulating Lindblad evolution for time $t$ to precision $ε$, Hamiltonian simulation provides an additive query lower bound, informally, $Ω(t + \mathrm{polylog}(1/ε))$. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(1/ε))$, in query complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. We further achieve nearly optimal gate complexity in evolution time and precision through history compression and an efficient implementation of the query-free part of the transducer using operation reordering and linear combinations of unitaries, while preserving the optimal query complexity.

quant-pharXiv:2609.17490•Sep 16, 2026•0 citations
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.
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.
Simulating the unitary dynamics of a quantum system is a fundamental problem of quantum mechanics, in which quantum computers are believed to have significant advantage over their classical counterparts. One prominent such instance is the simulation of electronic dynamics, which plays an essential role in chemical reactions, non-equilibrium dynamics, and material design. These systems are time-dependent, which requires that the corresponding simulation algorithm can be successfully concatenated with itself over different time intervals to reproduce the overall coherent quantum dynamics of the system. In this paper, we quantify such simulation algorithms by the property of being fully-coherent: the algorithm succeeds with arbitrarily high success probability 1 − δ while only requiring a single copy of the initial state. We subsequently develop fully-coherent simulation algorithms based on quantum signal processing (QSP), including a novel algorithm that circumvents the use of amplitude amplification while also achieving a query complexity additive in time t, ln(1/δ), and ln(1/ϵ) for error tolerance ϵ: Θ‖H‖|t|+ln(1/ϵ)+ln(1/δ). Furthermore, we numerically analyze these algorithms by applying them to the simulation of the spin dynamics of the Heisenberg model and the correlated electronic dynamics of an H2 molecule. Since any electronic Hamiltonian can be mapped to a spin Hamiltonian, our algorithm can efficiently simulate time-dependent ab initio electronic dynamics in the circuit model of quantum computation. Accordingly, it is also our hope that the present work serves as a bridge between QSP-based quantum algorithms and chemical dynamics, stimulating a cross-fertilization between these exciting fields.
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.
We develop a quantum algorithm for slow analytic Hamiltonians H~(t)=H(t/T)\widetilde H(t)=H(t/T)H(t)=H(t/T) with ∥H(s)∥≤α\|H(s)\|\leqα∥H(s)∥≤α that achieves nearly additive query complexity and low gate overhead. Our main technical contribution is a periodic Gevrey extension of H(s)H(s)H(s), together with Fourier component decay and truncation bounds that enable an efficient finite-dimensional simulation. Combined with Floquet embedding and optimal time-independent Hamiltonian simulation technique, this gives query complexity O~ ⁣(αT+log⁡(1/ε))\widetilde{\mathcal O}\!\left(αT+\log(1/\varepsilon)\right)O(αT+log(1/ε)) and additional gate complexity O~ ⁣((αT+log⁡(1/ε))2log⁡(1/ε))\widetilde{\mathcal O}\!\left((αT+\log(1/\varepsilon))^2\log(1/\varepsilon)\right)O((αT+log(1/ε))2log(1/ε)), assuming coherent access to H′(s)H'(s)H′(s) and endpoint derivatives. For slow analytic control Hamiltonians, only block encodings of the time-independent control operators are required, with the same query complexity and lower gate overhead. Our method also extends to Gevrey Hamiltonians and improves the precision dependence for simulating slow analytic semi-dissipative linear differential equations.
The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses q=O(αT+log⁡(1/ε)log⁡(e+log⁡(1/ε)/(αT))) q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right) q=O(αT+log(e+log(1/ε)/(αT))log(1/ε)​) queries to $\mathrm{HAM\mbox{-}T}$ within ε\varepsilonε error for a Lipschitz-continuous time-dependent Hamiltonian H(t)H(t)H(t) on [0,T][0,T][0,T] satisfying ∥H(t)∥≤α\left\lVert H(t)\right\rVert\leqα∥H(t)∥≤α. However, its direct circuit implementation incurs a substantially larger gate overhead. In this note, we give an implementation of the same algorithm that retains its optimal query complexity and uses O[q(a+log⁡(1+T(α+βT)ε))] O\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right] O[q(a+log(1+εT(α+βT)​))] one- and two-qubit gates, where aaa is the number of block-encoding ancilla qubits and βββ is the Lipschitz constant of HHH. The main ingredient is an exact dyadic factorization of the ordered update product in the underlying one-query transducer.
For the problem of simulating Lindblad evolution for time ttt to precision εεε, Hamiltonian simulation provides an additive query lower bound, informally, Ω(t+polylog(1/ε))Ω(t + \mathrm{polylog}(1/ε))Ω(t+polylog(1/ε)). However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, O(t polylog(1/ε))\mathcal{O}(t\,\mathrm{polylog}(1/ε))O(tpolylog(1/ε)), in query complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. We further achieve nearly optimal gate complexity in evolution time and precision through history compression and an efficient implementation of the query-free part of the transducer using operation reordering and linear combinations of unitaries, while preserving the optimal query complexity.