Quantum Algorithm for Time-Dependent Hamiltonian Simulation by Permutation Expansion

We present a quantum algorithm for the dynamical simulation of time-dependent Hamiltonians. Our method involves expanding the interaction-picture Hamiltonian as a sum of generalized permutations, which leads to an integral-free Dyson series of the time-evolution operator. Under this representation, we perform a quantum simulation for the time-evolution operator by means of the linear combination of unitaries technique. We optimize the time steps of the evolution based on the Hamiltonian’s dynamical characteristics, leading to a gate count that scales with an $L^1$-norm-like scaling with respect only to the norm of the interaction Hamiltonian, rather than that of the total Hamiltonian. We demonstrate that the cost of the algorithm is independent of the Hamiltonian’s frequencies, implying its advantage for systems with highly oscillating components, and for time-decaying systems the cost does not scale with the total evolution time asymptotically. In addition, our algorithm retains the near optimal $\log (1/ϵ)/\log \log (1/ϵ)$ scaling with simulation error $ϵ$.

Popular Summary

To understand how a quantum system evolves has been a central task ever since the development of quantum mechanics. It has far-reaching applications in physics, chemistry, material sciences, and beyond. Yet, simulating quantum dynamics on classical computers is formidable due to the exponentially large parameter space of a quantum many-body system. Quantum computers, on the other hand, provide a promising route to solving this problem. A majority of existing quantum simulation algorithms tackle systems with time-independent particle interactions. In this paper, we consider the most general quantum dynamics with time-dependent interactions. The noncommutativity between the interaction operators at different time steps adds another layer of complexity to the simulation problem. However, we show that our proposed algorithm does not add much additional cost comparing to the time-independent cases.

More specifically, we expand the time-dependent interaction Hamiltonian in terms of permutation operations and diagonal exponentials. Under this representation, we implement a circuit simulation framework that performs an operator written as a linear combination of unitaries. With careful analysis, we show that it has unique features and advantages, including the independence of frequencies in cost, a constant time scaling for time-decaying systems and a time-partition scheduling that dynamically adjusts the simulation length based on the instantaneous Hamiltonian norm. In addition, it retains the near optimal error scaling. Overall, this algorithm can simulate any quantum dynamics, with the most general Hamiltonian, without any exponential cost as opposed to classical simulation, and it also provides speedup over existing quantum algorithms for a large class of systems.

Figure 1

The actions of a sequence of generalized permutations. This figure gives a pictorial illustration on how the elements of the diagonal matrices are picked up when interleaving with permutations. In this example, we have $q=2$.