Fast-Forwardable Quantum Evolution and Where to Find Them

This is a Perspective on "Fast-forwarding quantum evolution" by Shouzhen Gu, Rolando D. Somma, and Burak Şahinoğlu, published in Quantum 5, 577 (2021).

By Yuan Su (Google Quantum AI, Venice, CA 90291, USA).

Simulating the time evolution of a quantum system is one of the major applications of quantum computers. The apparent intractability of this problem on a classical computer has led Feynman [1] and others to propose the idea of quantum computation. Since then, many quantum algorithms have been developed for both general-purpose Hamiltonian simulation as well as simulations of specific quantum models, including those arising in condensed-matter physics, quantum chemistry, and quantum field theory. Various algorithmic techniques and constructions, originally introduced for Hamiltonian simulation, have subsequently found applications in designing other quantum algorithms [2,3,4]. Simply put, an efficient solution of the Hamiltonian simulation problem would have implications both academically and industrially.

Within the quantum circuit model, the problem of Hamiltonian simulation aims to construct an approximation of the time-evolution operator $e^{-itH}$ using a sequence of elementary quantum gates, and the complexity of simulation is usually quantified by the number of gates appearing in the circuit. This complexity may depend on various input parameters, such as the accuracy of simulation $\epsilon$, certain norms of the Hamiltonian $\|H\|$, evolution time $t$, and additional parameters of the target system (such as the locality $k$ of a local Hamiltonian and the sparsity $d$ of a sparse Hamiltonian). The work of Gu, Somma, and Şahinoğlu focuses particularly on the scaling with evolution time $t$ [5]. Roughly speaking, they identified several scenarios where the scaling with $t$ can be reduced to be sublinear (or equivalently, the evolution can be fast-forwarded), and developed multiple approaches through which such fast-forwarding can be realized.

Note that it is not possible to simulate all quantum systems faster than they evolve. This claim can be rigorously justified for Hamiltonians provided by a black-box unitary [6], for geometrically local Hamiltonians [7], and for $2$-sparse row-computable Hamiltonians [8]. Nevertheless, when restricted to specific classes of Hamiltonians, fast-forwarding may be achieved. One simple example is the class of diagonal Hamiltonians with efficiently computable diagonal elements. In such a case, Hamiltonian simulation can be accomplished by simply introducing the correct phase for each basis state. Gu, Somma, and Şahinoğlu identified new classes of fast-forwardable Hamiltonians which were unknown from previous work, including the class of permutation-invariant Hamiltonians which can be block diagonalized by the quantum Schur transform, and certain classes of positive semidefinite local spin systems [9] whose spectral gaps can be amplified. The authors also considered fermionic and bosonic systems with Hamiltonians quadratic in the mode operators for which fast-forwarding results were previously known, but their formulation in a Lie-algebraic setting provided new insights. These results were obtained using a new definition of fast-forwarding based on the model of quantum computation, the target Hamiltonian, and properties of the initial states. This definition allows for polynomial improvements of the gate complexity and is arguably more flexible than the previous one from Atia and Aharonov’s work [8].

Sometimes only part of the Hamiltonian can be fast-forwarded but the full Hamiltonian cannot. In such a case, the result of Gu, Somma, and Şahinoğlu would still apply to the fast-forwardable part of the system. This is useful for implementing the quantum simulation algorithm based on Trotter-type product formulas [10], as well as other algorithms based on more advanced techniques [11,12,13,14,15,16,17].

Gu, Somma, and Şahinoğlu’s work was complemented by several other recent works that also explored the phenomenon of fast-forwarding quantum evolution [18,19]. Going forward, it would be interesting to identify further examples of fast-forwardable systems, to study implementation issues on a near-term quantum device [20], and to find other implications within quantum computing and beyond.

► BibTeX data

► References

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

[2] Andrew M. Childs, Lecture notes on quantum algorithms, URL: https:/​/​www.cs.umd.edu/​ amchilds/​qa/​ (2021).
https:/​/​www.cs.umd.edu/​~amchilds/​qa/​

[3] Ronald de Wolf, Quantum computing: Lecture notes, arXiv:1907.09415 [quant-ph] (2021).
arXiv:1907.09415

[4] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang, A grand unification of quantum algorithms, arXiv:2105.02859 [quant-ph] (2021).
arXiv:2105.02859

[5] Shouzhen Gu, Rolando D. Somma, and Burak Şahinoğlu, Fast-forwarding quantum evolution, Quantum 5, 577 (2021), arXiv:2105.07304.
https:/​/​doi.org/​10.22331/​q-2021-11-15-577
arXiv:2105.07304

[6] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians, Communications in Mathematical Physics 270, 359 (2007), arXiv:quant-ph/​0508139.
https:/​/​doi.org/​10.1007/​s00220-006-0150-x
arXiv:quant-ph/0508139

[7] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low, Quantum algorithm for simulating real time evolution of lattice Hamiltonians, in Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (2018) pp. 350–360, arXiv:1801.03922.
https:/​/​doi.org/​10.1109/​FOCS.2018.00041
arXiv:1801.03922

[8] Yosi Atia and Dorit Aharonov, Fast-forwarding of Hamiltonians and exponentially precise measurements, Nature Communications 8, 1572 (2017), arXiv:1610.09619.
https:/​/​doi.org/​10.1038/​s41467-017-01637-7
arXiv:1610.09619

[9] Burak Şahinoğlu and Rolando D. Somma, Hamiltonian simulation in the low-energy subspace, npj Quantum Information 7, 119 (2021), arXiv:2006.02660.
https:/​/​doi.org/​10.1038/​s41534-021-00451-w
arXiv:2006.02660

[10] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, Nearly tight Trotterization of interacting electrons, Quantum 5, 495 (2021), arXiv:2012.09194.
https:/​/​doi.org/​10.22331/​q-2021-07-05-495
arXiv:2012.09194

[11] Rolando D. Somma, Quantum simulations of one dimensional quantum systems, arXiv:1503.06319 [quant-ph] (2015).
arXiv:1503.06319

[12] Guang Hao Low and Nathan Wiebe, Hamiltonian simulation in the interaction picture, arXiv:1805.00675 [quant-ph] (2018).
arXiv:1805.00675

[13] Ryan Babbush, Dominic W. Berry, Jarrod R. McClean, and Hartmut Neven, Quantum simulation of chemistry with sublinear scaling in basis size, npj Quantum Information 5, 92 (2019), arXiv:1807.09802.
https:/​/​doi.org/​10.1038/​s41534-019-0199-y
arXiv:1807.09802

[14] Yi-Hsiang Chen, Amir Kalev, and Itay Hen, Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion, PRX Quantum 2, 030342 (2021), arXiv:2103.15334.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.030342
arXiv:2103.15334

[15] Yu Tong, Victor V. Albert, Jarrod R. McClean, John Preskill, and Yuan Su, Provably accurate simulation of gauge theories and bosonic systems, arXiv:2110.06942 [quant-ph] (2021).
arXiv:2110.06942

[16] Dong An, Di Fang, and Lin Lin, Time-dependent Hamiltonian simulation of highly oscillatory dynamics, arXiv:2111.03103 [quant-ph] (2021).
arXiv:2111.03103

[17] Abhishek Rajput, Alessandro Roggero, and Nathan Wiebe, Hybridized methods for quantum simulation in the interaction picture, arXiv:2109.03308 [quant-ph] (2021).
arXiv:2109.03308

[18] Efekan Kökcü, Thomas Steckmann, J. K. Freericks, Eugene F. Dumitrescu, and Alexander F. Kemper, Fixed depth Hamiltonian simulation via Cartan decomposition, arXiv:2104.00728 [quant-ph] (2021a).
arXiv:2104.00728

[19] Efekan Kökcü, Daan Camps, Lindsay Bassman, James K. Freericks, Wibe A. de Jong, Roel Van Beeumen, and Alexander F. Kemper, Algebraic compression of quantum circuits for Hamiltonian evolution, arXiv:2108.03282 [quant-ph] (2021b).
arXiv:2108.03282

[20] Cristina Cı̂rstoiu, Zoë Holmes, Joseph Iosue, Lukasz Cincio, Patrick J. Coles, and Andrew Sornborger, Variational fast forwarding for quantum simulation beyond the coherence time, npj Quantum Information 6, 82 (2020), arXiv:1910.04292.
https:/​/​doi.org/​10.1038/​s41534-020-00302-0
arXiv:1910.04292

Cited by

[1] Yulong Dong, Lin Lin, and Yu Tong, "Ground-State Preparation and Energy Estimation on Early Fault-Tolerant Quantum Computers via Quantum Eigenvalue Transformation of Unitary Matrices", PRX Quantum 3 4, 040305 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2022-12-08 10:12:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2022-12-08 10:12:52).