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

Hamiltonian Simulation by Uniform Spectral Amplification

Guang Hao Low, Isaac L. Chuang

Published Jul 17, 2017• 38 citations
arXivHTMLPDF

Abstract

The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian $\hat{H}$, and the quantum circuit $\hat{U}$ that encodes its description. In the quest to better approximate time-evolution $e^{-i\hat{H}t}$ with error $ε$, we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits $\hat{U}$ for generalized measurement. This allows us to define a \emph{uniform spectral amplification} problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring $\hat{U}$ into $n=1,2,3$ unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian, specializing these results allow us simulate time-evolution by $d$-sparse Hamiltonians using $\mathcal{O}\left(t(d \|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/ε)}\right)$ queries, where $\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}$. Up to logarithmic factors, this is a polynomial improvement upon prior art using $\mathcal{O}\left(td\|\hat H\|_{\text{max}}+\frac{\log{(1/ε)}}{\log\log{(1/ε)}}\right)$ or $\mathcal{O}(t^{3/2}(d \|\hat H\|_{\text{max}}\|\hat H\|_{1}\|\hat H\|/ε)^{1/2})$ queries. In the process, we also prove a matching lower bound of $Ω(t(d\|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2})$ queries, present a distortion-free generalization of spectral gap amplification, and an amplitude amplification algorithm that performs multiplication on unknown state amplitudes.

DOI
10.48550/arxiv.1707.05391

Related papers

Hamiltonian Simulation by Qubitization

Guang Hao Low, Isaac L. Chuang

We present the problem of approximating the time-evolution operator e−iH^t to error ϵ , where the Hamiltonian H^=(⟨G|⊗I^)U^(|G⟩⊗I^) is the projection of a unitary oracle U^ onto the state |G⟩ created by another unitary oracle. Our algorithm solves this with a query complexity O(t+log⁡(1/ϵ)) to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are d -sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where H^ is a density matrix. A key technical result is `qubitization', which uses the controlled version of these oracles to embed any H^ in an invariant SU(2) subspace. A large class of operator functions of H^ can then be computed with optimal query complexity, of which e−iH^t is a special case.

arXiv:1610.06546•Quantum•Jul 12, 2019•854 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

Hamiltonian Simulation by Qubitization

Guang Hao Low, Isaac L. Chuang

We present the problem of approximating the time-evolution operator e-iHt to error ϵ, where the Hamiltonian H = ((G|⊗I)U (|Gi⊗I) is the projection of a unitary oracle U onto the state |Gi created by another unitary oracle. Our algorithm solves this with a query complexity O ( t + log(1/ϵ) ) to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are d-sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where H is a density matrix. A key technical result is 'qubitization', which uses the controlled version of these oracles to embed any H in an invariant SU(2) subspace. A large class of operator functions of H can then be computed with optimal query complexity, of which e-iHt is a special case.

•Jul 1, 2019•652 citations

Query-Optimal and Gate-Efficient Lindbladian Simulation

Boyang Chen, Minbo Gao, Xinzhao Wang +1 more

We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian $H$ and a projected unitary encoding of the stacked jump operator $B=\sum_{k=1}^m \lvert k\rangle\otimes L_k$, with normalization factors $α_H$ and $α_B$, respectively. For evolution time $t$, set $τ=(α_H+α_B^2)t$. The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)$ oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.

quant-pharXiv:2609.18757•Sep 17, 2026•0 citations

Spectral Gap Amplification

R. D. Somma, S. Boixo

Many problems can be solved by preparing a specific eigenstate of some Hamiltonian $H$. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of $H$ for that eigenstate and the cost of evolving with $H$ for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian $H'$ with the same eigenstate as $H$ but a bigger spectral gap, requiring that constant-time evolutions with $H'$ and $H$ are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when $H$ satisfies a frustration-free property and give $H'$ for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states, which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.

arXiv:1110.2494•SIAM Journal on Computing•Jan 1, 2013•50 citations

Learning Clifford-structured quantum unitaries and Hamiltonians

Arkopal Dutt, Dale Jacobs, John Jeang +2 more

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.

quant-pharXiv:2608.09912•Aug 11, 2026•0 citations
The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian H^\hat{H}H^, and the quantum circuit U^\hat{U}U^ that encodes its description. In the quest to better approximate time-evolution e−iH^te^{-i\hat{H}t}e−iH^t with error εεε, we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits U^\hat{U}U^ for generalized measurement. This allows us to define a \emph{uniform spectral amplification} problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring U^\hat{U}U^ into n=1,2,3n=1,2,3n=1,2,3 unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian, specializing these results allow us simulate time-evolution by ddd-sparse Hamiltonians using O(t(d∥H^∥max∥H^∥1)1/2log⁡(t∥H^∥/ε))\mathcal{O}\left(t(d \|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/ε)}\right)O(t(d∥H^∥max​∥H^∥1​)1/2log(t∥H^∥/ε)) queries, where ∥H^∥≤∥H^∥1≤d∥H^∥max\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}∥H^∥≤∥H^∥1​≤d∥H^∥max​. Up to logarithmic factors, this is a polynomial improvement upon prior art using O(td∥H^∥max+log⁡(1/ε)log⁡log⁡(1/ε))\mathcal{O}\left(td\|\hat H\|_{\text{max}}+\frac{\log{(1/ε)}}{\log\log{(1/ε)}}\right)O(td∥H^∥max​+loglog(1/ε)log(1/ε)​) or O(t3/2(d∥H^∥max∥H^∥1∥H^∥/ε)1/2)\mathcal{O}(t^{3/2}(d \|\hat H\|_{\text{max}}\|\hat H\|_{1}\|\hat H\|/ε)^{1/2})O(t3/2(d∥H^∥max​∥H^∥1​∥H^∥/ε)1/2) queries. In the process, we also prove a matching lower bound of Ω(t(d∥H^∥max∥H^∥1)1/2)Ω(t(d\|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2})Ω(t(d∥H^∥max​∥H^∥1​)1/2) queries, present a distortion-free generalization of spectral gap amplification, and an amplitude amplification algorithm that performs multiplication on unknown state amplitudes.
We present the problem of approximating the time-evolution operator e−iH^t to error ϵ , where the Hamiltonian H^=(⟨G|⊗I^)U^(|G⟩⊗I^) is the projection of a unitary oracle U^ onto the state |G⟩ created by another unitary oracle. Our algorithm solves this with a query complexity O(t+log⁡(1/ϵ)) to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are d -sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where H^ is a density matrix. A key technical result is `qubitization', which uses the controlled version of these oracles to embed any H^ in an invariant SU(2) subspace. A large class of operator functions of H^ can then be computed with optimal query complexity, of which e−iH^t is a special case.
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 present the problem of approximating the time-evolution operator e-iHt to error ϵ, where the Hamiltonian H = ((G|⊗I)U (|Gi⊗I) is the projection of a unitary oracle U onto the state |Gi created by another unitary oracle. Our algorithm solves this with a query complexity O ( t + log(1/ϵ) ) to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are d-sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where H is a density matrix. A key technical result is 'qubitization', which uses the controlled version of these oracles to embed any H in an invariant SU(2) subspace. A large class of operator functions of H can then be computed with optimal query complexity, of which e-iHt is a special case.
We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian HHH and a projected unitary encoding of the stacked jump operator B=∑k=1m∣k⟩⊗LkB=\sum_{k=1}^m \lvert k\rangle\otimes L_kB=∑k=1m​∣k⟩⊗Lk​, with normalization factors αHα_HαH​ and αBα_BαB​, respectively. For evolution time ttt, set τ=(αH+αB2)tτ=(α_H+α_B^2)tτ=(αH​+αB2​)t. The algorithm approximates the evolution channel to diamond-norm error ε\varepsilonε using O ⁣(τ+log⁡(1/ε)log⁡ ⁣(e+log⁡(1/ε)/τ))O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)O(τ+log(e+log(1/ε)/τ)log(1/ε)​) oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.
Many problems can be solved by preparing a specific eigenstate of some Hamiltonian HHH. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of HHH for that eigenstate and the cost of evolving with HHH for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian H′H'H′ with the same eigenstate as HHH but a bigger spectral gap, requiring that constant-time evolutions with H′H'H′ and HHH are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when HHH satisfies a frustration-free property and give H′H'H′ for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states, which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning nnn-qubit quantum unitaries UUU and Hamiltonians HHH, given query access to UUU or the unitary evolution of HHH, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form U=∑iαiCiU = \sum_i α_i C_iU=∑i​αi​Ci​ over Cliffords CiC_iCi​ with bounded Clifford extent ∑i∣αi∣\sum_i |α_i|∑i​∣αi​∣. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary UUU with optimal Clifford fidelity opt\textsf{opt}opt, outputs a Clifford unitary witnessing fidelity ≥opt−ε\geq \textsf{opt} - \varepsilon≥opt−ε for some error ε>0\varepsilon > 0ε>0, in time poly(n,(1/ε)log⁡(1/ε))\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})poly(n,(1/ε)log(1/ε)). We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity Ω(2n)Ω(2^n)Ω(2n)) in the Pauli basis but are Clifford structured.