The dynamics of a quantum system can be simulated using a quantum computer by breaking down the unitary into a quantum circuit of one and two qubit gates. The most established methods are the Trotter-Suzuki decompositions, for which rigorous bounds on the circuit size depend on the number of terms L in the system Hamiltonian and the size of the largest term in the Hamiltonian Λ. Consequently, the Trotter-Suzuki method is only practical for sparse Hamiltonians. Trotter-Suzuki is a deterministic compiler but it was recently shown that randomized compiling offers lower overheads. Here we present and analyze a randomized compiler for Hamiltonian simulation where gate probabilities are proportional to the strength of a corresponding term in the Hamiltonian. This approach requires a circuit size independent of L and Λ, but instead depending on λ the absolute sum of Hamiltonian strengths (the ℓ_{1} norm). Therefore, it is especially suited to electronic structure Hamiltonians relevant to quantum chemistry. Considering propane, carbon dioxide, and ethane, we observe speed-ups compared to standard Trotter-Suzuki of between 306× and 1591× for physically significant simulation times at precision 10^{-3}. Performing phase estimation at chemical accuracy, we report that the savings are similar.
The dynamics of a quantum system can be simulated using a quantum computer by breaking down the unitary into a quantum circuit of one and two qubit gates. The most established methods are the Trotter-Suzuki decompositions, for which rigorous bounds on the circuit size depend on the number of terms L in the system Hamiltonian and the size of the largest term in the Hamiltonian Λ. Consequently, the Trotter-Suzuki method is only practical for sparse Hamiltonians. Trotter-Suzuki is a deterministic compiler but it was recently shown that randomized compiling offers lower overheads. Here we present and analyze a randomized compiler for Hamiltonian simulation where gate probabilities are proportional to the strength of a corresponding term in the Hamiltonian. This approach requires a circuit size independent of L and Λ, but instead depending on λ the absolute sum of Hamiltonian strengths (the ℓ_{1} norm). Therefore, it is especially suited to electronic structure Hamiltonians relevant to quantum chemistry. Considering propane, carbon dioxide, and ethane, we observe speed-ups compared to standard Trotter-Suzuki of between 306× and 1591× for physically significant simulation times at precision 10^{-3}. Performing phase estimation at chemical accuracy, we report that the savings are similar.
Randomized compilation protocols have recently attracted attention as alternatives to traditional deterministic Trotter-Suzuki methods, potentially reducing circuit depth and resource overhead. These protocols determine gate-application probabilities based on the strengths of Hamiltonian terms, as measured by the Schatten-$\ensuremath{\infty}$ norm. However, relying solely on the Schatten-$\ensuremath{\infty}$ norm to define sampling distributions may not be optimal, especially for continuous-variable and hybrid-variable systems involving unbounded operators, where quantifying Hamiltonian strengths is challenging. In this work, we propose an adaptive randomized compilation algorithm that dynamically updates sampling weights via low-order moment measurements of Hamiltonian terms, assigning higher probabilities to terms with greater uncertainty. This approach improves accuracy without significantly increasing gate counts and extends randomized compilation to continuous-variable and hybrid-variable systems by addressing the difficulties in characterizing the strengths of unbounded Hamiltonian terms. Numerical simulations demonstrate the effectiveness of our method.
Simulation of quantum chemistry is expected to be a principal application of quantum computing. In quantum simulation, a complicated Hamiltonian describing the dynamics of a quantum system is decomposed into its constituent terms, where the effect of each term during time-evolution is individually computed. For many physical systems, the Hamiltonian has a large number of terms, constraining the scalability of established simulation methods. To address this limitation we introduce a new scheme that approximates the actual Hamiltonian with a sparser Hamiltonian containing fewer terms. By stochastically sparsifying weaker Hamiltonian terms, we benefit from a quadratic suppression of errors relative to deterministic approaches. Relying on optimality conditions from convex optimisation theory, we derive an appropriate probability distribution for the weaker Hamiltonian terms, and compare its error bounds with other probability ansatzes for some electronic structure Hamiltonians. Tuning the sparsity of our approximate Hamiltonians allows our scheme to interpolate between two recent random compilers: qDRIFT and randomized first order Trotter. Our scheme is thus an algorithm that combines the strengths of randomised Trotterisation with the efficiency of qDRIFT, and for intermediate gate budgets, outperforms both of these prior methods.
Simulation of quantum chemistry is expected to be a principal application of quantum computing. In quantum simulation, a complicated Hamiltonian describing the dynamics of a quantum system is decomposed into its constituent terms, where the effect of each term during time-evolution is individually computed. For many physical systems, the Hamiltonian has a large number of terms, constraining the scalability of established simulation methods. To address this limitation we introduce a new scheme that approximates the actual Hamiltonian with a sparser Hamiltonian containing fewer terms. By stochastically sparsifying weaker Hamiltonian terms, we benefit from a quadratic suppression of errors relative to deterministic approaches. Relying on optimality conditions from convex optimisation theory, we derive an appropriate probability distribution for the weaker Hamiltonian terms, and compare its error bounds with other probability ansatzes for some electronic structure Hamiltonians. Tuning the sparsity of our approximate Hamiltonians allows our scheme to interpolate between two recent random compilers: qDRIFT and randomized first order Trotter. Our scheme is thus an algorithm that combines the strengths of randomised Trotterisation with the efficiency of qDRIFT, and for intermediate gate budgets, outperforms both of these prior methods.
Hamiltonian simulation is known to be one of the fundamental building blocks of a variety of quantum algorithms such as its most immediate application, that of simulating many-body systems to extract their physical properties. In this work, we present qSWIFT, a high-order randomized algorithm for Hamiltonian simulation. In qSWIFT, the required number of gates for a given precision is independent of the number of terms in the Hamiltonian, while the systematic error is exponentially reduced with regard to the order parameter. In this respect, our qSWIFT is a higher-order counterpart of the previously proposed quantum stochastic drift protocol (qDRIFT), the number of gates in which scales linearly with the inverse of the precision required. We construct the qSWIFT channel and establish a rigorous bound for the systematic error quantified by the diamond norm. qSWIFT provides an algorithm to estimate given physical quantities by using a system with one ancilla qubit, which is as simple as other product-formula-based approaches such as regular Trotter-Suzuki decompositions and qDRIFT. Our numerical experiment reveals that the required number of gates in qSWIFT is significantly reduced compared to qDRIFT. In particular, the advantage is significant for problems where high precision is required; e.g., to achieve a systematic relative propagation error of 10−6 , the required number of gates in third-order qSWIFT is 1000 times smaller than that of qDRIFT. Published by the American Physical Society 2024
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 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.
With quantum computers on the horizon, it is essential to understand what problems they can be used to solve. One potential application is simulating quantum systems, in particular, systems with many interacting electrons. However, there is a disparity between the computational resources required to study these problems and the capabilities of modern experimental quantum devices. In this thesis, we make progress toward closing this gap by reducing the cost of quantum simulation of quantum chemistry on a number of fronts. In the first half, we develop three improved quantum simulation algorithms by approximating time evolution under the Hamiltonian using a truncated Taylor series rather than the Trotter-Suzuki decomposition. We do this first for the molecular electronic structure Hamiltonian in two representations, obtaining asymptotic improvements in terms of both the number of orbitals and the required precision. We also apply the truncated Taylor series paradigm to quantum simulation in real space, where we consider simulation of general wave functions discretized on a uniform grid. In the second half, by working with Hamiltonians tailored specifically to quantum algorithms, we demonstrate that Trotter steps of the electronic structure Hamiltonian can be simulated in exactly N depth and with only linear connectivity, where N is the number of spin-orbitals. This resolves the problem of non-locality in fermion-to-qubit mappings, and has wide-ranging applications for variational and phase estimation-based quantum simulation of quantum chemistry. We further study this algorithm on an error-corrected quantum computer using the surface code. Benchmarking it alongside other product formula approaches, we show that quantum simulation of scientifically important instances of the electronic structure problem that are classically intractable can be performed with only a few hundred thousand physical qubits and fewer than one billion costly fault-tolerant gates. Finally, we study the effect of using randomized Hamiltonians in iterative phase estimation, and how this allows us to reduce the costs of simulation as well as to exploit knowledge of the ground state in how we design our simulation algorithm.