02331nas a2200181 4500008004100000245005200041210005200093260001300145300000700158490000700165520185000172100002302022700001302045700001902058700001802077700001702095856003702112 2021 eng d00aTheory of Trotter Error with Commutator Scaling0 aTheory of Trotter Error with Commutator Scaling c2/1/2021 a490 v113 a

The Lie-Trotter formula, together with its higher-order generalizations, provides a direct approach to decomposing the exponential of a sum of operators. Despite significant effort, the error scaling of such product formulas remains poorly understood. We develop a theory of Trotter error that overcomes the limitations of prior approaches based on truncating the Baker-Campbell-Hausdorff expansion. Our analysis directly exploits the commutativity of operator summands, producing tighter error bounds for both real- and imaginary-time evolutions. Whereas previous work achieves similar goals for systems with geometric locality or Lie-algebraic structure, our approach holds in general. We give a host of improved algorithms for digital quantum simulation and quantum Monte Carlo methods, including simulations of second-quantized plane-wave electronic structure, k-local Hamiltonians, rapidly decaying power-law interactions, clustered Hamiltonians, the transverse field Ising model, and quantum ferromagnets, nearly matching or even outperforming the best previous results. We obtain further speedups using the fact that product formulas can preserve the locality of the simulated system. Specifically, we show that local observables can be simulated with complexity independent of the system size for power-law interacting systems, which implies a Lieb-Robinson bound as a byproduct. Our analysis reproduces known tight bounds for first- and second-order formulas. Our higher-order bound overestimates the complexity of simulating a one-dimensional Heisenberg model with an even-odd ordering of terms by only a factor of 5, and is close to tight for power-law interactions and other orderings of terms. This suggests that our theory can accurately characterize Trotter error in terms of both asymptotic scaling and constant prefactor.

1 aChilds, Andrew, M.1 aSu, Yuan1 aTran, Minh, C.1 aWiebe, Nathan1 aZhu, Shuchen uhttps://arxiv.org/abs/1912.0885401668nas a2200169 4500008004100000245006300041210006100104260001400165490000600179520118500185100002301370700002301393700001301416700001401429700001801443856003701461 2020 eng d00aTime-dependent Hamiltonian simulation with L1-norm scaling0 aTimedependent Hamiltonian simulation with L1norm scaling c4/20/20200 v43 a

The difficulty of simulating quantum dynamics depends on the norm of the Hamiltonian. When the Hamiltonian varies with time, the simulation complexity should only depend on this quantity instantaneously. We develop quantum simulation algorithms that exploit this intuition. For the case of sparse Hamiltonian simulation, the gate complexity scales with the L1 norm ∫t0dτ∥H(τ)∥max, whereas the best previous results scale with tmaxτ∈[0,t]∥H(τ)∥max. We also show analogous results for Hamiltonians that are linear combinations of unitaries. Our approaches thus provide an improvement over previous simulation algorithms that can be substantial when the Hamiltonian varies significantly. We introduce two new techniques: a classical sampler of time-dependent Hamiltonians and a rescaling principle for the Schrödinger equation. The rescaled Dyson-series algorithm is nearly optimal with respect to all parameters of interest, whereas the sampling-based approach is easier to realize for near-term simulation. By leveraging the L1-norm information, we obtain polynomial speedups for semi-classical simulations of scattering processes in quantum chemistry.

1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aSu, Yuan1 aWang, Xin1 aWiebe, Nathan uhttps://arxiv.org/abs/1906.0711501404nas a2200133 4500008004100000245005700041210005500098260001500153490000600168520102800174100001301202700001801215856003701233 2018 eng d00aTime-reversal of rank-one quantum strategy functions0 aTimereversal of rankone quantum strategy functions c2018/01/250 v23 a

The quantum strategy (or quantum combs) framework is a useful tool for reasoning about interactions among entities that process and exchange quantum information over the course of multiple turns. We prove a time-reversal property for a class of linear functions, defined on quantum strategy representations within this framework, that corresponds to the set of rank-one positive semidefinite operators on a certain space. This time-reversal property states that the maximum value obtained by such a function over all valid quantum strategies is also obtained when the direction of time for the function is reversed, despite the fact that the strategies themselves are generally not time reversible. An application of this fact is an alternative proof of a known relationship between the conditional min- and max-entropy of bipartite quantum states, along with generalizations of this relationship.

1 aSu, Yuan1 aWatrous, John uhttps://arxiv.org/abs/1801.0849101648nas a2200169 4500008004100000245006100041210006100102300001400163490000900177520116300186100002301349700001901372700001801391700001901409700001301428856003701441 2018 eng d00aToward the first quantum simulation with quantum speedup0 aToward the first quantum simulation with quantum speedup a9456-94610 v115 3 a

With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.

1 aChilds, Andrew, M.1 aMaslov, Dmitri1 aNam, Yunseong1 aRoss, Neil, J.1 aSu, Yuan uhttps://arxiv.org/abs/1711.10980