Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner.However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques.We develop methods to perform faster Trotter steps with complexity sublinear in the number of terms.We achieve this for a class of Hamiltonians whose interaction strength decays with distance according to power law.Our methods include one based on a recursive block encoding and one based on an average-cost simulation, overcoming the normalization-factor barrier of these advanced quantum simulation techniques.We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank.Combining with a tighter error analysis, we show that it suffices to use η 1/3 n 1/3 + n 2/3 /η 2/3 n 1+o(1) gates to simulate uniform electron gas with n spin orbitals and η electrons in second quantization in real space, asymptotically improving over the best previous work.We obtain an analogous result when the external potential of nuclei is introduced under the Born-Oppenheimer approximation.We prove a circuit lower bound when the Hamiltonian coefficients take a continuum range of values, showing that generic n-qubit two-local Hamiltonians with commuting terms require at least (n 2 ) gates to evolve with accuracy = (1/poly(n)) for time t = ( ).Our proof is based on a gateefficient reduction from the approximate synthesis of diagonal unitaries within the Hamming weight-2 subspace, which may be of independent interest.Our result thus suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter steps with lower gate complexity.
Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner.However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques.We develop methods to perform faster Trotter steps with complexity sublinear in the number of terms.We achieve this for a class of Hamiltonians whose interaction strength decays with distance according to power law.Our methods include one based on a recursive block encoding and one based on an average-cost simulation, overcoming the normalization-factor barrier of these advanced quantum simulation techniques.We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank.Combining with a tighter error analysis, we show that it suffices to use η 1/3 n 1/3 + n 2/3 /η 2/3 n 1+o(1) gates to simulate uniform electron gas with n spin orbitals and η electrons in second quantization in real space, asymptotically improving over the best previous work.We obtain an analogous result when the external potential of nuclei is introduced under the Born-Oppenheimer approximation.We prove a circuit lower bound when the Hamiltonian coefficients take a continuum range of values, showing that generic n-qubit two-local Hamiltonians with commuting terms require at least (n 2 ) gates to evolve with accuracy = (1/poly(n)) for time t = ( ).Our proof is based on a gateefficient reduction from the approximate synthesis of diagonal unitaries within the Hamming weight-2 subspace, which may be of independent interest.Our result thus suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter steps with lower gate complexity.
Abstract The quantum simulation of quantum chemistry is a promising application of quantum computers. However, for N molecular orbitals, the O(N4) O ( N 4 ) gate complexity of performing Hamiltonian and unitary Coupled Cluster Trotter steps makes simulation based on such primitives challenging. We substantially reduce the gate complexity of such primitives through a two-step low-rank factorization of the Hamiltonian and cluster operator, accompanied by truncation of small terms. Using truncations that incur errors below chemical accuracy allow one to perform Trotter steps of the arbitrary basis electronic structure Hamiltonian with O(N3) O ( N 3 ) gate complexity in small simulations, which reduces to O(N2) O ( N 2 ) gate complexity in the asymptotic regime; and unitary Coupled Cluster Trotter steps with O(N3) O ( N 3 ) gate complexity as a function of increasing basis size for a given molecule. In the case of the Hamiltonian Trotter step, these circuits have O(N2) O ( N 2 ) depth on a linearly connected array, an improvement over the O(N3) O ( N 3 ) scaling assuming no truncation. As a practical example, we show that a chemically accurate Hamiltonian Trotter step for a 50 qubit molecular simulation can be carried out in the molecular orbital basis with as few as 4000 layers of parallel nearest-neighbor two-qubit gates, consisting of fewer than 10 5 non-Clifford rotations. We also apply our algorithm to iron–sulfur clusters relevant for elucidating the mode of action of metalloenzymes.
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.
Trotter product formulas are a leading approach for Hamiltonian simulation on quantum computers, yet their practical performance has remained difficult to assess due to the challenge of accurately estimating the Trotter error. In this work, we develop new theoretical results, algorithms, and software tools that advance the state-of-the-art in Trotter error estimation by orders of magnitude in both scale and accuracy. On the theoretical side, we prove that in the asymptotic limit the error of a product formula depends on the diagonal elements of the Baker-Campbell-Hausdorff (BCH) error operator in the eigenbasis of the Hamiltonian, rather than its full spectral norm -- yielding an improved scaling for Hamiltonian simulation using product formulas. On the algorithmic side, we introduce a compact representation of the BCH expansion that reduces the number of commutators from O(n3) to O(n) for second-order, and from O(n5) to O(n2) for fourth-order formulas on n fragments, complemented by an importance sampling scheme to further reduce the computational cost. We provide implementations of these techniques in software and demonstrate their power on two applications: (i) X-ray absorption spectroscopy of an electronic Hamiltonian (Li4Mn2O) at up to 56 qubits using tensor networks; and (ii) vibronic dynamics of naphthalene at over 100 qubits using ML-MCTDH, where we find that naive analytical bounds overestimate the required number of Trotter steps by nearly five orders of magnitude. Our framework enables, for the first time, the accurate estimation of Trotter error at practically relevant system sizes, providing a foundation for fair algorithmic comparisons and rational design of product formulas.
Discretizing electronic degrees of freedom into atomic orbitals is the default choice to accurately model electrons in molecules in a compact and flexible way. We consider the task of simulating such electronic structure models on a quantum computer for N orbitals, keeping the number of orbitals per atom constant. Atomic orbitals give rise to Hamiltonians with potentially up to O(N4) terms and little structure, which made it challenging to match the complexity of methods based on plane waves and real-space grids. In this work, we show that a Trotter step for atomic orbitals can be implemented in depth O(polylog(N)) without ancillas by combining a rigorous treatment of orbital localization, a hierarchical Hamiltonian decomposition based on the Fast Multipole Method, and shallow quantum Fourier arithmetic circuits. By bounding the Trotter error, we obtain sublinear simulation depth, and our total gate count N5/3+o(1) matches the best scaling known for any basis.
We consider simulating quantum systems on digital quantum computers. We show that the performance of quantum simulation can be improved by simultaneously exploiting the commutativity of Hamiltonian, the sparsity of interactions, and the prior knowledge of initial state. We achieve this using Trotterization for a class of interacting electrons that encompasses various physical systems, including the plane-wave-basis electronic structure and the Fermi-Hubbard model. We estimate the simulation error by taking the transition amplitude of nested commutators of Hamiltonian terms within the η-electron manifold. We develop multiple techniques for bounding the transition amplitude and expectation of general fermionic operators, which may be of independent interest. We show that it suffices to use O(n^(5/3)/η^(2/3)+n^(4/3)η^(2/3)) gates to simulate electronic structure in the plane-wave basis with n spin orbitals and η electrons up to a negligible factor, improving the best previous result in second quantization while outperforming the first-quantized simulation when n=O(η²). We also obtain an improvement for simulating the Fermi-Hubbard model. We construct concrete examples for which our bounds are almost saturated, giving a nearly tight Trotterization of interacting electrons.
We consider simulating quantum systems on digital quantum computers. We show that the performance of quantum simulation can be improved by simultaneously exploiting commutativity of the target Hamiltonian, sparsity of interactions, and prior knowledge of the initial state. We achieve this using Trotterization for a class of interacting electrons that encompasses various physical systems, including the plane-wave-basis electronic structure and the Fermi-Hubbard model. We estimate the simulation error by taking the transition amplitude of nested commutators of the Hamiltonian terms within the η -electron manifold. We develop multiple techniques for bounding the transition amplitude and expectation of general fermionic operators, which may be of independent interest. We show that it suffices to use (n5/3η2/3+n4/3η2/3)no(1) gates to simulate electronic structure in the plane-wave basis with n spin orbitals and η electrons, improving the best previous result in second quantization up to a negligible factor while outperforming the first-quantized simulation when n=η2−o(1) . We also obtain an improvement for simulating the Fermi-Hubbard model. We construct concrete examples for which our bounds are almost saturated, giving a nearly tight Trotterization of interacting electrons.