Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians 1: Lieb–Robinson Bound ‖[A(t),B]‖ ≤ (2/√η)‖A‖‖B‖(e^{ζ|t|√(8η)}−1)Σ_{x∈X}e^{−μ dist(x,Y)} Under Small CommutatorsResearch Paper
Motivation
A local quantum system is built from degrees of freedom placed at sites of a lattice. Its Hamiltonian may contain many terms, each acting on a small group of sites. Even though a term is local, time evolution can spread an observable beyond its original support. A Lieb–Robinson bound limits the size of a commutator between the evolved observable and one supported elsewhere. It gives a quantitative way to say that information propagates with an effective finite velocity. The Appendix C bound of Haah, Hastings, Kothari and Low treats interactions with exponential spatial decay and makes the effect of almost commuting Hamiltonian terms explicit.
The paper studies quantum simulation, where a system's real time evolution is approximated by a circuit. Lemma 12 is an analytic ingredient: it controls how far a local observable can spread during the simulated evolution. The mission targets that lemma and the displayed estimates in its proof, with the constants printed in the pinned arXiv version. The paper proves the results; the remaining task here is to give the stated finite system version machine checked proofs.
Setting
Let be a finite set of sites equipped with a metric . Each site has the same local Hilbert space , and the whole system has product basis indexed by configurations . An operator supported on is a matrix of the form : it may change the configuration on , but acts as the identity on every site outside . The matrix norm throughout is the spectral operator norm.
For every , let be a Hermitian operator supported on , and define the time independent Hamiltonian . The sum includes all subsets, including the empty set. Let
For site sets, write when , and when is nonempty. The diameter is for nonempty . The paper imposes two quantitative conditions. First, for some , every pair of terms has a small commutator:
Second, for some , the interactions decay in the weighted sense
Neither condition bounds each by one. This matters because the result is meant to include large but nearly commuting terms. These conventions are from Appendix C.1 of the source.
Formalization targets
The goal is Lemma 12. For an operator supported on and an operator supported on a disjoint set , and every real , the proposed formal statement is
The coefficient of in the exponential is proportional to . The goal keeps the paper's explicit factor , its inside the exponential, and the full sum over sites in . The statement is for , as the displayed formula is undefined at ; a family satisfying (14) with also satisfies it for any positive .
The milestones follow the source's numbered displays: the initial estimates for and in (28), their integral inequalities (24) and (27), the linked set series (32), the four estimates of Proposition 13, and the bound on its th line in (37). Here takes a supremum over supported operators of norm at most one, and . The milestone list is a map of the quantities that the proof controls, while the goal itself mentions only the physical operators and the two hypotheses.
Significance
The bound shows that a commutator is small when the support of is far from , with a rate determined by the decay parameter and the small commutator parameter . It applies to finite systems of any size with the same constants in (14) and (15). This makes it useful for reasoning about local approximations of time evolution in the quantum simulation setting of the paper. The authors also explain why a velocity proportional to can occur under their hypotheses, so a linear dependence on is not generally available. See the discussion immediately after Lemma 12 in Appendix C.1.
Formalizing the result would supply a reusable finite matrix model of local observables and a checked version of the analytic estimates for near commuting interactions. The source paper provides a proof, but this proposed statement and its milestones currently have no machine checked proof in the mission. The definitions of support, Heisenberg evolution and linked interactions may also be reused in later formalizations of quantum lattice dynamics.
Difficulty
The obvious global norm bound ignores the distance between supports. Merely bounding also loses spatial information and can grow with the whole system. The sharper statement simultaneously tracks where an interaction overlaps the current support and how the small commutator factor enters repeated interactions. A rigorous treatment must control a supremum over local operators, time dependent matrix exponentials, and an infinite series of finite linked set sums without changing any of the paper's constants.
Formalization scope
Sites form an arbitrary finite metric space, a disclosed generalization of the lattice setting used for the main algorithm. A common local dimension is used at every site; qubits occur at . Operators are complex matrices on the configuration space , with Mathlib's scoped L2 operator norm. Every term is Hermitian and explicitly supported on its stated set, and is the sum over all subsets. Time is real and is constant in time. The paper mentions a piecewise continuous time dependent extension, which this mission does not state.
The goal explicitly requires . The printed sentence of Lemma 12 omits this, but its derivation on page 24 assumes it; without disjointness the right side is zero at while the left side need not be. The positive condition is likewise explicit. These are the two repairs to the printed lemma, and they are recorded on each relevant item. The milestones (24) and (27) are restricted to , the direction for which the displayed forward integral uses and .
For an empty set, the Lean point to set distance and the local set distance are taken to be zero; a supported operator on the empty set is a scalar, so its commutators vanish. uses a real supremum of a nonempty, bounded set, and (32) states an actual sum with HasSum. The integral milestones involve continuous finite dimensional evolution. The support definition includes nonconstant single site operators, and the case is part of the goal. These choices prevent the result from being obtained through a vacuous support predicate, an entrywise norm, division by zero at , a default value of an unbounded supremum or divergent sum, or omitted disjointness. Contributions that establish the support calculus, matrix evolution estimates, integral inequalities, or linked set bounds are all within scope.
Selected references
- Jeongwan Haah, Matthew B. Hastings, Robin Kothari and Guang Hao Low, Quantum algorithm for simulating real time evolution of lattice Hamiltonians, SIAM Journal on Computing, 2021. arXiv:1801.03922v4, Appendix C.1–C.3, pp. 21–25.