Average-case Speedup for Product Formulas

Abstract

Quantum simulation is a promising application of future quantum computers. Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. For an accurate product formula approximation, the state-of-the-art gate complexity depends on the number of terms in the Hamiltonian and a local energy estimate. In this work, we give evidence that product formulas, in practice, may work much better than expected. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states, while the existing estimate is for the worst states. For general $k$-local Hamiltonians and higher-order product formulas, we obtain gate count estimates for input states drawn from any orthogonal basis. The gate complexity significantly improves over the worst case for systems with large connectivity. Our typical-case results generalize to Hamiltonians with Fermionic terms, with input states drawn from a fixed-particle number subspace, and with Gaussian coefficients (e.g., the SYK models). Technically, we employ a family of simple but versatile inequalities from non-commutative martingales called $\text{uniform smoothness}$, which leads to $\text{Hypercontractivity}$, namely $p$-norm estimates for $k$-local operators. This delivers concentration bounds via Markov's inequality. For optimality, we give analytic and numerical examples that simultaneously match our typical-case estimates and the existing worst-case estimates. Therefore, our improvement is due to asking a qualitatively different question, and our results open doors to the study of quantum algorithms in the average case.

51 pages, 10 figures; v2 improved presentation and included numerical simulation

References in corpus (32)

• Comments on the Sachdev-Ye-Kitaev model
• Quantum computational chemistry
• Error mitigation for short-depth quantum circuits
• Fast Scramblers
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Toward the first quantum simulation with quantum speedup
• A Theory of Trotter Error
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Towards the fast scrambling conjecture
• A random compiler for fast Hamiltonian simulation
• Quantum Simulation for High Energy Physics
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Building a fault-tolerant quantum computer using concatenated cat codes
• Quantum computing enhanced computational catalysis
• Sandwiched Rényi Divergence Satisfies Data Processing Inequality
• Nearly optimal lattice simulation by product formulas
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Estimates of moments and tails of Gaussian chaoses
• Hamiltonian simulation in the low-energy subspace
• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Provably accurate simulation of gauge theories and bosonic systems
• Some applications of hypercontractive inequalities in quantum information theory
• Concentration for random product formulas
• A Minkowski Type Trace Inequality and Strong Subadditivity of Quantum Entropy II: Convexity and Concavity
• Nearly tight Trotterization of interacting electrons
• Shorter gate sequences for quantum computing by mixing unitaries
• Hamiltonian simulation with random inputs
• Optimal Frobenius light cone in spin chains with power-law interactions
• A noncommutative martingale convexity inequality

Cited by in corpus (10)

• Entanglement accelerates quantum simulation
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Complexity is not Enough for Randomness
• Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Probing Entanglement Dynamics in the SYK Model using Quantum Computers
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
• Phase estimation with partially randomized time evolution
• Trotter error and gate complexity of the SYK and sparse SYK models