IQIM Postdoctoral and Graduate Student Seminar
Joint AWS/IQIM Seminar
Abstract: Quantum simulation is expected to be one of the central applications of future quantum computers. Product formulas, or Trotterization, are the oldest and still one of the most studied methods for quantum simulations due to their relatively simple implementation without ancillae. For an accurate product formula approximation in the spectral norm, the state-of-the-art gate complexity depends on the number of terms in the Hamiltonian and a certain 1-norm of its local terms. This work considers the concentration aspects of Trotter error: we show quantitatively that the Trotter error exhibits 2-norm scaling ``typically'', with the current estimates in 1-norm being for the ``worst'' cases. For general k-local Hamiltonians, we obtain gate count estimates for input states drawn from a 1-design ensemble (which includes e.g., computational basis states). Our gate count depends on the number of terms in the Hamiltonian but replaces the 1-norm quantity by its analog in 2-norm, giving significant speedup for systems with large connectivity. Our concentration results generalize to Hamiltonians with Fermionic terms and when the input state is restricted to a low-particle number subspace. Further, when the Hamiltonian itself has random coefficients, such as the SYK models, we show the stronger result that the 2-norm behavior persists even for the worst input state. Our primary technical tool is a family of simple but versatile inequalities from non-commutative martingales called uniform smoothness. We use them to derive Hypercontractivity, i.e., p-norm estimates for low-degree polynomials (i.e., k-local operator), implying concentration via Markov's inequality. In terms of optimality, we give examples that simultaneously match our p-norm estimates and the existing spectral norm estimates. This shows that 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.
Attend by zoom at https://caltech.zoom.us/j/81483492264