HHL finite sine-window phase-estimation algorithm

Input a self-adjoint $H$ with $\mathrm{\parallel }H\mathrm{\parallel }\le 1$, a unit input state $\mathrm{\mid }b⟩$ supported only on eigenvalues satisfying $1\mathrm{/}\kappa \le \mathrm{\mid }\lambda \mathrm{\mid }\le 1$, and a supplied finite exact representation of the cutoff $\kappa \ge 1$ that supports certified arithmetic and rational comparisons. Supply costed $B,B^{†}$ and controlled/inverse simulation access as in HHL state-preparation and simulation access model. The accuracy and failure inputs are exact rational values $ϵ=p_{ϵ}\mathrm{/}{q}_{ϵ}$ and $\rho =p_{\rho }\mathrm{/}{q}_{\rho }$, with positive binary-encoded integers and $0<p_{ϵ}\le q_{ϵ}$, $0<p_{\rho }<q_{\rho }$. Rectangular systems $A:{\mathbb{C}}^n\to {\mathbb{C}}^m$ use Hermitian dilation for a rectangular linear system: choose a supplied rational scale $\mathrm{\Lambda }\ge \mathrm{\parallel }{H}_A\mathrm{\parallel }$, use $H=H_A\mathrm{/}\mathrm{\Lambda }$, and set $\kappa =\mathrm{\Lambda }\mathrm{/}\gamma$ from the QLSP support gap $\gamma$. The QLSP definition supplies ${\sigma }_j\ge \gamma$ whenever the left singular coefficient of $b$ is nonzero; the dilation eigenvalues on this input support are $\pm {\sigma }_j\mathrm{/}\mathrm{\Lambda }$, so $1\mathrm{/}\kappa \le \mathrm{\mid }\lambda \mathrm{\mid }\le 1$. On $({\mathbb{C}}^m\otimes W)\oplus ({\mathbb{C}}^n\otimes W)$ prepare the normalized codomain-supported input $(b\mathrm{/}\mathrm{\parallel }b\mathrm{\parallel },0)$ with the tagged preparation $B_A:=B\oplus I_{{\mathbb{C}}^n\otimes W}$. Implement its $B$ block with the supplied tag-controlled form of $B$ and charge that controlled preparation cost. The QLSP promise $b\in \mathrm{ran}(A)$ removes the kernel component, and the output is tagged in the domain summand. All parameter comparisons, reversible arithmetic and finite-precision synthesis use the separately charged routines in the access model. The algorithm is the finite OP5 program:

1. Apply the supplied $B$ (or $B_A$ for a rectangular system) to prepare the input and its fixed work state, set $t_0=2048\kappa \mathrm{/}ϵ$, choose the least power of two $T\ge 8(t_0+1)$ by certified comparisons, and let $L={\log }_{2}T$. Initialize the phase register to $\mathrm{\mid }{0}^L⟩$ in big-endian order $q_{L-1}\cdots q_0$. This carrier chooses OP5's explicit table variant for preparing Finite sine-window phase state. Build the complete binary prefix tree on the $T$ leaves. At each level $\mathrm{\ell }=0,\dots ,L-1$ and for each interval node $[a,b)$ at that level, put $m=(a+b)\mathrm{/}2$ and compute the child masses $W_T(a,m)$ and $W_T(m,b)$ from the formula in Sine-window normalization and positive prefix weights. Store $r=W_T(a,m)\mathrm{/}{W}_T(a,b)$ and apply $R_y(2\arcsin \sqrt{r})$ to wire $q_{L-1-\mathrm{\ell }}$, controlled on the preceding $\mathrm{\ell }$ wires matching the path to $[a,b)$; encode bit $1$ as the left child and bit $0$ as the right child. The root has no controls. Thus the ideal circuit prepares $\mathrm{\mid }{\mathrm{\Psi }}_T⟩$ by Operator error for the finite sine-prefix rotation table. Put ${ϵ}_{\mathrm{\Psi }}=ϵ\mathrm{/}(4096\kappa )$. Each nonempty mass is at least $T^{-2}$ by Sine-window normalization and positive prefix weights. Use certified interval arithmetic with absolute mass error at most ${ϵ}_{\mathrm{\Psi }}^2\mathrm{/}({10}^6{L}^2{T}^4)$; refine until each stored angle and its finite gate synthesis together give controlled-rotation operator error at most ${ϵ}_{\mathrm{\Psi }}\mathrm{/}(100T)$. The cases $r=0$ and $r=1$ use the identity and $\pi$ rotations, respectively. Store each other angle with at least $\lceil {\log }_2(100\pi T\mathrm{/}{ϵ}_{\mathrm{\Psi }})\rceil +2$ bits. There are $T-1$ rotations; Operator error for the finite sine-prefix rotation table bounds their total operator error by ${ϵ}_{\mathrm{\Psi }}\mathrm{/}100$ from the displayed combined per-node operator tolerance. The table contains $O(T\log (T\mathrm{/}{ϵ}_{\mathrm{\Psi }}))$ bits and $T-1$ controlled rotations. Charge its one-time construction/data cost $G_{\mathrm{\Psi }}(T,{ϵ}_{\mathrm{\Psi }})$ and each forward/inverse preparation cost $C_{\mathrm{\Psi }}(T,{ϵ}_{\mathrm{\Psi }})$ from HHL state-preparation and simulation access model, including reversible lookup, control and finite gate synthesis. Thus the sine-preparation unitary and its inverse each have operator error at most ${ϵ}_{\mathrm{\Psi }}$; this variant pays linear-in-$T$ table and rotation resources rather than assuming a loaded amplitude table.

2. In either the original full-space or alternative clean-workspace simulation mode, initialize all simulator work in zero and retain it coherently. For $j=0,\dots ,L-1$, set $t_j=2^j{t}_0\mathrm{/}T$ and allocate ${\eta }_j=ϵ\mathrm{/}(8192\kappa L)$ to both its forward controlled call $S_H(t_j,{\eta }_j)$ and its reverse call. Apply $S_H(t_j,{\eta }_j)$ to the system controlled on wire $q_j$ being $1$, and act as identity on its $0$ branch. In the declared order $q_{L-1}\cdots q_0$, a phase label $\tau$ has bits $x_j$ with $\tau ={\sum }_{j=0}^{L-1}{2}^j{x}_j$, so the ideal controlled list applies $e^{+iH\tau t_0\mathrm{/}T}$. Apply the negative-sign QFT, decode $y$ to signed $k=y$ for $y<T\mathrm{/}2$ and $k=y-T$ otherwise, and set $\tilde{\lambda }=2\pi k\mathrm{/}{t}_0$. The total forward evolution time is ${\sum }_{j<L}{t}_j=t_0(1-1\mathrm{/}T)<t_0$, and the sum of the $2L$ simulation error allocations is $ϵ\mathrm{/}(4096\kappa )$. This uses the signed convention in Signed phase decoding has no alias on the promised spectrum.

3. Reversibly compute the flag angles and sign from $\tilde{\lambda }$ using Odd-well and even-ill reciprocal filter. Use the two-qubit computational basis $\mathrm{\mid }{q}_1{q}_0⟩$ with labels $\mathrm{\mid }\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{g}⟩=\mathrm{\mid }00⟩$, $\mathrm{\mid }\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}⟩=\mathrm{\mid }01⟩$, $\mathrm{\mid }\mathrm{i}\mathrm{l}\mathrm{l}⟩=\mathrm{\mid }10⟩$, and unused label $\mathrm{\mid }11⟩$. Write $p=\mathrm{\mid }{f}_{\kappa }(\tilde{\lambda })\mathrm{\mid }$, $r=\sqrt{1-p^2}$, $\alpha =2\arcsin p$, and $\beta =2\arcsin (g_{\kappa }(\tilde{\lambda })\mathrm{/}r)$. These are defined at every decoded grid point because The reciprocal filter defines valid three-outcome amplitudes gives $p\le 1\mathrm{/}2$, $0\le g\le 1\mathrm{/}2$, and $r\ge \sqrt{3}\mathrm{/}2$, so $g\mathrm{/}r\le 1\mathrm{/}\sqrt{3}<1$. First apply $R_y(\alpha )$ to $q_0$ conditioned on $q_1=0$, acting as identity on the $q_1=1$ subspace. Next apply $R_y(\beta )$ to $q_1$ conditioned on $q_0=0$, acting as identity on the $q_0=1$ subspace. Here $R_y(\theta )=\exp (-i\theta Y\mathrm{/}2)$ with the exact convention and unitary formula of Exact one-qubit gates and rotations and Pauli formula for an axis rotation. Finally apply $D_s=\mathrm{diag}(1,s,1,1)$ in the ordered flag basis, where $s=-1$ if $\tilde{\lambda }<0$ and $s=+1$ otherwise (in particular at zero, where $f_{\kappa }(0)=0$). The resulting full flag unitary is $D_s{G}_{02}(\beta )G_{01}(\alpha )$: the two conditional rotations act as $R_y$ on the indicated two-label subspaces and as identity on their orthogonal complements, and $D_s$ is diagonal unitary. All three factors fix the unused label $\mathrm{\mid }11⟩$. On $\mathrm{\mid }00⟩$ the product gives $h(\tilde{\lambda })\mathrm{\mid }00⟩+f_{\kappa }(\tilde{\lambda })\mathrm{\mid }01⟩+g_{\kappa }(\tilde{\lambda })\mathrm{\mid }10⟩$, since $\cos (\beta \mathrm{/}2)=h\mathrm{/}r$ and $\sin (\beta \mathrm{/}2)=g\mathrm{/}r$. Uncompute the arithmetic. Synthesize the phase-controlled map with uniform operator error at most ${\eta }_R:=ϵ\mathrm{/}(4096\kappa )$, charged through $C_{\mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}}$ and $C_{\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}}$.

4. Reverse the QFT, every actual controlled simulation circuit, and sine preparation, retaining the flag and all simulator work. In clean-workspace mode the ideal trajectory has this work in zero; Unitary hybrids on a preserved clean-work subspace bounds the complete attempt on that ideal trajectory without assuming actual intermediate work is clean. This gives a unitary flagged preparation $V$ and its exact circuit inverse $V^{†}$. Let ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ be the well-flag projection in Hermitian mode and the product of the well-flag projection and tagged domain projection in rectangular mode; these two projections act on distinct registers and commute. Let $p=\mathrm{\parallel }{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}V\mathrm{\mid }0⟩{\mathrm{\parallel }}^2$. Apply the finite capped amplification procedure proved in Finite capped amplification succeeds with a supplied lower bound with success projection ${\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$, lower bound $p_{\mathrm{l}\mathrm{o}\mathrm{w}}=1\mathrm{/}(16{\kappa }^2)$ and failure target $\rho$. Its success reflection and verification test both the well flag and the domain tag in rectangular mode; charge their actual costs to $C_{\mathrm{r}\mathrm{e}\mathrm{f}}$ and $C_{\mathrm{v}\mathrm{e}\mathrm{r}}$. Measure $\{{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},I-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\}$ and return the conditional state, tagged output and success bit on success; return FAIL otherwise.

The circuit uses no uniform-register phase-tail estimate: its phase distribution is the sine-window kernel proved in Second moment of the signed sine-window phase kernel. Its $G_{\mathrm{\Psi }},C_{\mathrm{\Psi }},C_{\mathrm{s}\mathrm{i}\mathrm{m}},C_{\mathrm{Q}\mathrm{F}\mathrm{T}}^{+\mathrm{/}-},C_{\mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}}$, reflection, verification and $B\mathrm{/}{B}^{†}$ costs remain separate inputs.