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•52 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•60 citations

Quantum Algorithms for Hamiltonian Simulation

Dominic William Berry, Graeme Ahokas, Richard Cleve

Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders Abstract 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•100 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

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
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. Sanders Abstract 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 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.