Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition

Hamiltonian simulation represents an important module in many quantum algorithms such as quantum machine learning, quantum linear algebra, and design of materials and chemistry. The most prominent methods for realizing the time-evolution unitary is the Trotter-Suzuki approximation. However, there are many possible decompositions for the infinitesimal time-evolution operator as the order in which each term of the Hamiltonian is implemented is arbitrary. We discuss a novel perspective for generating a low-depth Trotter-Suzuki decomposition assuming the 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 Hamiltonian terms currently available to be applied, Clifford operations represent a move between nodes, and the graph distance of the path represents the gate cost of implementation. Finding the optimal decomposition is then equivalent to solving a problem similar to the traveling salesman. Though this is an NP-hard problem, we use this perspective to demonstrate the simplest heuristic, greedy search, and compare the resulting two-qubit gate count and circuit depth to more standard methods.