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 simulation of Hamiltonians

Robin Kothari

Published Aug 18, 2010• 2 citations
OpenAlex

Abstract

The problem considered in this thesis is the following: We are given a Hamiltonian H and time t, and our goal is to approximately implement the unitary operator e^{-iHt} with an efficient quantum algorithm. We present an efficient algorithm for simulating sparse Hamiltonians. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian acts, this algorithm uses (d^2(d+log^* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log^* N)||Ht||)^{1+o(1)}. In terms of the parameter t, these algorithms are essentially optimal due to a no--fast-forwarding theorem. \n \nIn the second part of this thesis, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, and rule out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian H. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walks cannot be dramatically improved in general. We also show some positive results about simulating structured Hamiltonians efficiently.

Related papers

Limitations on the simulation of non-sparse hamiltonians

Andrew M. Childs, Robin Kothari

The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N × N Hamiltonian H for time t can be simulated using O(||Ht|| poly(logN)) operations, which is essentially optimal due to a no-fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations ontheir simulation. We generalize the no-fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time o(||Ht||), even though ||H|| is not a uniquemeasure of the size of a dense Hamiltonian H. We also present a stronger limitationruling out the possibility of generic simulations taking time poly(||Ht||; logN), showingthat known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonianscan be simulated efficiently, such as those with graphs of small arboricity.

•Jul 1, 2010•56 citations

Limitations on the simulation of non-sparse Hamiltonians

Andrew M. Childs, Robin Kothari

The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse $N \times N$ Hamiltonian $H$ for time $t$ can be simulated using $\O(\norm{Ht} \poly(\log N))$ operations, which is essentially optimal due to a no--fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time $\o(\norm{Ht})$, even though $\norm{H}$ is not a unique measure of the size of a dense Hamiltonian $H$. We also present a stronger limitation ruling out the possibility of generic simulations taking time $\poly(\norm{Ht},\log N)$, showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity.

Quantum Information and Computation•Jul 1, 2010•61 citations

Quantum Algorithms for Hamiltonian Simulation

Dominic William Berry, Graeme Ahokas, Richard Cleve

Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. SandersAbstract Arguably one of the most important applications of quantum computers is the simulation of quantum systems. In the case where the Hamiltonian consists of a sum of interaction terms between small subsystems, the simulation is thought to be exponentially more efficient than classical simulation. More generally, evolution under suitably specified sparse Hamiltonians may be efficiently simulated. In recent work we have shown that the complexity of simulating evolution under a Hamiltonian is very close to linear in the evolution time. In addition, we have shown that in the general case of a sparse Hamiltonian the complexity grows slowly with respect to the number of qubits. In this chapter we review these results.

Chapman & Hall/CRC eBooks•Sep 19, 2007•4 citations

Black-box hamiltonian simulation and unitary implementation

Dominic William Berry, Andrew M. Childs

We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N × N unitary operation use O(N2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N2/3(log logN)4/3) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(√N) queries, which is optimal.

Quantum Information and Computation•Jan 1, 2012•124 citations

The quantum query complexity of implementing black-box unitary transformations

Dominic William Berry, Andrew M. Childs

We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D^4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N x N unitary operation use O(N^2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(sqrt{N}) queries, which is optimal.

arXiv:0910.4157•Oct 22, 2009•4 citations

Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm

Zecheng Li, Chunhao Wang

We give a quantum algorithm for simulating a $d$-sparse Hermitian Hamiltonian $H$, assuming a known upper bound $Λ$ on its maximum column Euclidean norm $\|H\|_{1\to2}$. For $tΛ\ge1/2$, simulation with operator-norm error $ε$ uses \[ O\!\left(tΛ\sqrt d+\sqrt d\log(2/ε)\right) \] sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For $d>1$ and $tΛ\ge\log(2/ε)$, the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of $Λ$. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters. As applications, we obtain $O(κ\sqrt d\,\mathrm{polylog}(κ/ε))$ queries for solving $d$-sparse quantum linear systems with $\|A\|\le1$ and $\|A^{-1}\|\leκ$, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most $d$ nonzero entries per row and column using $O(\sqrt d\log(2/ε))$ queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields $Θ(\sqrt N)$ queries for arbitrary $N\times N$ unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].

quant-pharXiv:2610.02030•Oct 2, 2026•0 citations
The problem considered in this thesis is the following: We are given a Hamiltonian H and time t, and our goal is to approximately implement the unitary operator e^{-iHt} with an efficient quantum algorithm. We present an efficient algorithm for simulating sparse Hamiltonians. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian acts, this algorithm uses (d^2(d+log^* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log^* N)||Ht||)^{1+o(1)}. In terms of the parameter t, these algorithms are essentially optimal due to a no--fast-forwarding theorem. \n \nIn the second part of this thesis, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, and rule out generic simulations taking time o(||Ht||), even though ||H|| is not a unique measure of the size of a dense Hamiltonian H. We also present a stronger limitation ruling out the possibility of generic simulations taking time poly(||Ht||,log N), showing that known simulations based on discrete-time quantum walks cannot be dramatically improved in general. We also show some positive results about simulating structured Hamiltonians efficiently.
The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N × N Hamiltonian H for time t can be simulated using O(||Ht|| poly(logN)) operations, which is essentially optimal due to a no-fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations ontheir simulation. We generalize the no-fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time o(||Ht||), even though ||H|| is not a uniquemeasure of the size of a dense Hamiltonian H. We also present a stronger limitationruling out the possibility of generic simulations taking time poly(||Ht||; logN), showingthat known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonianscan be simulated efficiently, such as those with graphs of small arboricity.
The problem of simulating sparse Hamiltonians on quantum computers is well studied. The evolution of a sparse N×NN \times NN×N Hamiltonian HHH for time ttt can be simulated using $\O(\norm{Ht} \poly(\log N))$ operations, which is essentially optimal due to a no--fast-forwarding theorem. Here, we consider non-sparse Hamiltonians and show significant limitations on their simulation. We generalize the no--fast-forwarding theorem to dense Hamiltonians, ruling out generic simulations taking time $\o(\norm{Ht})$, even though $\norm{H}$ is not a unique measure of the size of a dense Hamiltonian HHH. We also present a stronger limitation ruling out the possibility of generic simulations taking time $\poly(\norm{Ht},\log N)$, showing that known simulations based on discrete-time quantum walk cannot be dramatically improved in general. On the positive side, we show that some non-sparse Hamiltonians can be simulated efficiently, such as those with graphs of small arboricity.
Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. SandersAbstract Arguably one of the most important applications of quantum computers is the simulation of quantum systems. In the case where the Hamiltonian consists of a sum of interaction terms between small subsystems, the simulation is thought to be exponentially more efficient than classical simulation. More generally, evolution under suitably specified sparse Hamiltonians may be efficiently simulated. In recent work we have shown that the complexity of simulating evolution under a Hamiltonian is very close to linear in the evolution time. In addition, we have shown that in the general case of a sparse Hamiltonian the complexity grows slowly with respect to the number of qubits. In this chapter we review these results.
We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N × N unitary operation use O(N2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N2/3(log logN)4/3) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(√N) queries, which is optimal.
We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D^4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N x N unitary operation use O(N^2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(sqrt{N}) queries, which is optimal.
We give a quantum algorithm for simulating a ddd-sparse Hermitian Hamiltonian HHH, assuming a known upper bound ΛΛΛ on its maximum column Euclidean norm ∥H∥1→2\|H\|_{1\to2}∥H∥1→2​. For tΛ≥1/2tΛ\ge1/2tΛ≥1/2, simulation with operator-norm error εεε uses O ⁣(tΛd+dlog⁡(2/ε)) O\!\left(tΛ\sqrt d+\sqrt d\log(2/ε)\right) O(tΛd​+d​log(2/ε)) sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For d>1d>1d>1 and tΛ≥log⁡(2/ε)tΛ\ge\log(2/ε)tΛ≥log(2/ε), the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of ΛΛΛ. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters. As applications, we obtain O(κd polylog(κ/ε))O(κ\sqrt d\,\mathrm{polylog}(κ/ε))O(κd​polylog(κ/ε)) queries for solving ddd-sparse quantum linear systems with ∥A∥≤1\|A\|\le1∥A∥≤1 and ∥A−1∥≤κ\|A^{-1}\|\leκ∥A−1∥≤κ, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most ddd nonzero entries per row and column using O(dlog⁡(2/ε))O(\sqrt d\log(2/ε))O(d​log(2/ε)) queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields Θ(N)Θ(\sqrt N)Θ(N​) queries for arbitrary N×NN\times NN×N unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].