A Caltech Library Service

Concentration for Trotter error

Chen, Chi-Fang and Brandão, Fernando G. S. L. (2021) Concentration for Trotter error. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Quantum simulation is expected to be one of the key applications of future quantum computers. Product formulas, or Trotterization, are the oldest and, still today, an appealing method for quantum simulation. For an accurate product formula approximation in the spectral norm, the state-of-the-art gate complexity depends on the number of Hamiltonian terms and a certain 1-norm of its local terms. This work studies the concentration aspects of Trotter error: we prove that, typically, the Trotter error exhibits 2-norm (i.e., incoherent) scaling; the current estimate with 1-norm (i.e., coherent) scaling is for the worst cases. For k-local Hamiltonians and higher-order product formulas, we obtain gate count estimates for input states drawn from a 1-design ensemble (e.g., computational basis states). Our gate count depends on the number of Hamiltonian terms but replaces the 1-norm quantity by its analog in 2-norm, giving significant speedup for systems with large connectivity. Our results generalize to Hamiltonians with Fermionic terms and when the input state is drawn from a low-particle number subspace. Further, when the Hamiltonian itself has Gaussian coefficients (e.g., the SYK models), we show the stronger result that the 2-norm behavior persists even for the worst input state. Our main technical tool is a family of simple but versatile inequalities from non-commutative martingales called uniform smoothness. We use them to derive Hypercontractivity, namely p-norm estimates for low-degree polynomials, which implies concentration via Markov's inequality. In terms of optimality, we give examples that simultaneously match our p-norm bounds and the spectral norm bounds. Therefore, our improvement is due to asking a qualitatively different question from the spectral norm bounds. Our results give evidence that product formulas in practice may generically work much better than expected.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Chen, Chi-Fang0000-0001-5589-7896
Brandão, Fernando G. S. L.0000-0003-3866-9378
Additional Information:We thank Yuan Su and Mario Berta for helpful discussions and Joel Tropp and Andrew Lucas for related collaborations. CFC is especially thankful for Joel Tropp for introducing to him the subject of matrix concentration inequalities. After this work was completed, we became aware of related work by Qi Zhao, You Zhou, Alexander F. Shaw, Tongyang Li, and Andrew M. Childs that also studies Hamiltonian simulation with random input states. We thank them for letting us know about their work. CFC is supported by Caltech RA fellowship and the Eddleman Fellowship.
Group:Institute for Quantum Information and Matter, AWS Center for Quantum Computing
Funding AgencyGrant Number
Robert A. Millikan FellowshipUNSPECIFIED
Eddleman FellowshipUNSPECIFIED
Record Number:CaltechAUTHORS:20211130-215806841
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:112117
Deposited By: George Porter
Deposited On:30 Nov 2021 23:18
Last Modified:30 Nov 2021 23:18

Repository Staff Only: item control page