Qubitization and Near-Optimal Hamiltonian Simulation

Let $V,W:H\to K\otimes E$ be linear isometries between finite-dimensional complex inner-product spaces, meaning $V^{\ast }V=W^{\ast }W=I_H$, and assume $\delta \ge 0$ and $\mathrm{\parallel }V-W{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \delta$. For every nonzero finite-dimensional reference space $R$ and density matrix $\rho$ on $H\otimes R$ (a positive semidefinite matrix of trace one), define $V_R=V\otimes I_R$ and $W_R=W\otimes I_R$ on the ordered product bases. Define the partial trace by $({\mathrm{Tr}}_{E}X{)}_{(k,r),(k^{\mathrm{\prime }},r^{\mathrm{\prime }})}={\sum }_e{X}_{(k,e,r),(k^{\mathrm{\prime }},e,r^{\mathrm{\prime }})},$ and define $\mathrm{\parallel }X{\mathrm{\parallel }}_1$ as the sum of singular values and $D(\sigma ,\omega )=\frac{1}{2}\mathrm{\parallel }\sigma -\omega {\mathrm{\parallel }}_1$. The output density matrices ${\rho }_V=({\mathrm{Tr}}_E\otimes I_R)(V_R\rho V_R^{\ast }),{\rho }_W=({\mathrm{Tr}}_E\otimes I_R)(W_R\rho W_R^{\ast })$ satisfy $D({\rho }_V,{\rho }_W)\le \delta$. Tensor products use the ordered product orthonormal basis and product inner product; the displayed matrix formula fixes the partial-trace convention used here. For column vectors, $a^{\ast }$ denotes conjugate transpose and $a{a}^{\ast }$ the rank-one matrix with entries $a_i\overline{a_j}$.

Let ${\mathcal{B}}_n$ be the complex inner-product space with orthonormal basis $\{\mathrm{\mid }y⟩:y\in \{0,1{\}}^n\}$. For $1\le r\le n$, define $X_r\mathrm{\mid }{y}_1\cdots y_n⟩=\mathrm{\mid }{y}_1\cdots (y_r\oplus 1)\cdots y_n⟩$, and put $J=\frac{1}{2}{\sum }_{r=1}^n{X}_r$. For $0\le i\le n$, let $\mathrm{\mid }{D}_i^n⟩$ be the normalized uniform sum of basis vectors of Hamming weight $i$; define ${\mathcal{S}}_n=\mathrm{span}\{\mathrm{\mid }{D}_i^n⟩:0\le i\le n\}$. On a separate path space with orthonormal basis $\{\mathrm{\mid }i⟩:0\le i\le n\}$, define $H_0$ to have off-diagonal entries $w_i=\sqrt{i(n+1-i)}\mathrm{/}n$ between $\mathrm{\mid }i-1⟩$ and $\mathrm{\mid }i⟩$ for every 1≤i≤n, and all other matrix entries zero.

Let $n\ge 1$, $x\in \{0,1{\}}^n$, and $p_0=0,p_i=x_1\oplus \cdots \oplus x_i$. On the basis $\{\mathrm{\mid }i,b⟩:0\le i\le n,b\in \{0,1\}\}$, put $H_x={\sum }_{i=1}^n{w}_i{\sum }_{b=0}^1(\mathrm{\mid }i-1,b⟩⟨i,b\oplus x_i\mathrm{\mid }+\mathrm{\mid }i,b\oplus x_i⟩⟨i-1,b\mathrm{\mid })\mathrm{.}$ Write $\mathrm{parity}(x)=p_n=x_1\oplus \cdots \oplus x_n$. The basis permutation $V_x\mathrm{\mid }i,b⟩=\mathrm{\mid }i,b\oplus p_i⟩$ conjugates $H_x$ to two copies of $H_0$. The counting identity proved below gives $H_0=(2\mathrm{/}n)J{\mathrm{\mid }}_{{\mathcal{S}}_n}$, under the isometry $\mathrm{\mid }i⟩\mapsto \mathrm{\mid }{D}_i^n⟩$. Consequently $\mathrm{\parallel }{H}_x{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 1$ and $e^{-i{H}_x\pi n\mathrm{/}2}\mathrm{\mid }0,0⟩=(-i{)}^n\mathrm{\mid }n,\mathrm{parity}(x)⟩\mathrm{.}$

Let $H$ be a finite-dimensional complex inner-product space, let $K=K^{\ast }$ on $H$, and let $\alpha >0$ satisfy $\mathrm{\parallel }K{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \alpha$. Put $A=K\mathrm{/}\alpha$. Let $U$ be a unitary on an ancilla-system space $H_A\otimes H$, let $J:H\to H_A\otimes H$ be the isometry $Jv=\mathrm{\mid }{0}^a⟩\otimes v$, and let $\mathrm{\Pi }=J{J}^{\ast }$. An exact Hermitian block encoding is the data $(U,J,\alpha )$ with $J^{\ast }UJ=A$. The matrix $K$ is Hermitian; $U$ itself need not be Hermitian.

The signal-register reflection is $R_{\mathrm{\Pi }}=2\mathrm{\Pi }-I$. The access record lists, separately, each supplied call to $U$, $U^{\ast }$, controlled-$U$, controlled-$U^{\ast }$, and $R_{\mathrm{\Pi }}$, together with their circuit, query, gate, width, ancilla, precision, and classical-generation costs from Block-encoding oracle and implementation cost model and Circuit-family and computation cost model. A state description or block matrix alone supplies none of these calls. A controlled reflection is also separate. Any PREPARE, SELECT, sparse-location, value, or coefficient operation used by a construction is a separately supplied, reversible interface with its inverse and cost recorded.

Here is the standard-form qubiterate for this access instance. Add a flag qubit and define $\tilde{U}=\mathrm{\mid }0⟩⟨0\mathrm{\mid }\otimes U+\mathrm{\mid }1⟩⟨1\mathrm{\mid }\otimes U^{\ast }$, $J^{\mathrm{\prime }}v=\mathrm{\mid }+⟩\otimes Jv$, $S=X\otimes I$, $F=S\tilde{U}$, and $W_{\mathrm{q}}=(2J^{\mathrm{\prime }}{J}^{\mathrm{\prime }\ast }-I)F$. Implementing $\tilde{U}$ requires the separately declared controlled-$U$ and controlled-$U^{\ast }$ calls; $S$, the preparation of $\mathrm{\mid }+⟩$, and the reflection about $\mathrm{ran}(J^{\mathrm{\prime }})$ also have declared costs. Qubitization lifts scalar QSP ↗ proves its compressed block and spectral relation.

For the QSVT simulation sequence, the signal operations are the alternating $U,U^{\ast }$ calls interleaved with the projector phases $e^{i\varphi (2\mathrm{\Pi }-I)}$ from QSP signal matrix and ordered phase sequence. Their exact phase list, parity, real-polynomial extraction, controls, inverse calls, and phase-synthesis precision are part of the supplied circuit description. The scalar polynomial pairs must satisfy Admissible polynomial pair for Hermitian-reflection QSP; singular-value transformations use the convention of Odd and even singular-value transforms.

For a finite Hermitian $H$ with exact block-encoding normalization $\alpha >0$, $\mathrm{\parallel }H{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \alpha$, and real time $t$, put $\tau =\alpha t$. On $x\in [-1,1]$ the scalar target is $f_{\tau }(x)=\exp (-i\tau x)$; if $H{\psi }_{\lambda }=\lambda {\psi }_{\lambda }$, then $f_{\tau }(\lambda \mathrm{/}\alpha )=\exp (-it\lambda )$, the eigenvalue of the finite matrix evolution Finite Hermitian matrix dynamics.

Define the Chebyshev polynomials by $T_0(x)=1$, $T_1(x)=x$, and $T_{k+1}(x)=2x{T}_k(x)-T_{k-1}(x)$ for $k\ge 1$. For $k\ge 0$, define the Bessel coefficients used here by the series $J_k(\tau )={\sum }_{j=0}^{\mathrm{\infty }}\frac{(-1{)}^j(\tau \mathrm{/}2{)}^{2j+k}}{j!(j+k)!}\mathrm{.}$ For $\tau \mathrm{\ne }0$, the ratio of consecutive absolute summands is ${\tau }^2\mathrm{/}[4(j+1)(j+k+1)]\to 0$, so the series converges absolutely. If $\tau =0$, at most its $j=0,k=0$ summand is nonzero, so it also converges absolutely. Thus the series defines $J_k(\tau )$ before any estimate is used. The exponential uses the series convention of The complex exponential by its power series, whose absolute convergence is supplied by The complex exponential series converges absolutely for every complex argument. This definition specifies the target and coefficient series; it does not assert a Jacobi–Anger expansion or a truncation bound. A real QSP or QSVT theorem alone does not implement this full complex, non-parity target; the finite even/odd combination, complementary-polynomial certificates, normalization, and controlled relative phase are separate operations in the binding simulator.

Let $(U,J,\alpha )$ be an exact Hermitian block encoding from Qubitization access model, and choose an orthonormal eigenbasis $K{\psi }_j={\lambda }_j{\psi }_j$. Put $x_j={\lambda }_j\mathrm{/}\alpha$ and $s_j=\sqrt{1-x_j^2}$. For $\mathrm{\mid }{x}_j\mathrm{\mid }<1$, define ${\eta }_j=(I-\mathrm{\Pi })UJ{\psi }_j\mathrm{/}{s}_j,{\tilde{\eta }}_j=(I-\mathrm{\Pi })U^{\ast }J{\psi }_j\mathrm{/}{s}_j\mathrm{.}$ The ${\eta }_j$ are orthonormal in $\ker \mathrm{\Pi }$, as are the ${\tilde{\eta }}_j$. In the paired input basis $(J{\psi }_j,{\tilde{\eta }}_j)$ and output basis $(J{\psi }_j,{\eta }_j)$, $U$ has matrix $\left(\begin{array}{cc}{x}_j& s_j\\ s_j& -x_j\end{array}\right)\mathrm{.}$ The unitary $U^{\ast }$ maps in the reverse direction by the same matrix. If $\mathrm{\mid }{x}_j\mathrm{\mid }=1$, the complement is absent and $UJ{\psi }_j=x_{j}J{\psi }_j=U^{\ast }J{\psi }_j$; no division by zero is used. The value $x_j=0$ is an ordinary two-dimensional signal plane.

Let $(U,J,\alpha )$ be an exact Hermitian block encoding of $K$, with $K=K^{\ast }$ and $\mathrm{\parallel }K{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \alpha$. The qubiterate $W_{\mathrm{q}}$ of Qubitization access model has, on each eigenvalue $x=\lambda \mathrm{/}\alpha$, a two-dimensional invariant signal space on which it is a rotation with eigenvalues $e^{\pm i\arccos x}$; at $x=\pm 1$ the space collapses to the corresponding eigenline.

For a phase list $\mathrm{\Phi }=({\varphi }_0,\dots ,{\varphi }_d)$, alternating $U,U^{\ast }$ calls and projector phases $e^{i\varphi (2\mathrm{\Pi }-I)}$ acts on each paired signal space as the scalar Hermitian-reflection QSP sequence $U_{\mathrm{\Phi }}(x)$ of QSP signal matrix and ordered phase sequence. If $P_{\mathrm{\Phi }}$ is its upper-left polynomial, the clean compressed block is $P_{\mathrm{\Phi }}(K\mathrm{/}\alpha )$ on all eigenspaces simultaneously, with the endpoint and null directions handled by the same polynomial evaluation. Admissible phases are supplied by Constructive factorization of an admissible QSP polynomial pair; translating to the SU(2) convention carries the scalar $i^d$, which remains a relative phase under control.

Any quantum query algorithm that, on every $x\in \{0,1{\}}^n$, outputs $\mathrm{parity}(x)$ with error at most $1\mathrm{/}3$ using the coherent XOR oracle for $x$ makes at least $n\mathrm{/}2$ oracle queries.

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.