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

Complexity Bounds for Hamiltonian Simulation in Unitary Representations

Naihuan Jing, Molena Nguyen

quant-phmath-phSubmitted Mar 7, 2026• Announced Mar 10, 2026• 0 citations
arXivHTMLPDF

Abstract

For any unitary representation $ρ$ on a finite-dimensional Hilbert space \(V\) with differential \(dρ: \mathfrak{g} \to \mathfrak{u}(V)\) for the Lie algebra $\mathfrak g$, we consider the Hamiltonian evolution \[ U_X(t) \coloneqq ρ(\exp(tX)) = e^{t\,dρ(X)}, \qquad t\in\mathbb{R}. \] For any complexification $ X_\mathbb{C} = X_0 + \sum\limits_{α\inΔ} x_αE_α$ associated with the root system $Δ$, we introduce the numerical invariants %\emph{root activity} and \emph{root curvature} functionals \begin{align*} \mathcal{A}_p(X) &\coloneqq \Bigl(\sum_{α\inΔ} |x_α|^p \,\|dρ(E_α)\|_{\mathrm{op}}^p\Bigr)^{1/p}, \quad 1\le p<\infty\\ \mathcal{C}(X) &\coloneqq \Bigl(\sum_{α\inΔ} |α(X_0)|^2\,|x_α|^2 \,\|dρ(E_α)\|_{\mathrm{op}}^2\Bigr)^{1/2}, \end{align*} where \(\|\cdot\|_{\mathrm{op}}\) is the operator norm on \(\mathrm{End}(V)\). We first describe how the Hamiltonian \(dρ(X)\) is distributed along the directions of root spaces $\mathfrak{g}_α$. Our main result shows that for each fixed \(X\in\mathfrak{g}\) there exists a constant \(C_X>0\) such that \[ \bigl\| e^{t(dρ(X_0)+dρ(X_{\mathrm{root}}))} - e^{\frac{t}{2}dρ(X_0)} e^{t dρ(X_{\mathrm{root}})} e^{\frac{t}{2}dρ(X_0)} \bigr\|_{\mathrm{op}} \le C_X\,t^{3}\,\bigl(\mathcal{C}(X)+\mathcal{A}_1(X_{\mathrm{root}})\bigr) \] for all sufficiently small \(|t|\). We also introduce a root-gate circuit model and test this on spin$-$chain Hamiltonians on \((\mathbb{C}^2)^{\otimes n}\subset\mathfrak{su}(2^n)\), where root spaces are spanned by matrix units, \(\mathcal{A}_p\), and \(\mathcal{C}\), which gives sharper complexity bounds and dimension$-$free representation$-$theoretic invariants.

Comments
34pp

Related papers

Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers

Dominic W. Berry, Abhishek Rawat, Sophia Simon +1 more

We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an $s$-sparse Hermitian matrix with row and column Euclidean norms bounded by $η$, evolution for time $t$ to error $ε$ uses $\mathcal{O}(\sqrt{s}τ+\sqrt{sτ\log(1/ε)}+\log(1/ε))$ queries, where $τ=η|t|$. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in $\sqrt{s}τ$ and $\log(1/ε)$. For dissipative linear differential equations we obtain $\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))$ queries, where $τ$ is the evolution time multiplied by a norm bound, $\bar g$ bounds the ratio of combined input and source norms to the final-solution norm, and $C$ is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give $\mathcal{O}(κ\sqrt{s}\log(1/ε))$ queries when $\|A\|\le1$ and $\|A^{-1}\|\leκ$, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.

quant-pharXiv:2610.02939•Oct 5, 2026•1 citation

Statistics and complexity of wavefunction spreading in quantum dynamical systems

Y. W. Fu, Keun-young Kim A, Kunal Pal +1 more

A bstract We consider the statistics of the results of a measurement of the spreading operator in the Krylov basis generated by the Hamiltonian of a quantum system starting from a specified initial pure state. We first obtain the probability distribution of the results of measurements of this spreading operator at a certain instant of time, and compute the characteristic function of this distribution. We show that the moments of this characteristic function are related to the so-called generalised spread complexities, and obtain expressions for them in several cases when the Hamiltonian is an element of a Lie algebra. Furthermore, by considering a continuum limit of the Krylov basis, we show that the generalised spread complexities of higher orders have a peak in the time evolution for a random matrix Hamiltonian belonging to the Gaussian unitary ensemble. We also obtain an upper bound in the change in generalised spread complexity at an arbitrary time in terms of the operator norm of the Hamiltonian and discuss the significance of these results.

arXiv:2411.09390•Journal of High Energy Physics•Jun 13, 2025•14 citations

Towards verifications of Krylov complexity

Ryu Sasaki B

Abstract Krylov complexity is considered to provide a measure of the growth of operators evolving under Hamiltonian dynamics. The main strategy is the analysis of the structure of Krylov subspace $\mathcal {K}_M(\mathcal {H},\eta )$ spanned by the multiple applications of the Liouville operator $\mathcal {L}$ defined by the commutator in terms of a Hamiltonian $\mathcal {H}$, $\mathcal {L}:=[\mathcal {H},\cdot ]$ acting on an operator η, $\mathcal {K}_M(\mathcal {H},\eta )=\text{span}\lbrace \eta ,\mathcal {L}\eta ,\ldots ,\mathcal {L}^{M-1}\eta \rbrace$. For a given inner product ( ·, ·) of the operators, the orthonormal basis $\lbrace \mathcal {O}_n\rbrace$ is constructed from $\mathcal {O}_0=\eta /\sqrt{(\eta ,\eta )}$ by Lanczos algorithm. The moments $\mu _m=(\mathcal {O}_0,\mathcal {L}^m\mathcal {O}_0)$ are closely related to the important data {bn} called Lanczos coefficients. I present the exact and explicit expressions of the moments {μm} for 16 quantum mechanical systems which are exactly solvable both in the Schrödinger and Heisenberg pictures. The operator η is the variable of the eigenpolynomials. Among them six systems show a clear sign of ‘non-complexity’ as vanishing higher Lanczos coefficients bm = 0, m ≥ 3.

arXiv:2403.06391•Progress of Theoretical and Experimental Physics•May 11, 2024•9 citations

Some Numerical Methods And Analysis of A Class of Quantum Stochastic Differential Equations

Samuel Oluwaseyi Ogundipe

The classical stochastic differential equation given as \[dX(t, \omega) = a(t, X) \, dt + b(t, X) \, dQ(t), \quad X(t_0) = X_0, \quad t \in [t_0, T],\] where the driving process \( Q(t) \) is a martingale, and \( a \) and \( b \) are adapted functionals has several numerical schemes developed for it, where each exhibits distinct stability and convergence properties depending on the nature of the driving process and the functional space of the solution. A generalization of this equation is the quantum stochastic differential equation introduced by Hudson and Parthasarathy, expressed as \[dX(t) = E(t, X(t)) \, d\Lambda_\pi(t) + F(t, X(t)) \, dA_f^\dagger(t) + G(t, X(t)) \, dA_g(t) + H(t, X(t)) \, dt,\] where \( E, F, G, \) and \( H \) are stochastic operator-valued functions defined on a Hilbert space. In 1992, Ekhaquere reformulated this equation in an equivalent form involving the non-classical differential equation stated as; \[\frac{d}{dt} \langle \eta, X(t) \xi \rangle = P(t, X(t)) \langle \eta, \xi \rangle, \quad X(t_0) = X_0, \quad t \in [t_0, T],\] which represents an ordinary differential equation of non-classical type. The stochastic process \( X(t) \) acts as a densely defined linear operator on a tensor product of two Hilbert spaces, one of which is the Boson Fock space. The vectors \( \eta \) and \( \xi \) belong to a dense subset of this tensor product Hilbert space, and the mapping \[(\eta, \xi) \mapsto P(t, X)(\eta, \xi)\] defines a sesquilinear form for each fixed pair \((t, X)\). We analyze the numerical approximation of the QSDE using its equivalent inner-product form. The numerical investigation employs three principal methods: the Lagrangian Quadrature Method, the Linear Multistep Scheme, and the Newton–Cotes Method. Each method is carefully designed to ensure the consistency, stability, and convergence of the approximate solution \(X(t)\) toward the exact stochastic process. These schemes are implemented using Python programming language, which provides a flexible and efficient computational environment for testing the proposed algorithms. Our computational results show that the developed schemes generalize Taylor-type approximations of Itô processes under weak convergence criteria. The proposed algorithms exhibit numerical stability and yield results that compare favorably with analytical benchmarks. Furthermore, the implementation avoids direct approximation of the driving quantum processes, thereby preserving the natural adaptation of the schemes to quantum dynamical models.

•Jan 9, 2026•0 citations

Bounds to unitary evolution

Mark Andrews

Upper and lower bounds are established for the survival probability $\ensuremath{\mid}⟨\ensuremath{\psi}(0)\ensuremath{\mid}\ensuremath{\psi}(t)⟩{\ensuremath{\mid}}^{2}$ of a quantum state, in terms of the energy moments $⟨\ensuremath{\psi}(0)\ensuremath{\mid}{H}^{n}\ensuremath{\mid}\ensuremath{\psi}(0)⟩$. Introducing a cutoff in the energy generally enables considerable improvement in these bounds and allows the method to be used where the exact energy moments do not exist.

arXiv:0705.1823•Physical Review A•Jun 21, 2007•15 citations

A Hamiltonian-Level Certificate for Network-Free Distributed Quantum Simulation: Exact Tensor-Separability Criterion and Approximate Residual Bounds

Kan He, Shusen Liu, Jinchuan Hou +4 more

Circuit cutting allows quantum circuits to be evaluated on smaller devices at the cost of additional sampling and classical reconstruction. For Hamiltonian-simulation circuits, the target unitary $\exp[it\mathbf H]$ connects this decomposition problem to the structure of the generator. We develop a Hamiltonian-level certificate that assesses exact separability and the accuracy of independent module evolution before a gate decomposition is chosen. For a time-independent Hamiltonian and a fixed module partition, the Hilbert--Schmidt projection onto sums of module-local terms isolates a cross-module residual $H_{ns}$. Its vanishing is necessary and sufficient for product evolution at all times; for Pauli-list inputs, this condition is checked in one pass over the combined coefficients. When $H_{ns}\ne0$, the projected evolution has operator-norm error at most $|t| ||H_{ns}||_{op}$. Across a bipartition, an explicit first-order algebraic correction has the same operator-Schmidt rank as $H_{ns}$ and leaves a second-order residual. The same Hamiltonian residual connects this approximation to short-time entanglement, determining the leading state-space and operator-space entangling powers and, through its Schmidt spectrum, the leading Choi tripartite-information terms. Numerical experiments test these relations and demonstrate block-factorised simulation up to $20$ qubits.

arXiv:1901.04629•Jan 15, 2019•0 citations
For any unitary representation ρρρ on a finite-dimensional Hilbert space (V) with differential (dρ: \mathfrak{g} \to \mathfrak{u}(V)) for the Lie algebra g\mathfrak gg, we consider the Hamiltonian evolution [ U_X(t) \coloneqq ρ(\exp(tX)) = e^{t,dρ(X)}, \qquad t\in\mathbb{R}. ] For any complexification XC=X0+∑α∈ΔxαEα X_\mathbb{C} = X_0 + \sum\limits_{α\inΔ} x_αE_αXC​=X0​+α∈Δ∑​xα​Eα​ associated with the root system ΔΔΔ, we introduce the numerical invariants %\emph{root activity} and \emph{root curvature} functionals \begin{align*} \mathcal{A}p(X) &\coloneqq \Bigl(\sum{α\inΔ} |x_α|^p ,|dρ(E_α)|{\mathrm{op}}^p\Bigr)^{1/p}, \quad 1\le p<\infty\ \mathcal{C}(X) &\coloneqq \Bigl(\sum{α\inΔ} |α(X_0)|^2,|x_α|^2 ,|dρ(E_α)|{\mathrm{op}}^2\Bigr)^{1/2}, \end{align*} where (|\cdot|{\mathrm{op}}) is the operator norm on (\mathrm{End}(V)). We first describe how the Hamiltonian (dρ(X)) is distributed along the directions of root spaces gα\mathfrak{g}_αgα​.
Our main result shows that for each fixed (X\in\mathfrak{g}) there exists a constant (C_X>0) such that [ \bigl| e^{t(dρ(X_0)+dρ(X_{\mathrm{root}}))} - e^{\frac{t}{2}dρ(X_0)} e^{t dρ(X_{\mathrm{root}})} e^{\frac{t}{2}dρ(X_0)} \bigr|_{\mathrm{op}} \le C_X,t^{3},\bigl(\mathcal{C}(X)+\mathcal{A}1(X{\mathrm{root}})\bigr) ] for all sufficiently small (|t|). We also introduce a root-gate circuit model and test this on spin−-−chain Hamiltonians on ((\mathbb{C}^2)^{\otimes n}\subset\mathfrak{su}(2^n)), where root spaces are spanned by matrix units, (\mathcal{A}_p), and (\mathcal{C}), which gives sharper complexity bounds and dimension−-−free representation−-−theoretic invariants.
We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an sss-sparse Hermitian matrix with row and column Euclidean norms bounded by ηηη, evolution for time ttt to error εεε uses O(sτ+sτlog⁡(1/ε)+log⁡(1/ε))\mathcal{O}(\sqrt{s}τ+\sqrt{sτ\log(1/ε)}+\log(1/ε))O(s​τ+sτlog(1/ε)​+log(1/ε)) queries, where τ=η∣t∣τ=η|t|τ=η∣t∣. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in sτ\sqrt{s}τs​τ and log⁡(1/ε)\log(1/ε)log(1/ε). For dissipative linear differential equations we obtain O(gˉ[s(τ+τ)+1]log⁡(Cgˉ/ε))\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))O(gˉ​[s​(τ+τ​)+1]log(Cgˉ​/ε)) queries, where τττ is the evolution time multiplied by a norm bound, gˉ\bar ggˉ​ bounds the ratio of combined input and source norms to the final-solution norm, and CCC is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give O(κslog⁡(1/ε))\mathcal{O}(κ\sqrt{s}\log(1/ε))O(κs​log(1/ε)) queries when ∥A∥≤1\|A\|\le1∥A∥≤1 and ∥A−1∥≤κ\|A^{-1}\|\leκ∥A−1∥≤κ, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.
A bstract We consider the statistics of the results of a measurement of the spreading operator in the Krylov basis generated by the Hamiltonian of a quantum system starting from a specified initial pure state. We first obtain the probability distribution of the results of measurements of this spreading operator at a certain instant of time, and compute the characteristic function of this distribution. We show that the moments of this characteristic function are related to the so-called generalised spread complexities, and obtain expressions for them in several cases when the Hamiltonian is an element of a Lie algebra. Furthermore, by considering a continuum limit of the Krylov basis, we show that the generalised spread complexities of higher orders have a peak in the time evolution for a random matrix Hamiltonian belonging to the Gaussian unitary ensemble. We also obtain an upper bound in the change in generalised spread complexity at an arbitrary time in terms of the operator norm of the Hamiltonian and discuss the significance of these results.
Abstract Krylov complexity is considered to provide a measure of the growth of operators evolving under Hamiltonian dynamics. The main strategy is the analysis of the structure of Krylov subspace KM(H,η)\mathcal {K}_M(\mathcal {H},\eta )KM​(H,η) spanned by the multiple applications of the Liouville operator L\mathcal {L}L defined by the commutator in terms of a Hamiltonian H\mathcal {H}H, L:=[H,⋅]\mathcal {L}:=[\mathcal {H},\cdot ]L:=[H,⋅] acting on an operator η, KM(H,η)=span{η,Lη,…,LM−1η}\mathcal {K}_M(\mathcal {H},\eta )=\text{span}\lbrace \eta ,\mathcal {L}\eta ,\ldots ,\mathcal {L}^{M-1}\eta \rbraceKM​(H,η)=span{η,Lη,…,LM−1η}. For a given inner product ( ·, ·) of the operators, the orthonormal basis {On}\lbrace \mathcal {O}_n\rbrace{On​} is constructed from O0=η/(η,η)\mathcal {O}_0=\eta /\sqrt{(\eta ,\eta )}O0​=η/(η,η)​ by Lanczos algorithm. The moments μm=(O0,LmO0)\mu _m=(\mathcal {O}_0,\mathcal {L}^m\mathcal {O}_0)μm​=(O0​,LmO0​) are closely related to the important data {bn} called Lanczos coefficients. I present the exact and explicit expressions of the moments {μm} for 16 quantum mechanical systems which are exactly solvable both in the Schrödinger and Heisenberg pictures. The operator η is the variable of the eigenpolynomials. Among them six systems show a clear sign of ‘non-complexity’ as vanishing higher Lanczos coefficients bm = 0, m ≥ 3.
The classical stochastic differential equation given as dX(t,ω)=a(t,X) dt+b(t,X) dQ(t),X(t0)=X0,t∈[t0,T],dX(t, \omega) = a(t, X) \, dt + b(t, X) \, dQ(t), \quad X(t_0) = X_0, \quad t \in [t_0, T],dX(t,ω)=a(t,X)dt+b(t,X)dQ(t),X(t0​)=X0​,t∈[t0​,T], where the driving process Q(t) Q(t) Q(t) is a martingale, and a a a and b b b are adapted functionals has several numerical schemes developed for it, where each exhibits distinct stability and convergence properties depending on the nature of the driving process and the functional space of the solution. A generalization of this equation is the quantum stochastic differential equation introduced by Hudson and Parthasarathy, expressed as dX(t)=E(t,X(t)) dΛπ(t)+F(t,X(t)) dAf†(t)+G(t,X(t)) dAg(t)+H(t,X(t)) dt,dX(t) = E(t, X(t)) \, d\Lambda_\pi(t) + F(t, X(t)) \, dA_f^\dagger(t) + G(t, X(t)) \, dA_g(t) + H(t, X(t)) \, dt,dX(t)=E(t,X(t))dΛπ​(t)+F(t,X(t))dAf†​(t)+G(t,X(t))dAg​(t)+H(t,X(t))dt, where E,F,G, E, F, G, E,F,G, and H H H are stochastic operator-valued functions defined on a Hilbert space. In 1992, Ekhaquere reformulated this equation in an equivalent form involving the non-classical differential equation stated as; ddt⟨η,X(t)ξ⟩=P(t,X(t))⟨η,ξ⟩,X(t0)=X0,t∈[t0,T],\frac{d}{dt} \langle \eta, X(t) \xi \rangle = P(t, X(t)) \langle \eta, \xi \rangle, \quad X(t_0) = X_0, \quad t \in [t_0, T],dtd​⟨η,X(t)ξ⟩=P(t,X(t))⟨η,ξ⟩,X(t0​)=X0​,t∈[t0​,T], which represents an ordinary differential equation of non-classical type. The stochastic process X(t) X(t) X(t) acts as a densely defined linear operator on a tensor product of two Hilbert spaces, one of which is the Boson Fock space. The vectors η \eta η and ξ \xi ξ belong to a dense subset of this tensor product Hilbert space, and the mapping (η,ξ)↦P(t,X)(η,ξ)(\eta, \xi) \mapsto P(t, X)(\eta, \xi)(η,ξ)↦P(t,X)(η,ξ) defines a sesquilinear form for each fixed pair (t,X)(t, X)(t,X). We analyze the numerical approximation of the QSDE using its equivalent inner-product form. The numerical investigation employs three principal methods: the Lagrangian Quadrature Method, the Linear Multistep Scheme, and the Newton–Cotes Method. Each method is carefully designed to ensure the consistency, stability, and convergence of the approximate solution X(t)X(t)X(t) toward the exact stochastic process. These schemes are implemented using Python programming language, which provides a flexible and efficient computational environment for testing the proposed algorithms. Our computational results show that the developed schemes generalize Taylor-type approximations of Itô processes under weak convergence criteria. The proposed algorithms exhibit numerical stability and yield results that compare favorably with analytical benchmarks. Furthermore, the implementation avoids direct approximation of the driving quantum processes, thereby preserving the natural adaptation of the schemes to quantum dynamical models.
Upper and lower bounds are established for the survival probability $\ensuremath{\mid}⟨\ensuremath{\psi}(0)\ensuremath{\mid}\ensuremath{\psi}(t)⟩{\ensuremath{\mid}}^{2}$ of a quantum state, in terms of the energy moments $⟨\ensuremath{\psi}(0)\ensuremath{\mid}{H}^{n}\ensuremath{\mid}\ensuremath{\psi}(0)⟩$. Introducing a cutoff in the energy generally enables considerable improvement in these bounds and allows the method to be used where the exact energy moments do not exist.
Circuit cutting allows quantum circuits to be evaluated on smaller devices at the cost of additional sampling and classical reconstruction. For Hamiltonian-simulation circuits, the target unitary exp⁡[itH]\exp[it\mathbf H]exp[itH] connects this decomposition problem to the structure of the generator. We develop a Hamiltonian-level certificate that assesses exact separability and the accuracy of independent module evolution before a gate decomposition is chosen. For a time-independent Hamiltonian and a fixed module partition, the Hilbert--Schmidt projection onto sums of module-local terms isolates a cross-module residual HnsH_{ns}Hns​. Its vanishing is necessary and sufficient for product evolution at all times; for Pauli-list inputs, this condition is checked in one pass over the combined coefficients. When Hns≠0H_{ns}\ne0Hns​=0, the projected evolution has operator-norm error at most ∣t∣∣∣Hns∣∣op|t| ||H_{ns}||_{op}∣t∣∣∣Hns​∣∣op​. Across a bipartition, an explicit first-order algebraic correction has the same operator-Schmidt rank as HnsH_{ns}Hns​ and leaves a second-order residual. The same Hamiltonian residual connects this approximation to short-time entanglement, determining the leading state-space and operator-space entangling powers and, through its Schmidt spectrum, the leading Choi tripartite-information terms. Numerical experiments test these relations and demonstrate block-factorised simulation up to 202020 qubits.