Graph optimization perspective for low-depth Trotter-Suzuki decomposition

Hamiltonian simulation represents an important module in a large class of quantum algorithms and simulations such as quantum machine learning, quantum linear algebra methods, and modeling for physics, material science, and chemistry. One of the most prominent methods for realizing the time-evolution unitary is via the Trotter-Suzuki decomposition. However, there is a large class of possible decompositions for the infinitesimal time-evolution operator as the order in which the Hamiltonian terms are implemented is arbitrary. We introduce a perspective for generating a low-depth Trotter-Suzuki decomposition assuming the standard $\mathrm{Clifford}+$rz gate set by adapting ideas from quantum error correction. We map a given Trotter-Suzuki decomposition to a constrained path on a graph which we deem the Pauli frame graph (PFG). Each node of the PFG represents the set of possible Hamiltonian terms currently available to be applied, Clifford operations represent a move from one node to another, and so the graph distance represents the gate cost of implementing the decomposition. The problem of finding the optimal decomposition is then equivalent to solving a problem similar to the traveling salesman. Although this is an NP-hard problem, we demonstrate the simplest heuristic, greedy search, and compare the resulting two-qubit gate count and circuit depth to more standard methods for a large class of scientifically relevant Hamiltonians, both fermionic and bosonic, found in chemical, vibrational, and condensed-matter problems which naturally scale. We find, in nearly every case we study, the resulting depth and two-qubit gate counts are less than those provided by standard methods, by as much as an order of magnitude. We also find the method is efficient and amenable to parallelization, making it scalable for problems of real interest.

Figure 1

Circuit diagram for our simple example. Below the circuit represents the frame which provides the effective $Z$-rotation axis for each qubit.

Figure 2

Simple depiction of a closed path in the PFG which might be used to realize a unitary in the PoPR form. Gray arrows represent the path generated by standard methods of compute and uncompute, whereas the black arrows represent a more direct path connecting different Pauli frames.

Figure 3

Table of the nine 2qE gates.

Figure 4

Plots for the results of synthesizing an effective Trotter step for the Fermi-Hubbard model with the Jordan-Wigner (JW) and Bravyi-Kitaev (BK) fermionic encodings using the “standard” method (STD) and the method of this paper (PFG). The left plot is for number of TQE gates per term and the right plot is for circuit depth. In all cases, PFG outperforms STD.

Figure 5

Plots for the results of synthesizing an effective Trotter step for the polyacetylene model with the Jordan-Wigner (JW) and Bravyi-Kitaev (BK) fermionic encodings using the “standard” method (STD) and the method of this paper (PFG). The left plot is for number of TQE gates per term and the right plot is for circuit depth. In all cases, PFG outperforms STD.

Figure 6

Plots for the results of synthesizing an effective Trotter step for the Bose-Hubbard model with the Gray code (Gray) and standard (Std) bosonic encodings using the “standard” method (STD) and the method of this paper (PFG). The left two plots are for number of TQE gates per term and the right two plots are for circuit depth. The top two plots are for $d=4$ and bottom two plots are for $d=8$. In all cases, PFG outperforms STD.

Figure 7

Plots for the results of synthesizing an effective Trotter step for the vibronic model with the Gray code (Gray) and standard (Std) bosonic encodings using the “standard” method (STD) and the method of this paper (PFG). The insets show a zoomed-in section where both methods produce results. The left two plots are for number of TQE gates per term and the right two plots are for circuit depth. The top two plots are for $d=4$ and bottom two plots are for $d=8$. In nearly all cases, PFG outperforms STD.

Figure 8

Log-log plots of CPU time (wall-clock time times number of CPU processes used) as a function of number of qubits times number of Pauli Hamiltonian terms. Each plot is for the model with the Jordan-Wigner (JW) and Bravyi-Kitaev (BK) fermionic encodings or the Gray code (Gray) and standard (Std) bosonic encodings where applicable using the method of this paper (PFG). The linearity of these plots demonstrates the PFG method herein scales polynomially in the size of problem. The approximate slope of these lines can be found in Table 1. Each plot pertain is for a given model such that: top left is for Fermi-Hubbard, top right is for polyacetylene, left middle is for Bose-Hubbard with $d=4$, right middle is for Bose-Hubbard with $d=8$, bottom left is for vibronic with $d=4$ and bottom right is for vibronic with $d=8$.