Framework for Hamiltonian simulation and beyond: standard-form encoding, qubitization, and quantum signal processing

This is a Perspective on "Hamiltonian Simulation by Qubitization" by Guang Hao Low and Isaac L. Chuang, published in Quantum 3, 163 (2019).

By Yuan Su (Department of Computer Science, Institute for Advanced Computer Studies and Joint Center for Quantum Information and Computer Science, University of Maryland).

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

[1] Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21 (6-7): 467-488, 1982. 10.1007/​BF02650179.
https:/​/​doi.org/​10.1007/​BF02650179

[2] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3: 163, July 2019. ISSN 2521-327X. 10.22331/​q-2019-07-12-163. URL https:/​/​doi.org/​10.22331/​q-2019-07-12-163.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[3] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters, 118: 010501, 2017. 10.1103/​PhysRevLett.118.010501.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501

[4] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 20-29, 2003.

[5] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters, 114 (9): 090502, 2015. 10.1103/​PhysRevLett.114.090502.
https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502

[6] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10 (9): 631, 2014. 10.1038/​nphys3029.
https:/​/​doi.org/​10.1038/​nphys3029

[7] Mario Szegedy. Quantum speed-up of markov chain based algorithms. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 32-41, Oct 2004. 10.1109/​FOCS.2004.53.
https:/​/​doi.org/​10.1109/​FOCS.2004.53

[8] Andrew M Childs. On the relationship between continuous-and discrete-time quantum walk. Communications in Mathematical Physics, 294 (2): 581-603, 2010. 10.1007/​s00220-009-0930-1.
https:/​/​doi.org/​10.1007/​s00220-009-0930-1

[9] Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14 (2): 122-152, June 2005. ISSN 1016-3328. 10.1007/​s00037-005-0194-x. URL http:/​/​dx.doi.org/​10.1007/​s00037-005-0194-x.
https:/​/​doi.org/​10.1007/​s00037-005-0194-x

[10] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. Methodology of resonant equiangular composite quantum gates. Physical Review X, 6: 041067, 2016. 10.1103/​PhysRevX.6.041067.
https:/​/​doi.org/​10.1103/​PhysRevX.6.041067

[11] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115 (38): 9456-9461, 2018. 10.1073/​pnas.1801723115.
https:/​/​doi.org/​10.1073/​pnas.1801723115

[12] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st ACM Symposium on Theory of Computing, pages 193-204, 2019. ISBN 978-1-4503-6705-9. 10.1145/​3313276.3316366. URL http:/​/​doi.acm.org/​10.1145/​3313276.3316366.
https:/​/​doi.org/​10.1145/​3313276.3316366

[13] Dominic W Berry, Mária Kieferová, Artur Scherer, Yuval R Sanders, Guang Hao Low, Nathan Wiebe, Craig Gidney, and Ryan Babbush. Improved techniques for preparing eigenstates of fermionic Hamiltonians. npj Quantum Information, 4 (1): 22, 2018. 10.1038/​s41534-018-0071-5.
https:/​/​doi.org/​10.1038/​s41534-018-0071-5

[14] David Poulin, Alexei Kitaev, Damian S Steiger, Matthew B Hastings, and Matthias Troyer. Quantum algorithm for spectral measurement with a lower gate count. Physical Review Letters, 121 (1): 010501, 2018. 10.1103/​PhysRevLett.121.010501.
https:/​/​doi.org/​10.1103/​PhysRevLett.121.010501

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2019-12-15 09:53:30). On SAO/NASA ADS no data on citing works was found (last attempt 2019-12-15 09:53:30).