Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition

Abstract

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 novel perspective for generating a low-depth Trotter-Suzuki decomposition assuming the standard 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. Though 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 the method scalable for problems of real interest.

arXiv comment22 pages, 8 Figures; Updated to revtex format. Added appendices

References in corpus (26)

• Many-Body Physics with Ultracold Gases
• Elementary gates for quantum computation
• Quantum computational chemistry
• Improved Simulation of Stabilizer Circuits
• Quantum Error Correction for Quantum Memories
• Fermionic quantum computation
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• ProjectQ: An Open Source Software Framework for Quantum Computing
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• Solving strongly correlated electron models on a quantum computer
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Low rank representations for quantum simulation of electronic structure
• ScaffCC: Scalable Compilation and Analysis of Quantum Programs
• Exploiting locality in quantum computation for quantum chemistry
• Digital quantum simulation of molecular vibrations
• Hardware Efficient Quantum Algorithms for Vibrational Structure Calculations
• Quantum algorithm for calculating molecular vibronic spectra
• How will quantum computers provide an industrially relevant computational advantage in quantum chemistry?
• Near- and long-term quantum algorithmic approaches for vibrational spectroscopy
• Optimising Clifford Circuits with Quantomatic
• On Clifford groups in quantum computing
• Introduction to Coding Quantum Algorithms: A Tutorial Series Using Pyquil

Cited by in corpus (4)

• Biology and medicine in the landscape of quantum advantages
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation