Efficient Quantum Algorithms for Simulating Sparse Hamiltonians

By Dominic W. Berry, Graeme Ahokas, Richard Cleve, Barry C. Sanders. 2005

877 citations recorded by the source corpus.

We present an efficient quantum algorithm for simulating the evolution of a quantum state for a sparse Hamiltonian H over a given time t in terms of a procedure for computing the matrix entries of H. In particular, when H acts on n qubits, has at most a constant number of nonzero entries in each row/column, and ||H|| is bounded by a constant, we may select any positive integer k such that the simulation requires O((log*n)t1+1/2k) accesses to matrix entries of H. We also show that the temporal scaling cannot be significantly improved beyond this, because sublinear time scaling is not possible.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/9c171dfe55abe2511b08926f8e04f7afce283ea6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Quantum Metropolis sampling (2009, methodology): “The simulation method described in [2] relies on the fact that we are able to decompose the Hamiltonian into a sum of local Hamiltonians hk with H = k hk that can be simulated by themselves on a quantum computer efficiently.”
Automated optimization of large quantum circuits with continuous parameters (2017, methodology): “We also considered circuits for the product formula approach to Hamiltonian simulation.(17) In both cases, we focused on circuit sizes likely to be useful in applications that outperform classical computation, and ran experiments with different types of adders and product formulas.”
Polynomial-time quantum algorithm for the simulation of chemical dynamics (2008, methodology): “The error due to time discretization can be systematically improved by use of higher-order Trotter schemes (24).”
High-order quantum algorithm for solving linear differential equations (2010, methodology): “Evolution under this Hamiltonian can be solved by methods considered in previous work [6, 8].”
Universal computation by quantum walk. (2008, background): “ca two models are equivalent, since the quantum walk on any sufficiently sparse graph can be efficiently simulated by a universal quantum computer [4, 21, 22, 23].”
Low-Depth Quantum Simulation of Materials (2017, methodology): “[80,84,85] to show a technique for performing time evolution of arbitrary Hamiltonians with sublogarithmic dependence on the inverse precision.”
Variational Quantum Linear Solver (2019, background): “In general, this can only be achieved with a quantum circuit of size linear in κ as per the “no fast-forwarding theorem” [63, 64].”
Elucidating reaction mechanisms on quantum computers (2016, background): “[45] Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C Sanders, “Efficient quantum algorithms for sim-”
Quantum Simulation (2013, methodology): “This question has been thoroughly studied, and several methods have been developed (see, e.g., (Berry et al., 2007; Bravyi et al., 2008; Bremner et al., 2005; Brown et al., 2011; Dodd et al., 2002; Dür et al., 2008; Hastings, 2006; Wang and Zanardi, 2002; Wocjan et al., 2002a,b,c)), but it still…”
Efficient Variational Quantum Simulator Incorporating Active Error Minimization (2016, methodology): “For the lowest-order symmetric TrotterSuzuki decomposition [60,61], each time step in Eq.”
Higher order decompositions of ordered operator exponentials (2008, methodology): “in [5] and that used by Suzuki in [9]; we split the ordered exponential into a product of ordinary exponentials, each of which has a short duration.”
Strawberry Fields: A Software Platform for Photonic Quantum Computing (2018, methodology): “In the discrete-variable qubit model, efficient methods of Hamiltonian simulation have been discussed at length, providing several implementations depending on properties of the Hamiltonian, and resulting in a linear simulation time [89, 90].”
Quantum Computation and Quantum Information (2012, background): “See Abrams and Lloyd (1997), Aspuru-Guzik, Dutoi and Head-Gordon (2005), Ben-nett et al. (2002), Berry et al. (2007), Freedman, Ki-taev and Wang (2002), Jan´e et al. (2003), Boghosian and Taylor (1998), Lloyd (1996), Nielsen and Chuang (2000), and Zalka (1998).”
Hamiltonian Simulation by Qubitization (2016, background): “This can be improved with higher-ordered Trotter-Suzuki product formulas [6] which bound the”
Toward the first quantum simulation with quantum speedup (2017, methodology): “Recent work has led to algorithms with signiﬁcantly improved asymptotic performance as a function of various parameters such as the evolution time and the allowed simulation error (13–17).”