Hamiltonian Simulation and Product Formulas

Let $V$ be a finite-dimensional complex inner-product space and let $H=H^{\ast }$ be a specified endomorphism. Its exact time-$t$ evolution is $U_H(t)=e^{-itH}$ as defined by Finite Hermitian matrix dynamics. The notation $\mathrm{\parallel }T\mathrm{\parallel }$ denotes the operator norm of The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||. The target register's Hilbert space is identified with $V$ as part of the input. A Hamiltonian simulator at encoded time $t$ and tolerance $0<ϵ<1$ is a declared procedure whose output is a unitary $W$ on the stated target register satisfying $\mathrm{\parallel }W-U_H(t)\mathrm{\parallel }\le ϵ$. If its circuit uses auxiliary registers, the exact clean or dirty contract of Clean and dirty ancillas must make the induced target unitary $W$ well-defined; the error is measured on that target unitary. The scalar time and tolerance have exact finite descriptions under the declared input convention; their description lengths are recorded.

The resource record lists, separately, the number of calls to each named oracle, controlled calls, inverse calls, elementary gate occurrences, clean and dirty ancillary wires, coefficient bits, full circuit-description bits, and classical generation time. A coordinate not supplied by the access contract is unavailable, not zero. No matrix description supplies a circuit, oracle, controlled call, inverse call, or term exponential for free; uniform-family and cost conventions are those of Full-list uniform quantum circuit family, Circuit-family and computation cost model, Controlled Unitary Access, and Inverse Unitary Access. No polynomial resource bound is asserted by this definition.

A term-list access input consists of an integer $m\ge 1$, finite-dimensional self-adjoint endomorphisms $H_1,\dots ,H_m$ on one stated register, and the exact target $H={\sum }_{j=1}^m{H}_j$. A supported time code is a finite expression whose leaves are rational numbers or symbols ${\rho }_q$ denoting the unique positive real root of $x^q=4$ for an odd integer $q\ge 1$; Existence and uniqueness of $n$-th roots: a unique $a^{1\mathrm{/}n}\ge 0$ with $(a^{1\mathrm{/}n}{)}^n=a$ gives a unique nonnegative root; it is positive because $0^q=0\mathrm{\ne }4$. Internal operations are addition, subtraction, multiplication, or division by a nonzero expression. Its exact real value and bit length are recorded. These codes include rational times and every coefficient-scaled rational time in the finite Suzuki recursion.

For each $j$, the input declares which time codes are supported and supplies either the exact operation $e^{-is{H}_j}$ or a full-list uniform circuit generator, in the sense of Full-list uniform quantum circuit family, that returns a unitary $V_j(s)$ together with a certified error ${\eta }_j(s)\ge 0$ satisfying $\mathrm{\parallel }{V}_j(s)-e^{-is{H}_j}\mathrm{\parallel }\le {\eta }_j(s)$. If a circuit uses auxiliary registers, it supplies the exact clean or dirty contract of Clean and dirty ancillas so that its induced operation $V_j(s)$ on the target is well-defined: clean registers start and return to zero for every target input, and dirty registers are acted on by the identity. The operator-norm error is measured on the induced target operation. The provider specifies how each supported code is passed to the generator and records its actual description length and generation time; no polynomial bound is inferred. This is an explicit access promise, not a claim that every matrix has such a family.

For each supported call the input records its named-oracle query counts, gate count, ancillary wires, description bits, coefficient bits, and classical generation cost. Costs of composing the calls into a full product and generating that product are separately recorded as $Q_{\mathrm{w}\mathrm{r}\mathrm{a}\mathrm{p}}$ and $G_{\mathrm{w}\mathrm{r}\mathrm{a}\mathrm{p}}$. A controlled form is available only when separately declared as the block operation of Controlled Unitary Access. Inverse access to a call is available only when separately declared under Inverse Unitary Access, with its own cost and error record. Forward access implies neither capability. The term list supplies no promise that any operation or coefficient computation is free.

Fix $N\ge 1$, a sparsity bound $d\ge 1$, an integer $b\ge 1$, and an injective code $\mathrm{e}\mathrm{n}\mathrm{c}:C\to \{0,1{\}}^b$ for a finite set $C\subset \mathbb{C}$ containing $0$ and closed under conjugation. Put $w=\lceil {\log }_{2}N\rceil$ and $v=\lceil {\log }_{2}d\rceil$, identify $[N]$ with the first $N$ strings in $\{0,1{\}}^w$, and regard any remaining strings as invalid labels. A valid $w$-bit index is zero-extended to $w+1$ bits. Let $H=(H_{xy}{)}_{x,y\in [N]}$ be Hermitian, have entries in $C$, and have at most $d$ nonzero entries in every row. For each valid row $x$, list its nonzero column indices in increasing order. Define the total location function $f_H(x,\mathrm{\ell })$ to be the $\mathrm{\ell }$-th listed index for a valid slot $0\le \mathrm{\ell }<d$ when that slot exists, and a distinguished sentinel otherwise. Invalid row labels and invalid slot labels also return the sentinel. Encode the sentinel by a fixed $(w+1)$-bit word outside the valid index codes. Define the total value function $g_H(x,y)$ to return $\mathrm{e}\mathrm{n}\mathrm{c}(H_{xy})$ on valid labels and $\mathrm{e}\mathrm{n}\mathrm{c}(0)$ on invalid labels. All label widths and codes are part of the finite input description.

The row-location oracle and entry-value oracle are the coherent XOR maps $O_{f_H}\mathrm{\mid }x,\mathrm{\ell },z⟩=\mathrm{\mid }x,\mathrm{\ell },z\oplus f_H(x,\mathrm{\ell })⟩$ and $O_{g_H}\mathrm{\mid }x,y,z⟩=\mathrm{\mid }x,y,z\oplus g_H(x,y)⟩$, where the output target has respectively $w+1$ and $b$ bits. The slot register has $v$ bits; all unused slot strings are invalid and use the sentinel. These are total Boolean-function oracles on every bitstring basis input. They are instances of Coherent XOR function oracle, whose justified-by supplier proves unitarity and involutivity for arbitrary total functions. Each named call and any separately granted controlled or inverse call is charged under Circuit-family and computation cost model. This exact-code model describes the decoded matrix $H$; approximating a different target matrix requires a separate bound on the matrix difference. Row and value access alone does not supply a term list or term-evolution circuits.

For a term-list input $H={\sum }_{j=1}^m{H}_j$, a real time $h$, and the announced order $1,\dots ,m$, define $S_1(h):=e^{-ih{H}_1}{e}^{-ih{H}_2}\cdots e^{-ih{H}_m}\mathrm{.}$ Operator products are written in their ordinary left-to-right algebraic order, so the rightmost factor acts first on a vector. For an integer $r\ge 1$, the $r$-step first-order approximation at time $t$ is $S_1(t\mathrm{/}r{)}^r$. Each exponential is the finite-matrix evolution of Finite Hermitian matrix dynamics; this definition does not identify the product with $e^{-itH}$ when terms fail to commute.

For the announced term order $1,\dots ,m$ and real $h$, define the palindromic product $S_2(h):=e^{-ih{H}_1\mathrm{/}2}{e}^{-ih{H}_2\mathrm{/}2}\cdots e^{-ih{H}_{m-1}\mathrm{/}2}{e}^{-ih{H}_m}{e}^{-ih{H}_{m-1}\mathrm{/}2}\cdots e^{-ih{H}_2\mathrm{/}2}{e}^{-ih{H}_1\mathrm{/}2}\mathrm{.}$ For $m=1$ this is just $e^{-ih{H}_1}$. The $r$-step approximation is $S_2(t\mathrm{/}r{)}^r$, with $r\ge 1$. A written product acts right-to-left, as in First-order Lie product formula. Every term call and any signed-time implementation cost must be declared by Term-list Hamiltonian access.

The finite Suzuki recursion, finite-order cancellation, and the explicit conservative norm bound proved on this page are the higher-order claims supplied here. They use signed term times and charge every expanded term call. No asymptotic complexity claim with hidden commutator constants, no generic nested-commutator estimate, and no free negative-time access is part of this remark; any stronger resource assertion needs its own complete proof and access-cost accounting.

Let $V$ be a finite-dimensional complex inner-product space, let $H_1,\dots ,H_m$ be self-adjoint endomorphisms of $V$ with $m\ge 1$, and set $H={\sum }_{j=1}^m{H}_j$. For every real $t$ and integer $r\ge 1$, $\parallel S_1(t\mathrm{/}r{)}^r-U_H(t)\parallel \le \frac{t^2}{2r}{\sum }_{1\le j<k\le m}\mathrm{\parallel }[H_j,H_k]\mathrm{\parallel },$ where $S_1$ has the fixed order of First-order Lie product formula and $U_H(t)=e^{-itH}$ is the finite-matrix evolution of Finite Hermitian matrix dynamics.

Input: A finite term-list access input with $H={\sum }_{j=1}^m{H}_j$, a finite time code $t$ in the expression language of Term-list Hamiltonian access, a rational tolerance $0<ϵ<1$, a certified rational $C_2\ge 0$ satisfying $C_2\ge {\sum }_{1\le j<\mathrm{\ell }\le m}\mathrm{\parallel }[H_j,H_{\mathrm{\ell }}]\mathrm{\parallel }$, and a supplied certified rational upper bound $R\ge 0$ satisfying $R\ge t^2{C}_2\mathrm{/}ϵ$. For $t\mathrm{\ne }0$, put $r=\max \{1,\lceil R\rceil \}$ and $h=t\mathrm{/}r$; the access declarations must supply each term call at this exact signed code $h$, with its implementation and costs. A call may be directly supported at $h$ or supplied by separately declared inverse or time-reversed access, with that route's own costs. When $t\mathrm{\ne }0$, every approximate call must have a certified error, and the sum of those errors over all $rm$ calls must be at most $ϵ\mathrm{/}2$. The time-code and call conventions are those of Term-list Hamiltonian access.

Output: The composed unitary circuit for the declared product order, together with its query, gate, ancilla, coefficient-bit, description-bit, and classical-generation cost record.

Instructions:

1. Compare the exact value of the supplied time code with $0$. If it is $0$, return the identity circuit.
2. Otherwise set $r=\max \{1,\lceil R\rceil \}$ using rational arithmetic and set $h=t\mathrm{/}r$ as a supported finite expression code.
3. For each of exactly $r$ repetitions, execute the declared term calls chronologically in order $m,m-1,\dots ,1$. By Denotational semantics of a finite layered circuit, later executed gates multiply on the left. The ideal exact-call operator for one repetition is therefore $e^{-ih{H}_1}\cdots e^{-ih{H}_m}$ of First-order Lie product formula; with supplied implementations the actual operator is $V_1(h)\cdots V_m(h)$, with the declared call errors accumulated separately. If the call at $h$ is supplied through inverse or time-reversed access, use that separately declared route and its cost and error record; do not infer it from forward access alone.
4. Keep circuit-generation, coefficient, and all oracle costs in their separate declared coordinates. When $t\mathrm{\ne }0$ and calls are approximate, retain their per-call error records; admissibility requires their sum over all $rm$ calls to be at most $ϵ\mathrm{/}2$.

The procedure makes no claim that the required term calls or their uniform generator exist for an arbitrary matrix.

Let $V$ be finite-dimensional, let $H_1,\dots ,H_m$ be self-adjoint with $m\ge 1$, put $H={\sum }_j{H}_j$ and $M={\sum }_j\mathrm{\parallel }{H}_j\mathrm{\parallel }$. For every real $t$ and integer $r\ge 1$, $\parallel S_2(t\mathrm{/}r{)}^r-U_H(t)\parallel \le \frac{\mathrm{\mid }t{\mathrm{\mid }}^3{M}^3}{3r^2},$ where $S_2$ is the palindromic product of Symmetric second-order product formula and $U_H$ is the finite-matrix evolution of Finite Hermitian matrix dynamics.

Input: Integers $k,r\ge 1$, a finite time code $t$ in the expression language of Term-list Hamiltonian access, and a finite term-list access input.

Admissible conditions: If $t\mathrm{\ne }0$, for every term occurrence $e^{-i{c}_{\nu }t{H}_{j_{\nu }}\mathrm{/}r}$ in the fully expanded segment, the access input supports that exact signed time code for term $H_{j_{\nu }}$ and declares its implementation, per-call costs, and any approximation-error record. The call may be supplied directly at the signed code or through separately declared inverse or time-reversed access with its own cost and error record. This condition includes the half-time calls in the base formula and every signed central call in the recursion.

Output: The finite product circuit and its declared query, gate, ancilla, coefficient-bit, description-bit, and classical-generation costs.

Instructions:

1. Compare the exact value of the supplied time code with $0$. If it is $0$, return the identity. Otherwise begin with $S_2(h)$ from Symmetric second-order product formula, where $h=t\mathrm{/}r$.
2. For each $j=2,\dots ,k$, let ${\rho }_{2j-1}$ be the unique nonnegative root of $x^{2j-1}=4$ from Existence and uniqueness of $n$-th roots: a unique $a^{1\mathrm{/}n}\ge 0$ with $(a^{1\mathrm{/}n}{)}^n=a$; it is positive since $0^{2j-1}\mathrm{\ne }4$. Put $p_j=(4-{\rho }_{2j-1}{)}^{-1}$, and recursively replace the current even-order formula $S_{2j-2}(h)$ by $S_{2j}(h):=S_{2j-2}(p_{j}h{)}^2{S}_{2j-2}((1-4p_j)h)S_{2j-2}(p_{j}h{)}^2\mathrm{.}$
3. Recursively expand one segment until only the term exponentials remain, retaining their displayed operator order. For exactly $r$ repetitions, execute the factors of each expanded segment chronologically in the reverse of their displayed operator order. Since later executed gates multiply on the left by Denotational semantics of a finite layered circuit, the exact-call operator is $S_{2k}(t\mathrm{/}r{)}^r$. If calls are approximate, execute their supplied unitary implementations in that same chronological order and retain the per-call error records; the displayed $S_{2k}$ remains the ideal exact-call word.
4. For each central coefficient $1-4p_j$, use the implementation declared for that actual signed call time. For $q=2j-1\ge 3$, let ${\rho }_q$ be the positive root of ${\rho }_q^q=4$. It is positive, and ${\rho }_q<4$: otherwise monotonicity of positive integer powers (Monotonicity of $x\mapsto x^n$ and of $n\mapsto a^n$) would give ${\rho }_q^q\ge 4^q>4$, a contradiction. Hence $4-{\rho }_q>0$, $p_j=(4-{\rho }_q{)}^{-1}>1\mathrm{/}4$, and $1-4p_j<0$. Thus the central coefficient is negative; the actual call time is this coefficient times the current recursive time argument. Use the resulting signed code, which may be positive or negative, with its directly supported implementation or separately declared inverse or time-reversed access. Charge exact coefficient descriptions and classical generation separately.

The recursion is finite because $j$ increases only from $2$ through $k$, and each expansion makes five calls to the preceding formula. No asymptotic error or cost guarantee is part of this procedure definition.

For the term-list input $H={\sum }_{j=1}^m{H}_j$ in Term-list Hamiltonian access, let $t$ be a finite time code in its expression language, let $0<ϵ<1$ be rational, and let $C_2\ge 0$ be a certified rational satisfying $C_2\ge {\sum }_{1\le j<\mathrm{\ell }\le m}\mathrm{\parallel }[H_j,H_{\mathrm{\ell }}]\mathrm{\parallel }$. Supply a certified rational upper bound $R\ge t^2{C}_2\mathrm{/}ϵ$ and put $r=\max \{1,\lceil R\rceil \}$ and $h=t\mathrm{/}r$. When $t\mathrm{\ne }0$, suppose each term call at the exact signed code $h$ is supported and declared, directly or through separately declared inverse or time-reversed access, with at most $q_j$ named queries and $g_j$ gate occurrences. Let $Q_{\mathrm{w}\mathrm{r}\mathrm{a}\mathrm{p}}$ and $G_{\mathrm{w}\mathrm{r}\mathrm{a}\mathrm{p}}$ be the separately declared query and gate costs of uniform circuit composition and generation. For $t\mathrm{\ne }0$, the algorithm First-order term-list simulator uses at most $r{\sum }_j{q}_j+Q_{\mathrm{w}\mathrm{r}\mathrm{a}\mathrm{p}}$ queries and $r{\sum }_j{g}_j+G_{\mathrm{w}\mathrm{r}\mathrm{a}\mathrm{p}}$ gates. Its exact term product has error at most $ϵ\mathrm{/}2$. If, when $t\mathrm{\ne }0$, implemented calls are unitary and their total operator-norm error over all $rm$ calls is at most $ϵ\mathrm{/}2$, the returned unitary is within $ϵ$ of $U_H(t)$. When $t=0$, the algorithm returns the identity with no term calls. Coefficient, description-bit, ancilla, and classical-generation resources remain separate coordinates.

Let $H_1,\dots ,H_m$ be fixed finite-dimensional self-adjoint matrices, $m\ge 1$, and let $U(h)=e^{-ih{\sum }_j{H}_j}$. The recursive formulas $S_{2k}$ of Finite higher-order Suzuki product formula have the same Taylor coefficients as $U(h)$ through degree $2k$ at $h=0$. They are symmetric: $S_{2k}(-h)=S_{2k}(h{)}^{-1}$ for all real $h$.

Let $k,m,r\ge 1$, let $H_1,\dots ,H_m$ be self-adjoint endomorphisms of a finite-dimensional complex inner-product space, and put $H={\sum }_j{H}_j$, $M={\sum }_j\mathrm{\parallel }{H}_j\mathrm{\parallel }$, and $q=2k+1$. Expand one recursive segment as $S_{2k}(h)={\prod }_{\nu =1}^L{e}^{-ih{c}_{\nu }{H}_{j_{\nu }}}$ in its declared order and set $B_k={\sum }_{\nu =1}^L\mathrm{\mid }{c}_{\nu }\mathrm{\mid }\mathrm{\parallel }{H}_{j_{\nu }}\mathrm{\parallel }$. For every real $t$, $\parallel S_{2k}(t\mathrm{/}r{)}^r-U_H(t)\parallel \le \frac{(B_k^q+M^q)\mathrm{\mid }t{\mathrm{\mid }}^q}{q!r^{q-1}}\mathrm{.}$ The expanded term count is $L=(2m-1)5^{k-1}$ per segment. If $t$ is rational with an exact finite code, a rational tolerance $ϵ>0$ and rational upper bounds $\bar{B}\ge B_k$, $\bar{M}\ge M$ are supplied, a finite integer search for the least $r\ge 1$ satisfying $r^{q-1}q!ϵ\ge ({\bar{B}}^q+{\bar{M}}^q)\mathrm{\mid }t{\mathrm{\mid }}^q$ makes the displayed exact-call error at most $ϵ$. For the resource claims when $t\mathrm{\ne }0$, require the term-list input to support every actual signed call code $c_{\nu }t\mathrm{/}r$ for its term $H_{j_{\nu }}$ in the fully expanded segment, including half-time base calls and negative central calls, and to declare an implementation and per-call cost at each such code. An inverse or time-reversed implementation must be separately declared with its own cost and error record; forward access alone does not supply it. When $t\mathrm{\ne }0$ and term circuits are approximate, add the sum of all per-call operator-norm errors separately; to keep total error at most $ϵ$, use $ϵ\mathrm{/}2$ in the integer search and require the sum of call errors over all $rL$ calls to be at most $ϵ\mathrm{/}2$. When $t\mathrm{\ne }0$, the term-call contributions to query and gate costs are the sums of the declared costs at the actual signed times in one expanded word, multiplied by $r$; when $t=0$, the recursive algorithm returns the identity with no term calls. The separately declared product-composition overheads $Q_{\mathrm{w}\mathrm{r}\mathrm{a}\mathrm{p}}$ and $G_{\mathrm{w}\mathrm{r}\mathrm{a}\mathrm{p}}$ are added to those totals; coefficient, description-bit, ancilla, and classical-generation resources remain separate coordinates.