Efficient quantum algorithms for simulating sparse Hamiltonians

I. INTRODUCTION

• Higher-order Suzuki integrators reduce temporal scaling from t^3/2 or t^2 to t^(1+1/2k), where k can be arbitrarily large.The order k controls how close the scaling approaches linear behavior.Source: §I · p. 1
• A new Hamiltonian decomposition reduces the scaling in n from n^2 or n^9 to log^*n for n-qubit systems.The method is similar to deterministic coin tossing and Linial’s graph-coloring method.Source: §I · p. 1
• The paper determines an upper bound on the required exponentials, enabling estimation of an optimal integrator order and k-independent temporal scaling.Source: §I · p. 1

General problem

• The exponential-decomposition problem seeks to approximate e^-iHt with a sequence of e^-iHjt′ while bounding final-state trace-distance error by ǫ.The number of exponentials Nexp is the relevant complexity measure when each H_j can be efficiently simulated for arbitrary t′.Source: §II · p. 1
• For Problem 1, Theorem 1 bounds Nexp for arbitrary positive integer k and τ = ∥H∥t, with scaling that can approach linear in τ as k increases.Taking k too large can nevertheless increase Nexp for fixed τ, so the order must be optimized.Source: §II · pp. 1–2
• Optimizing the integrator order yields an Nexp expression independent of k, with scaling close to linear for large mτ.The integer-valued optimum is obtained by adding 1 and rounding the minimizing value of k.Source: §II · p. 2

Sparse Hamiltonians

• The sparse-Hamiltonian problem assumes at most d nonzero entries per column, a black-box function f for retrieving them, dimension at most 2^n, and trace-distance error at most ǫ.The target complexity is the number Nbb of calls to f required to simulate e^-iHt.Source: §II · p. 2
• The sparse algorithm decomposes H into H_j and constructs corresponding black-box access, extending the approach of ATS to obtain a theorem for the number of black-box calls.The decomposition includes the tensor-product setting and cases where nonzero column entries can be calculated, but computing it requires additional algorithmic steps.Source: §II · pp. 1–2
• The resulting log^*n dependence improves on the n^9 scaling implicit in ATS and the n^2 scaling of Childs.In the black-box setting, the near-linear temporal scaling is effectively optimal because general simulations cannot be sublinear in τ.Source: §II · p. 2

III. HIGHER ORDER INTEGRATORS

• Higher-order integrators achieve temporal scaling arbitrarily close to linear by increasing the integrator order k.The integrator order may be chosen as a positive integer, although excessively large k can increase the number of exponentials for fixed time.Source: §III · pp. 2–3
• The Taylor-expansion analysis bounds the higher-order product-formula error using cancellations through order 2k and products of noncommuting Hamiltonian terms.The expansion contains terms involving powers of the number m of Hamiltonian components, while the operator norms are bounded through Λ = ∥H∥.Source: §III · p. 3
• The construction controls trace-distance error by first bounding the difference between the implemented and target unitaries.Under the stated restrictions, the resulting simulation error does not exceed ǫ.Source: §III · p. 4
• The number of exponentials satisfies Nexp ≤ 2m5k−1r, with r chosen from the accuracy-dependent interval bound.The resulting order scaling is obtained after accounting for the ceiling function in r.Source: §III · p. 4
• The framework applies to tensor-product interaction Hamiltonians and sparse Hamiltonians, provided the Hamiltonian is decomposed into efficiently simulable terms.For sparse Hamiltonians, the additional task is decomposing the Hamiltonian into a sum of terms.Source: §III · p. 4

IV. LINEAR LIMIT ON SIMULATION TIME

• A row-computable 2-sparse Hamiltonian at scaled time τ = πN/2 requires at least τ/2π queries to achieve trace-distance precision 1/4.This establishes a linear lower bound on simulation queries for every positive integer N.Source: §IV · pp. 4–5
• The constructed Hamiltonian simulates parity computation: evolution from |0, 0⟩ to |kN, N⟩ makes the ancilla encode the parity of N input bits.The graph contains two disconnected state sets, with the solid-line path determined by the input-bit-dependent sequence k0, …, kN.Source: §IV · p. 5
• Simulations making no more than N/2 queries to the Xj incur trace-distance error at least 1/4; since each H-column query uses at most two Xj queries, N/4 H queries suffice for this implication.Source: §IV · p. 5
• The lower bound also rules out a general integrator for H = H1 + H2 using fewer than τ/2π exponentials at error 1/4.The decomposition uses two 1-sparse Hamiltonians, each efficiently simulable with only two queries.Source: §IV · p. 5
• The near-linear lower bound applies in the black-box setting and does not exclude faster simulation for individual Hamiltonians with additional structure.The limitation concerns general simulations whose cost is specified through oracle queries or exponentials.Source: §IV · p. 5

• The decomposition writes H as a sum of 1-sparse Hamiltonians, each simulable directly with two black-box queries.The number of components m therefore directly affects the total simulation cost.Source: §V · p. 6
• m = 6d^2 colors suffice, and each query to a decomposed Hamiltonian can be simulated using O(log^*n) queries to H.The six possible ν values combine with d possible values for each of i and j; determining ν requires at most 2(z_n + 2) black-box queries.Source: §V · pp. 6–7
• The associated graph is edge-colored so each color defines one Hamiltonian component and incident edges have different labels.Labels begin with ordered neighbor indices (i, j) and are augmented by ν to remove collisions.Source: §V · pp. 6–7
• The ν-construction repeatedly transforms chain values until at most six possibilities remain, with z_n of order log^*n.For realistic problem sizes, z_n is no more than 6.Source: §V · pp. 6–7
• The black-box function returns nonzero entries for diagonal edges and mutually exclusive paired-edge cases, assigning all other inputs (x, 0).This implements the colored components H_(i,j,ν) while preventing repeated diagonal elements.Source: §V · p. 7
• O(log^*n) black-box calls to f suffice to simulate each H(i,j,ν), yielding the query count stated in Eq. (3).The decomposition uses m = 6d^2 Hamiltonians, and each g evaluation requires 2(zn + 2) black-box calls.Source: §V · p. 8
• Calculating Υ(x, i, j) introduces O(n log^*n) auxiliary operations from bit comparisons, with subsequent steps preserving this scaling.Source: §V · p. 8
• The resulting scaling is superior to the n10 scaling in Ref..Source: §V · p. 9
• Finite-precision matrix elements contribute error at most 4m5kτ/2^n′, controlled below ǫ/2 by choosing n′ > 5 + log2(τd25k/ǫ).The integration error is also chosen below ǫ/2 so the total error remains below ǫ.Source: §V · p. 9

• The scheme reduces simulation scaling to be close to linear in ∥H∥t and decomposition costs to close to log^*n black-box calls.Source: §VI · p. 9
• The authors show that scaling cannot be sublinear in ∥H∥t for reasonable values of n.Source: §VI · p. 9