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

Exponential improvement in precision for Hamiltonian-evolution simulation

Dominic William Berry, Richard Cleve, Rolando D. Somma

Published Aug 25, 2013• 10 citations
arXivHTMLPDF

Abstract

We provide a quantum method for simulating Hamiltonian evolution with complexity polynomial in the logarithm of the inverse error. This is an exponential improvement over existing methods for Hamiltonian simulation. In addition, its scaling with respect to time is close to linear, and its scaling with respect to the time derivative of the Hamiltonian is logarithmic. These scalings improve upon most existing methods. Our method is to use a compressed Lie-Trotter formula, based on recent ideas for efficient discrete-time simulations of continuous-time quantum query algorithms.

DOI
10.48550/arxiv.1308.5424

Related papers

Exponential improvement in precision for simulating sparse Hamiltonians

Dominic William Berry, Andrew M. Childs, Richard Cleve +2 more

We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d-sparse Hamiltonian H on n qubits can be simulated for time t with precision ε using O(τlog(τ/ε)/log log(τ/ε)) queries and O(τnlog2(τ/ε)/log log(τ/ε)) additional 2-qubit gates, where τ=d2||H||maxt. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.

arXiv:1312.1414•ACM Symposium on Theory of Computing (STOC)•May 31, 2014•324 citations

EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS

Dominic William Berry, Andrew M. Childs, Richard Cleve +2 more

We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a $d$ -sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$ with precision $\unicode[STIX]{x1D716}$ using $O(\unicode[STIX]{x1D70F}(\log (\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716})/\log \log (\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716})))$ queries and $O(\unicode[STIX]{x1D70F}(\log ^{2}(\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716})/\log \log (\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716}))n)$ additional 2-qubit gates, where $\unicode[STIX]{x1D70F}=d^{2}\Vert H\Vert _{\max }t$ . Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault-correction procedure. Our simplification relies on a new form of ‘oblivious amplitude amplification’ that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.

Forum of Mathematics Sigma•Jan 1, 2017•31 citations

Optimization of quantum Hamiltonian evolution: From two projection operators to local Hamiltonians

Apoorva D. Patel, Anjani Priyadarsini

Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points and different series expansions. A choice among these possibilities can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in the error bound, and is exponentially superior in error complexity to the scheme based on the straightforward application of the Lie–Trotter formula. The strategy is then extended first to simulation of any Hamiltonian that is a linear combination of two projection operators, and then to any local efficiently computable Hamiltonian. The key feature is to construct an evolution in terms of the largest possible steps instead of taking small time steps. Reflection operations and Chebyshev expansions are used to efficiently control the total error on the overall evolution, without worrying about discretization errors for individual steps. We also use a digital implementation of quantum states that makes linear algebra operations rather simple to perform.

International Journal of Quantum Information•Sep 13, 2016•1 citation

Exponentially more precise quantum simulation of fermions in second quantization

Ryan Babbush, Dominic William Berry, Ian Kivlichan +3 more

We introduce novel algorithms for the quantum simulation of fermionic systems which are dramatically more efficient than those based on the Lie–Trotter–Suzuki decomposition. We present the first application of a general technique for simulating Hamiltonian evolution using a truncated Taylor series to obtain logarithmic scaling with the inverse of the desired precision. The key difficulty in applying algorithms for general sparse Hamiltonian simulation to fermionic simulation is that a query, corresponding to computation of an entry of the Hamiltonian, is costly to compute. This means that the gate complexity would be much higher than quantified by the query complexity. We solve this problem with a novel quantum algorithm for on-the-fly computation of integrals that is exponentially faster than classical sampling. While the approaches presented here are readily applicable to a wide class of fermionic models, we focus on quantum chemistry simulation in second quantization, perhaps the most studied application of Hamiltonian simulation. Our central result is an algorithm for simulating an N spin–orbital system that requires O ~ ( N 5 t ) gates. This approach is exponentially faster in the inverse precision and at least cubically faster in N than all previous approaches to chemistry simulation in the literature.

arXiv:1506.01020•New Journal of Physics•Mar 24, 2016•135 citations

Improved Time-independent Hamiltonian Simulation

Nhat A. Nghiem

We describe a simple method for simulating time-independent Hamiltonian $H$ that could be decomposed as $H = \sum_{i=1}^m H_i$ where each $H_i$ can be efficiently simulated. Approaches relying on product formula generally work by splitting the evolution time into segments, and approximate the evolution in each segment by the evolution of composing Hamiltonian $H_i$. This key step incur a constraint, that prohibits a (poly)logarithmic scaling on approximation error. We employ the recently introduced quantum singular value transformation framework to utilize the ability to simulate $H_i$ in an alternative way, which then allows us to construct and simulate the main Hamiltonian $H$ with polylogarithmical scaling on the inverse of desired error, which is a major improvement with respect to product formula approaches.

arXiv:2410.15256•Oct 20, 2024•0 citations

Optimisation of Quantum Hamiltonian Evolution: Two Projection Operators

Apoorva D. Patel, Anjani Priyadarsini

Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points. A choice among these trajectories can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in error bound, and is exponentially superior in error complexity to the scheme based on straightforward application of the Lie-Trotter formula. The strategy is then extended to simulation of any Hamiltonian that is a linear combination of two projection operators. The key feature is to construct an evolution in terms of reflection operators instead of taking small time steps. The reflection operation amounts to taking the largest possible step consistent with unitarity in the specified direction. Though that makes discretisation error for individual steps large, the total error on the overall evolution can be efficiently controlled.

arXiv:1503.01755•Mar 5, 2015•0 citations
We provide a quantum method for simulating Hamiltonian evolution with complexity polynomial in the logarithm of the inverse error. This is an exponential improvement over existing methods for Hamiltonian simulation. In addition, its scaling with respect to time is close to linear, and its scaling with respect to the time derivative of the Hamiltonian is logarithmic. These scalings improve upon most existing methods. Our method is to use a compressed Lie-Trotter formula, based on recent ideas for efficient discrete-time simulations of continuous-time quantum query algorithms.
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d-sparse Hamiltonian H on n qubits can be simulated for time t with precision ε using O(τlog(τ/ε)/log log(τ/ε)) queries and O(τnlog2(τ/ε)/log log(τ/ε)) additional 2-qubit gates, where τ=d2||H||maxt. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a ddd -sparse Hamiltonian HHH acting on nnn qubits can be simulated for time ttt with precision $\unicode[STIX]{x1D716}$ using $O(\unicode[STIX]{x1D70F}(\log (\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716})/\log \log (\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716})))$ queries and $O(\unicode[STIX]{x1D70F}(\log ^{2}(\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716})/\log \log (\unicode[STIX]{x1D70F}/\unicode[STIX]{x1D716}))n)$ additional 2-qubit gates, where $\unicode[STIX]{x1D70F}=d^{2}\Vert H\Vert _{\max }t$ . Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also simplify the analysis of this conversion, avoiding the need for a complex fault-correction procedure. Our simplification relies on a new form of ‘oblivious amplitude amplification’ that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.
Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points and different series expansions. A choice among these possibilities can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in the error bound, and is exponentially superior in error complexity to the scheme based on the straightforward application of the Lie–Trotter formula. The strategy is then extended first to simulation of any Hamiltonian that is a linear combination of two projection operators, and then to any local efficiently computable Hamiltonian. The key feature is to construct an evolution in terms of the largest possible steps instead of taking small time steps. Reflection operations and Chebyshev expansions are used to efficiently control the total error on the overall evolution, without worrying about discretization errors for individual steps. We also use a digital implementation of quantum states that makes linear algebra operations rather simple to perform.
We introduce novel algorithms for the quantum simulation of fermionic systems which are dramatically more efficient than those based on the Lie–Trotter–Suzuki decomposition. We present the first application of a general technique for simulating Hamiltonian evolution using a truncated Taylor series to obtain logarithmic scaling with the inverse of the desired precision. The key difficulty in applying algorithms for general sparse Hamiltonian simulation to fermionic simulation is that a query, corresponding to computation of an entry of the Hamiltonian, is costly to compute. This means that the gate complexity would be much higher than quantified by the query complexity. We solve this problem with a novel quantum algorithm for on-the-fly computation of integrals that is exponentially faster than classical sampling. While the approaches presented here are readily applicable to a wide class of fermionic models, we focus on quantum chemistry simulation in second quantization, perhaps the most studied application of Hamiltonian simulation. Our central result is an algorithm for simulating an N spin–orbital system that requires O ~ ( N 5 t ) gates. This approach is exponentially faster in the inverse precision and at least cubically faster in N than all previous approaches to chemistry simulation in the literature.
We describe a simple method for simulating time-independent Hamiltonian HHH that could be decomposed as H=∑i=1mHiH = \sum_{i=1}^m H_iH=∑i=1m​Hi​ where each HiH_iHi​ can be efficiently simulated. Approaches relying on product formula generally work by splitting the evolution time into segments, and approximate the evolution in each segment by the evolution of composing Hamiltonian HiH_iHi​. This key step incur a constraint, that prohibits a (poly)logarithmic scaling on approximation error. We employ the recently introduced quantum singular value transformation framework to utilize the ability to simulate HiH_iHi​ in an alternative way, which then allows us to construct and simulate the main Hamiltonian HHH with polylogarithmical scaling on the inverse of desired error, which is a major improvement with respect to product formula approaches.
Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points. A choice among these trajectories can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in error bound, and is exponentially superior in error complexity to the scheme based on straightforward application of the Lie-Trotter formula. The strategy is then extended to simulation of any Hamiltonian that is a linear combination of two projection operators. The key feature is to construct an evolution in terms of reflection operators instead of taking small time steps. The reflection operation amounts to taking the largest possible step consistent with unitarity in the specified direction. Though that makes discretisation error for individual steps large, the total error on the overall evolution can be efficiently controlled.