Hamiltonian simulation using linear combinations of unitary operations

By Andrew M. Childs, Nathan Wiebe. Quantum information & computation, 2012

806 citations recorded by the source corpus.

We present a new approach to simulating Hamiltonian dynamics based on implementing linear combinations of unitary operations rather than products of unitary operations. The resulting algorithm has superior performance to existing simulation algorithms based on product formulas and, most notably, scales better with the simulation error than any known Hamiltonian simulation technique. Our main tool is a general method to nearly deterministically implement linear combinations of nearby unitary operations, which we show is optimal among a large class of methods.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/c4091149da5970f513e043473d86ae592d3768c2

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 Computational Theory and Mathematics

In Hardware and Architecture

Citations in the corpus

Elucidating reaction mechanisms on quantum computers (2016, background): “[46] Andrew M Childs and Nathan Wiebe, “Hamiltonian simulation using linear combinations of unitary operations,” Quantum Information & Computation 12, 901– 924 (2012).”
Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision (2015, methodology): “Our technique for implementing linear combinations of unitary operations arises from previous work on Hamiltonian simulation [BCC + 14, Kot14, BCC + 15, BCK15] (see also [SOG + 02, CW12] for previous related approaches).”
Generalized Quantum Signal Processing (2023, methodology): “…algorithm theory have revealed a powerful, overarching insight: the majority of prominent quantum algorithms, such as Hamiltonian simulation [1–4], quantum search [5–7], factoring [8], and quantum walks [7, 9], can be fundamentally reduced to the central task of implementing a matrix function…”
Hamiltonian Simulation in the Interaction Picture (2018, background): “As an example, H = ∑2na j=1 ajUj [4] could be a linear combination of l = 2a unitaries.”
Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity (2018, methodology): “[54].”
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters (2015, background): “Aharonov and Ta-Shma gave an efficient simulation algorithm for the more general class of sparse Hamiltonians [2], and much subsequent work has given improved simulations [4, 5, 6, 7, 8, 12, 17, 18].”
Evaluating analytic gradients on quantum hardware (2018, methodology): “Secondly, we show that any other gate can be handled by a method that involves a coherent linear combination of unitaries routine [12].”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “The first methods introduced to solve this problem were Trotter formula decompositions [9, 39] and subsequently methods based on linear combinations of unitaries were developed [19] to provide better asymptotic scaling of the cost of simulation.”
Hamiltonian Simulation by Qubitization (2016, methodology): “e rst explicit quantum algorithms were discovered by Lloyd [31] for local interactions, and then generalized by Aharonov and Ta-Shma [3] to sparse Hamiltonians. Celebrated achievements over the years [20,8,32,10,33] have each ignited a urry of activity in diverse applications from quantum algorithms”
Optimal Hamiltonian Simulation by Quantum Signal Processing. (2016, background): “Two key properties distinguish quantum signal processing from routines that can effect similar transformations, such as quantum phase estimation [23] or linearcombination-of-unitaries [16, 18, 19] which require a large number of ancilla.”
Circuit-centric quantum classifiers (2018, methodology): “Linear combination of unitaries is a known technique in quantum mechanics [37], where the sum is implemented in a coherent fashion.”