Simulating the Hamiltonian dynamics of a quantum system is one of the most promising applications of quantum computers. Indeed, the idea of quantum computers, suggested by Feynman [1] and Manin, was strongly motivated by the problem of quantum simulation. Over the past two decades, many efficient quantum algorithms have been designed for simulating both general Hamiltonians and specific systems in condensed matter physics, quantum chemistry, and quantum field theory. These algorithms employ a variety of techniques to process Hamiltonians encoded in different ways, each with runtime that depends on a number of parameters, typically time, accuracy, and system size. Published in Quantum [2], Guang Hao Low and Isaac L. Chuang’s paper develops a framework that unifies a number of these Hamiltonian encodings and leads to a simulation algorithm with not only optimal query complexity (as established in their earlier work [3]) but also low ancilla overhead, a feature that is especially desirable for near-term realization.

Naturally, the cost of quantum simulation depends on how the input Hamiltonians are accessed by the quantum computers. Previous works typically consider two input models: (i) the sparse matrix model [4], well-motivated from a theoretical perspective, assumes that the Hamiltonians are sparse and access to the nonzero matrix elements are provided by oracles; and (ii) the linear-combination-of-unitaries model [5], favored for practical applications such as condensed matter physics and quantum chemistry, handles Hamiltonians that can be decomposed into linear combinations of unitaries. Low and Chuang propose a general input model they call “standard-form encoding”, which includes both above models as special cases. This generality has also motivated new query models of density-matrix simulation, offering better scaling than the sample-based model studied by Lloyd, Mohseni, and Rebentrost [6].

Now that the input Hamiltonians are encoded in standard form, we ask how they are related to the operations we can perform on digital quantum computers. This relation is made clear through “qubitization”, the central result by Low and Chuang [2]. Qubitization asserts that whenever the encoded Hamiltonian $H$ contains an eigenvalue $\lambda$, the operation that encodes $H$ contains a two-by-two block

$\begin{bmatrix}
\lambda & -\sqrt{1-\lambda^2}\\
-\sqrt{1-\lambda^2} & -\lambda
\end{bmatrix}$

or

$\begin{bmatrix}
\lambda & -\sqrt{1-\lambda^2}\\
\sqrt{1-\lambda^2} & \lambda
\end{bmatrix}$

on the diagonal, with respect to a basis determined jointly by the eigenstates of $H$ and the encoding. Different eigenvalues of $H$ associate with different two-by-two blocks; they behave as if they are single-qubit rotations or reflections—hence the name “qubitization”. This spectral relation builds on earlier results such as Szegedy quantum walk [7,8] and Marriott-Watrous QMA amplification [9], but Low and Chuang’s new formulation makes it more versatile for quantum simulation.

For a given Hamiltonian $H$ and evolution time $t$, the goal of quantum simulation is to implement $e^{-itH}$ using a quantum circuit comprised of elementary gates. When $H$ is qubitized, this can be realized by “quantum signal processing” [3,10]. Quantum signal processing allows one to apply polynomial functions to the entries of a single-qubit unitary operation. Combining with standard-form encoding and qubitization, this technique implements a transformation that approximates $\lambda\mapsto e^{-it\lambda}$ on each eigenstate of $H$ with eigenvalue $\lambda$, thus providing an approach to quantum simulation. The structure of the resulting circuit is simple and the ancilla overhead is low. Indeed, recent study shows that this algorithm is competitive against other quantum algorithms for an instance of classically infeasible, practically useful simulation [11].

The new framework of Low and Chuang enables function design of Hamiltonians, in many cases with optimal query complexity, of which Hamiltonian simulation is a particular example. After the original preprint release, the ideas of standard-form encoding, qubitization, and quantum signal processing have been successfully applied to areas beyond quantum simulation [12]. It will certainly be of interest to identify more applications of this framework [13,14], as well as to explore its performance in practice for near-term implementation of quantum simulation.

► BibTeX data

► References

Cited by

This View is published in Quantum Views under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.