In this paper we provide a framework for combining multiple quantum simulation methods, such as Trotter-Suzuki formulas and QDrift into a single Composite channel that builds upon older coalescing ideas for reducing gate counts. The central idea behind our approach is to use a partitioning scheme that allocates a Hamiltonian term to the Trotter or QDrift part of a channel within the simulation. This allows us to simulate small but numerous terms using QDrift while simulating the larger terms using a high-order Trotter-Suzuki formula. We prove rigorous bounds on the diamond distance between the Composite channel and the ideal simulation channel and show under what conditions the cost of implementing the Composite channel is asymptotically upper bounded by the methods that comprise it for both probabilistic partitioning of terms and deterministic partitioning. Finally, we discuss strategies for determining partitioning schemes as well as methods for incorporating different simulation methods within the same framework.
In this paper we provide a framework for combining multiple quantum simulation methods, such as Trotter-Suzuki formulas and QDrift into a single Composite channel that builds upon older coalescing ideas for reducing gate counts. The central idea behind our approach is to use a partitioning scheme that allocates a Hamiltonian term to the Trotter or QDrift part of a channel within the simulation. This allows us to simulate small but numerous terms using QDrift while simulating the larger terms using a high-order Trotter-Suzuki formula. We prove rigorous bounds on the diamond distance between the Composite channel and the ideal simulation channel and show under what conditions the cost of implementing the Composite channel is asymptotically upper bounded by the methods that comprise it for both probabilistic partitioning of terms and deterministic partitioning. Finally, we discuss strategies for determining partitioning schemes as well as methods for incorporating different simulation methods within the same framework.
Recent work has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian H for a given simulation problem into subsets A and B such that H=A+B, where the terms in A are simulated with a Trotter-Suzuki channel and the B terms are randomly sampled via the QDrift algorithm. Here we show that this approach holds in imaginary time, making it a candidate classical algorithm for quantum Monte-Carlo calculations. We upper-bound the induced Schatten-1→1 norm on both imaginary-time QDrift and Composite channels. Another recent result demonstrated that simulations of Hamiltonians containing geometrically-local interactions for systems defined on finite lattices can be improved by decomposing H into subsets that contain only terms supported on that subset of the lattice using a Lieb-Robinson argument. Here, we provide a quantum algorithm by unifying this result with the composite approach into ``local composite channels" and we upper bound the diamond distance. We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form e−iHjt and e−Hjβ to meet a certain error tolerance ε. We show constant factor advantages for a variety of interesting Hamiltonians, the maximum of which is a ≈20 fold speedup that occurs for a simulation of Jellium.
For Hamiltonian H=∑jhj, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms ∥hj∥, time t, and trace-distance error ε. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case ∥hj∥ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in 1/ε, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
Recent study has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian H for a given simulation problem into subsets A and B such that H=A+B , where the terms in A are simulated with a Trotter-Suzuki channel and the B terms are randomly sampled via the Qdrift algorithm. Here we extend Qdrift and composite product formulas to imaginary time, formulating candidate classical algorithms for quantum Monte Carlo calculations. We upper bound the induced Schatten- 1→1 norm on both imaginary-time Qdrift and composite channels. Another recent result demonstrated that simulations of lattice Hamiltonians containing geometrically local interactions can be improved using a Lieb-Robinson argument to decompose H into subsets that contain only terms supported on that subset of the lattice. Here, we provide a quantum algorithm by unifying this result with the composite approach into “local composite channels” and we upper bound the diamond distance. We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form e−iHjt and e−Hjβ to meet a certain error tolerance ε . In doing so, we optimize the partitioning into sets A and B using gradient boosted tree models from machine learning. These numerical studies are important given that product formulas have been historically known to outperform analytic upper bounds. We show constant factor advantages for a variety of interesting Hamiltonians, the maximum of which is a ≈20 -fold speedup that occurs in the simulation of Jellium. Published by the American Physical Society 2024
When simulating the dynamics of open quantum systems with quantum computers, it is essential to accurately approximate the system's behaviour while preserving the physicality of its evolution. Traditionally, for Markovian open quantum systems, this has been achieved using first and second-order Trotter-Suzuki product formulas or probabilistic algorithms. In this work, we introduce novel non-probabilistic algorithms for simulating Markovian open quantum systems using randomisation. Our methods, including first and second-order randomised Trotter-Suzuki formulas and the QDRIFT channel, not only maintain the physicality of the system's evolution but also enhance the scalability and precision of quantum simulations. We derive error bounds and step count limits for these techniques, bypassing the need for the mixing lemma typically employed in Hamiltonian simulation proofs. Furthermore, we implement these randomised algorithms using Classical Sampling (CS), demonstrating their gate complexity advantages over deterministic TS product formulas. This work systematically extends powerful randomisation techniques from Hamiltonian simulation to the general setting of Markovian open quantum systems, highlighting their potential to enable faster and more accurate simulations.
Randomized product formulas such as qDrift offer a resource-efficient alternative to deterministic Trotter--Suzuki decompositions for Hamiltonian simulation, removing their polynomial dependence on the number of Hamiltonian terms. qDrift, however, is intrinsically limited to first order in the evolution time, so its query complexity remains linear in the inverse of the target accuracy, 1/ε. We introduce Pathwise Random Hamiltonian Simulation (PRHS), which extends qDrift to arbitrary order by subdividing each time step into M correlated slices, each evolving under a term sampled from a quasi-probability distribution that we construct in closed form and prove unique, with a bias decaying factorially in M. Optimizing jointly over the number of slices M and the number of independent blocks N interpolates between the standard qDrift protocol at long times and a high-precision regime where the query cost grows slower than any power of 1/ε, without requiring ancillary qubits. Numerical simulations of five molecular Hamiltonians confirm this advantage, with PRHS achieving accuracies two to four orders of magnitude beyond qDrift at equal query cost.
Abstract Quantum computers can be used to simulate the evolution of quantum systems via the discretization of this evolution into unitary gate sequences. While Trotter-Suzuki (TS) methods stand as the most prevalent approach for quantum simulation, their effectiveness is contingent upon the sparsity of the Hamiltonian system. This is due to the precision and gate complexity of the TS method being dependent on the number of terms within the Hamiltonian. Despite attempts to mitigate this dependence through the random permutation of terms within TS methods, scalability issues persist. To address this, Campbell introduced the qDRIFT algorithm, leveraging random compilation to alleviate the reliance on the Hamiltonian’s term count. However, the initial implementation of this algorithm necessitated the involvement of classical computing resources for gate set compilation. Our study presents two novel quantum circuit implementations of the qDRIFT algorithm, eliminating the need for classical computing resources. We employ the Linear Combination of Unitaries (LCU) approach and the Quantum Forking (QF) procedure to construct efficient circuits to implement the qDRIFT algorithm. Furthermore, we conduct a comparative analysis of the gate complexities between our proposed circuits and TS methods, identifying the scenarios in which our circuits exhibit superior performance.