Optimal Hamiltonian Simulation by Quantum Signal Processing.

By Guang Hao Low, Isaac L. Chuang. Physical Review Letters, 2016

942 citations recorded by the source corpus.

The physics of quantum mechanics is the inspiration for, and underlies, quantum computation. As such, one expects physical intuition to be highly influential in the understanding and design of many quantum algorithms, particularly simulation of physical systems. Surprisingly, this has been challenging, with current Hamiltonian simulation algorithms remaining abstract and often the result of sophisticated but unintuitive constructions. We contend that physical intuition can lead to optimal simulation methods by showing that a focus on simple single-qubit rotations elegantly furnishes an optimal algorithm for Hamiltonian simulation, a universal problem that encapsulates all the power of quantum computation. Specifically, we show that the query complexity of implementing time evolution by a d-sparse Hamiltonian H[over ^] for time-interval t with error ε is O[td∥H[over ^]∥_{max}+log(1/ε)/loglog(1/ε)], which matches lower bounds in all parameters. This connection is made through general three-step "quantum signal processing" methodology, comprised of (i) transducing eigenvalues of H[over ^] into a single ancilla qubit, (ii) transforming these eigenvalues through an optimal-length sequence of single-qubit rotations, and (iii) projecting this ancilla with near unity success probability.

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

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

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 Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision (2017, background): “More recent work has streamlined these algorithms and improved their dependence on other parameters [6, 7, 15, 8, 14, 16].”
Efficient Multiphoton Sampling of Molecular Vibronic Spectra on a Superconducting Bosonic Processor (2019, neutral): “Using quantum signal processing [37], the approximate”
A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery (2018, methodology): “In the specific case of quantum chemistry simulations, their T count can be reduced significantly by using more advanced algorithms [50–52], which also profit from arbitrary-angle”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “This enables a simple proof of recent optimal block-Hamiltonian simulation results [43],”
Generalized Quantum Signal Processing (2023, methodology): “√ √ So the idea here is to write a more fine-grained piecewise representation of e itx such that y , hence getting rid of the δ dependence in 8, so the approximation part of the algorithm runs in O (log(1 /ϵ )).”
Hamiltonian Simulation in the Interaction Picture (2018, methodology): “More generally, the complexity of time-independent quantum simulation for generic Hamiltonians, given minimal information, appears to be nearly resolved [11].”
Improved techniques for preparing eigenstates of fermionic Hamiltonians (2017, methodology): “The synthesis of e is typically performed using digital quantum simulation algorithms, such as by Lie-Trotter product formulas,(8) truncated Taylor series,(9) or quantum signal processing.(10) Since the proposal by Abrams and Lloyd,(7) algorithms for timeevolving fermionic systems have improved subs”
Hamiltonian Simulation by Qubitization (2016, methodology): “Similar to previous approaches [6, 7], we approximate e−iλt with the JacobiAnger expansion e cos (z)t = ∑∞ k=−∞ i Jk(t)e [38], where Jk(t) are Bessel function of the first kind.”
Grand Unification of Quantum Algorithms (2021, methodology): “As in [16], we can fix this by rescaling the polynomials by a factor of 1 1+ , at the expense of an increase the error of these approximations to 2 .”
Methodology of Resonant Equiangular Composite Quantum Gates (2016, background): “Indeed, this relationship has already proven fruitful in surprising directions, such as recent work furnishing optimal algorithms for important problems such as Hamiltonian simulation [53, 54] on a quantum computer.”
Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity (2018, methodology): “Modern Hamiltonian simulation methods such as the signal processing algorithm [24] and qubitization [25] have achieved the provably optimal scaling that is possible for g ð ϵ Þ within a query model that aims to synthesize e − iH τ : The definition of λ depends on the query model; e.g., in models…”
Toward the first quantum simulation with quantum speedup (2017, methodology): “The QSP algorithm of Low and Chuang (16, 17) effectively implements a linear combination of unitary operators by a different mechanism.”
Low-Depth Quantum Simulation of Materials (2017, background): “Since then, several papers have introduced other “post-Trotter” methods with improved dependence on ε [86,87].”