Qubitized Hamiltonian simulator

Inputs. A finite Hermitian $H$, $\alpha >0$ with the certified norm promise $\mathrm{\parallel }H{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \alpha$, rational time $t$, rational $0<ϵ\le 1$, and either (i) the exact $(\alpha ,a,0)$ block encoding $U$ with clean injection $J$ and $J^{\ast }UJ=H\mathrm{/}\alpha$, or (ii) a separately selected bounded-block-error mode with the same declared ancilla embedding $J$ and a unitary $U$ whose clean block satisfies $\mathrm{\parallel }{J}^{\ast }UJ-H\mathrm{/}\alpha {\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le {ϵ}_{\mathrm{B}\mathrm{E}}$ for a supplied certified rational upper bound ${ϵ}_{\mathrm{B}\mathrm{E}}\ge 0$. The latter mode is accepted only if it passes the explicit post-degree error-budget test in steps 3 and 5. For either mode, declare the access and cost for $U,U^{\ast },$ controlled-$U$, controlled-$U^{\ast }$, both projector-phase circuits, coefficient preparation, SELECT, OAA reflections, phase synthesis, data access, and classical arithmetic. The input description also supplies terminating certified comparisons and rational-interval evaluations for the scalar arithmetic below.

Output. Return the finite circuit list and error certificate for a unitary dilation $V_{\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{l}}$. Its success claim is on the clean-input isometry $J_{\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{n}}\mathrm{\mid }\psi ⟩=\mathrm{\mid }{0}_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{k}}⟩\mathrm{\mid }\psi ⟩$; auxiliary output registers are approximate and are not measured to clean an unknown system input. On a failed polynomial or phase certificate, return the phase routine's declared failure status and do not report a simulator.

Generation and execution. Set $\tau =\alpha t$ and $\rho ={ϵ}^2\mathrm{/}10000$. For $t=0$, return the identity circuit and zero query count. Otherwise:

1. Starting at $d=\max (1,\lceil \mathrm{\mid }\tau \mathrm{\mid }\rceil )$, increase $d$ until $u=\mathrm{\mid }\tau \mathrm{\mid }\mathrm{/}(2(d+2))<1$ and $\frac{2(\mathrm{\mid }\tau \mathrm{\mid }\mathrm{/}2{)}^{d+1}}{(d+1)!(1-u)}\le \rho \mathrm{/}8.$ Evaluate each strict comparison by the certified interval routine named in OP0 of the binding operational appendix; an undecided equality is not rounded toward success.

2. For each $k=0,\dots ,d$, compute $J_k(\tau )$ from the series in Hamiltonian-simulation polynomial target. Stop its alternating-series evaluation only after its ratio ${\tau }^2\mathrm{/}[4(j+1)(j+k+1)]$ is below $1$ and its geometric remainder is at most $\rho \mathrm{/}(32(d+1))$. Store a rational coefficient and its error interval. Form $T_0=1,T_1=x,T_{k+1}=2x{T}_k-T_{k-1}$. Set $E=J_0+2{\sum }_{1\le 2r\le d}(-1{)}^r{J}_{2r}{T}_{2r},O=2{\sum }_{1\le 2r+1\le d}(-1{)}^r{J}_{2r+1}{T}_{2r+1}\mathrm{.}$ Thus $Q:=E-iO$ is the rounded Jacobi–Anger truncation and its certified scalar error is $\mathrm{\parallel }Q-f_{\tau }{\mathrm{\parallel }}_{[-1,1]}\le \rho$; the sign $(-i{)}^k$ is literal.

3. Require a certified combined polynomial error at most $\rho$. Then $\mathrm{\mid }E(x)\mathrm{\mid },\mathrm{\mid }O(x)\mathrm{\mid }\le 1+\rho$ on $[-1,1]$. Put $B=1+2\rho$, $p_E=E\mathrm{/}B$, and $p_O=O\mathrm{/}B$, and set ${\delta }_{\mathrm{q}\mathrm{s}\mathrm{p}}=\rho \mathrm{/}64$. Define $\mathrm{\Gamma }={\left(\frac{3ϵ}{128}\right)}^2-3\rho -2{\delta }_{\mathrm{q}\mathrm{s}\mathrm{p}}>0,$ since $3\rho +2{\delta }_{\mathrm{q}\mathrm{s}\mathrm{p}}=97{ϵ}^2\mathrm{/}320000<9{ϵ}^2\mathrm{/}16384$. In exact-block mode put ${ϵ}_{\mathrm{B}\mathrm{E}}=0$. In bounded-block-error mode require the supplied rational upper bound to satisfy $(8d{)}^2{ϵ}_{\mathrm{B}\mathrm{E}}\le {\mathrm{\Gamma }}^2$; otherwise return CERTIFICATE_ERROR. This is the explicit block-error allocation for the selected degree. Call Real bounded-polynomial QSP phase synthesis separately on the rational real targets in efficient-numerical mode with tolerance ${\delta }_{\mathrm{q}\mathrm{s}\mathrm{p}}$, their actual degree, and its parity. If either target is identically zero, declare degree $0$ and even parity. Retain each complementary-polynomial identity, phase list, per-phase precision and optional compiler certificates. A successful call certifies ${\eta }_{\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}}+{\sum }_{\mathrm{\ell }}{\zeta }_{\mathrm{\ell }}\le {\delta }_{\mathrm{q}\mathrm{s}\mathrm{p}}$, where ${\eta }_{\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}}$ is the exact phase-list polynomial error and ${\zeta }_{\mathrm{\ell }}$ are the implemented phase-slot errors, by Correctness of QSP phase synthesis. Execute each real QSVT extraction using Quantum singular-value transformation circuit and the supplied forward/inverse signal calls of Qubitization access model, with block-compression error $0$ in exact mode or at most ${ϵ}_{\mathrm{B}\mathrm{E}}$ in bounded mode. For the bounded mode, compare each exact $\mathrm{\Phi }$ and $-\mathrm{\Phi }$ singular-value transform on the perturbed and target block using Operator perturbation bound for QSVT, then average the two bounds. The phase-list polynomial mismatch and implemented phase-slot errors together contribute at most ${\delta }_{\mathrm{q}\mathrm{s}\mathrm{p}}$, while the averaged block perturbation is at most $4d\sqrt{{ϵ}_{\mathrm{B}\mathrm{E}}}$. Thus each extracted clean block differs from its target by at most ${\delta }_{\mathrm{q}\mathrm{s}\mathrm{p}}+4d\sqrt{{ϵ}_{\mathrm{B}\mathrm{E}}}$. Since $p_E$ is even and $p_O$ odd, these singular-value transforms on Hermitian $H\mathrm{/}\alpha$ equal the ordinary polynomials $p_E(H\mathrm{/}\alpha )$ and $p_O(H\mathrm{/}\alpha )$: the even values agree at $\lambda =\pm \sigma$, while for the odd transform a negative eigenvalue has left singular vector $u=-v$ and therefore supplies the sign; also $p_O(0)=0$. Propagate every non-success status from either synthesis or extraction unchanged; do not report a simulator on a failed certificate.

4. Pad both extraction workspaces to the same ordered register space. Prepare a clean coefficient qubit in $\mathrm{\mid }+⟩$. SELECT applies the $p_E(H\mathrm{/}\alpha )$ block in branch $0$ and $-i$ times the $p_O(H\mathrm{/}\alpha )$ block in branch $1$. Unprepare the coefficient qubit. The ideal target block is $M\mathrm{/}2$, where $M=p_E(H\mathrm{/}\alpha )-i{p}_O(H\mathrm{/}\alpha )=Q(H\mathrm{/}\alpha )\mathrm{/}B$. Let $M_{\mathrm{p}\mathrm{h}}$ be twice the clean block of this phase-certified $W$ when its remaining operations are exact. By the step-3 synthesis certificates and branchwise robustness from Operator perturbation bound for QSVT, $\mathrm{\parallel }{M}_{\mathrm{p}\mathrm{h}}-M{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 2{\delta }_{\mathrm{q}\mathrm{s}\mathrm{p}}+8d\sqrt{{ϵ}_{\mathrm{B}\mathrm{E}}},$ In exact-block mode this bound uses ${ϵ}_{\mathrm{B}\mathrm{E}}=0$. Since $B=1+2\rho$, the ideal target polynomial error satisfies $\mathrm{\parallel }M-e^{-itH}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \frac{\rho }{B}+\frac{B-1}{B}=\frac{3\rho }{1+2\rho }<3\rho ;$ here $f_{\tau }(H\mathrm{/}\alpha )=e^{-itH}$ by finite spectral calculus and $\mathrm{\mid }{f}_{\tau }(x)\mathrm{\mid }=1$. The factor $-i$ is a relative phase under any outer control and is not discarded.

5. Apply the explicit phase-corrected oblivious-amplitude-amplification unitary $C=-WR{W}^{\ast }RW$, where $R=I-2{\mathrm{\Pi }}_{\mathrm{z}\mathrm{e}\mathrm{r}\mathrm{o}}$ and $W$ is the complete even/odd block-combination circuit. Retain its work registers. By step 4, with $V=e^{-itH}$, the certified OAA input error is ${\eta }_{\mathrm{O}\mathrm{A}\mathrm{A}}:=3\rho +2{\delta }_{\mathrm{q}\mathrm{s}\mathrm{p}}+8d\sqrt{{ϵ}_{\mathrm{B}\mathrm{E}}}\le {\left(\frac{3ϵ}{128}\right)}^2<1\mathrm{/}100.$ The exact and bounded-block variants use the same OAA route; Robust one-step OAA including ancilla leakage certifies phase/block clean-input isometry error at most $10\sqrt{{\eta }_{\mathrm{O}\mathrm{A}\mathrm{A}}}\le 15ϵ\mathrm{/}64$, including the retained-work leakage.

   For the remaining implementation error, unroll the complete post-amplification circuit, including every occurrence within $W,W^{\ast },W$, both OAA reflections, the known correction, each $U\mathrm{/}{U}^{\ast }$ and controlled call, both SELECT branches, coefficient preparation/unpreparation, projector-reflection implementation, and all inverses. Exclude only phase-rotation and optional phase-compiler errors already covered by the two step-3 certificates. Let $N$ be the number of remaining primitive-unitary occurrences in this unrolled list. For $N>0$, require each finite-basis implementation ${\tilde{G}}_j$ of its ideal unitary $G_j$ to have a certified full-space bound $\mathrm{\parallel }{\tilde{G}}_j-G_j{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le ϵ\mathrm{/}(64N)$; exact supplied calls have zero error. Count repeated and controlled occurrences separately. If any implementation lacks a unitary certificate at its allocation, return IMPLEMENTATION_ERROR. The full-space telescoping product estimate, using The inner-product norm is definite, homogeneous, and satisfies the triangle inequality and unitary norm one, gives remaining post-amplification error at most $ϵ\mathrm{/}64$ (zero if $N=0$). The complete clean-input isometry certificate is therefore at most $15ϵ\mathrm{/}64+ϵ\mathrm{/}64=ϵ\mathrm{/}4<ϵ$; return CERTIFICATE_ERROR if a certified comparison does not verify this bound. A controlled simulator controls every whole block and the known correction, using the separately supplied controlled access and counting its implementation in the same way.

The arithmetic, coefficient series, two phase-generation calls, controlled QSVT sequences, coefficient register, SELECT, and OAA list are finite outputs; their gate, query, precision, workspace, description-bit, and classical computation costs are separate coordinates. The phase-generation call is the finite procedure of Real bounded-polynomial QSP phase synthesis, not a free source routine. A sparse input uses its actually supplied block-encoding circuit and its exact row-location, value, precision, and state-preparation costs; standard XOR sparse access alone does not imply an in-place reversible location permutation.