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

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.