The simulation of quantum systems is believed to be one of the main applications of quantum computers [1]. The work of Lloyd [2] was the first to propose how the time-evolution of a quantum system can be simulated by a sequence of quantum gates implementable on a universal quantum computer. The main idea behind this gate decomposition is the Lie-Trotter formula [3]: for a Hamiltonian given by a sum of local terms $H=\sum h_i$ the time-evolution for a time segment $s$ can be approximated as
$$\prod_{j=1}^L e^{-i h_j s}\approx e^{-i H s} +O(s^2).$$
To simulate the system for time $T=r s$ one can apply the previous approximation $r$ times ($r$ Trotter steps), while making sure that the time segment $s$ is short enough to keep the total error bounded. Furthermore, several standard ways exist to implement each term $e^{-i h_j s}$ on a quantum computer, depending on the the quantum system at hand.

Since the work of Lloyd, several methods were proposed that reach better asymptotic performance over the Lie-Trotter formula. Prominent examples are higher order Trotter-Suzuki formulas that approximate the time-evolution operator for time segment $s$ by more complicated product of terms of the form $e^{-i h_j \tau}$, where $\tau$ is some fraction of $s$ [4,5]. Recently, new methods have been developed that do not rely on such product formulas and are sometimes referred to as “post-Trotter” methods [6,7,8,9]. These methods achieve exponentially better scaling in error and are essentially optimal in certain query models.

Importantly, better asymptotic performances do not always mean a better performance for a particular quantum simulation problem with a fixed target error. Indeed, a better analysis of the error bounds of Trotter errors [10,11] shows that approaches based on product formulas can remain competitive or better in practice, due to smaller constant overheads and no need for ancillary space. For this reason new ideas to improve Trotterisation methods, while keeping its main advantages, can be of great importance, specially in this early stage of quantum computing where the number of qubits and gates is highly limited.

Recently, it was shown that stochastic approaches to Trotterisation can lead to a significant saving of resources. One approach is based on randomizing the order of application of the terms $e^{-i h_j s}$ [12]. In its simplest case, one could choose with probability 1/2 whether to apply them in forward order $(1,…,L)$ or in reverse order $(L,…,1)$, an approach referred to as randomized first order Trotterisation scheme.

Another protocol, named qDRIFT [13], stochastically sparsifies the system Hamiltonian by randomly picking which of the $h_j$ terms are kept according to their importance. Specifically, in each of the $r$ Trotter steps, each term $e^{-i h_j s}$ is chosen with a probability proportional to the strength of $h_j$. Crucially, the cost of implementing this approach scales independently of the number of terms in the Hamiltonian — instead, it scales with the sum of the strength of the individual terms. This can lead to a large reduction in the number of gates if the Hamiltonian contains many relatively weak terms as can happen, for example, in quantum chemistry problems. However, this approach scales worse in terms of time and error and hence can lose out to standard or randomized-order Trotterisation methods for large evolution times or very small errors.

The question that Ouyang, White and Campbell answer in their work [14] is how to combine the advantages of qDRIFT with those of randomised Trotterisation. The authors propose a new algorithm named SparSto that interpolates between these two approaches in the following way: firstly, choose a number $a$ of the strongest terms of the Hamiltonian with probability 1, referred to as the active set, and pick the rest of the weaker terms proportionally to their strength similarly to the qDRIFT protocol; secondly, after stochastically choosing which terms to keep, apply them according to the randomised 1st order Trotter scheme. Clearly, if all terms are kept with probability one i.e., $a=L$, the approach becomes the randomised first order Trotterisation scheme. On the other hand, if no term is kept with certainty ($a=0$), the approach reduces to qDRIFT.

In my view, the main strength of the work of Ouyang et al. is that they derive an explicit upper bound for the error of their approach, depending on the probability distribution chosen for sparsifying the Hamiltonian. In addition, based on convex optimization arguments, the authors show that the distribution that minimizes their error bound can be obtained by exhaustive search over only two parameters: the average number of gates per Trotter step and the size $a$ of the active set. For a given quantum simulation problem and a fixed gate budget, one can search among these parameters the ones that would lead to the smallest simulation error. Hence, this leads to a quantum simulation method that is guaranteed to have better performance than both qDRIFT and randomised first order Trotterisation.

To quantify the performance of their approach, the authors estimate the number of gates required as a function of the desired error for three particular quantum simulation problems involving three different molecules (carbon dioxide, ethane and propane). For low gate budgets they recover a performance similar to qDRIFT and for large gate budgets similar to randomised first order Trotter. It is for intermediate gate budgets that their new simulation algorithm shows a considerable advantage with respect to those two methods, improving the simulation error up to approximately one order of magnitude. Furthermore, in their examples, 2nd order product formulas seem to perform considerably worse than all the previously referred simulation methods due to larger constant factors (at least at the level of the known error upper bounds). Nevertheless, the random sparsification ideas can, in principle, easily be combined with higher order product formulas and lead to advantages for other quantum simulation problems. Whether analytical error bounds can be obtained in that case is an open problem.

It would be interesting if future work compares quantum simulation approaches based on product formulas with randomly sparsified Hamiltonians to post-Trotter methods, extending the work of Childs et al. [10]. Furthermore, as pointed out by Berry [15] and Ouyang et al. it would be interesting to investigate whether random sparsification ideas can improve post-Trotter simulation methods. At this early stage of quantum computers, all the theoretical help that leads to saving of quantum resources is needed in the path to achieve the first quantum simulation with quantum speed-up.

► 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.