Block-Encoding Linear Systems and Variable-Time Amplification

Let $0<\eta <1$, $0<g\le t$, and $s>0$ satisfy $s+t\le 1$. Let $S$ be an odd real polynomial such that $\mathrm{\mid }S(y)\mathrm{\mid }\le 1$ for $y\in [-1,1]$ and $\mathrm{\mid }S(y)-\mathrm{sgn}(y)\mathrm{\mid }\le \eta \mathrm{/}2$ whenever $y\in [-1,1]$ and $\mathrm{\mid }y\mathrm{\mid }\ge g$. Define $R(x)=\frac{1-\eta }{2}(S(x+t)+S(t-x))+\frac{\eta }{2},D(x)=1-\frac{S(x+t)+S(t-x)}{2}$ for $x\in [-s,s]$. Then $R$ and $D$ are even polynomials, each has degree at most $\mathrm{deg}S$, and $0\le R(x)\le 1$ for all $x\in [-s,s]$. On $\mathrm{\mid }x\mathrm{\mid }\le t-g$, $1-\eta \le R(x)\le 1$ and $\mathrm{\mid }D(x)\mathrm{\mid }\le \eta \mathrm{/}(2(1-\eta ))$. On $\mathrm{\mid }x\mathrm{\mid }\ge t+g$, $0\le R(x)\le \eta$ and $\mathrm{\mid }D(x)-1\mathrm{\mid }\le \eta \mathrm{/}(2(1-\eta ))$. Globally, $-\frac{\eta }{2(1-\eta )}\le D(x)\le 1+\frac{\eta }{2(1-\eta )}\mathrm{.}$ The inner or outer interval may be empty, in which case its corresponding assertion is vacuous.

With $a=1+t_0$, the OP1A expression $1+(S((x-t_0)\mathrm{/}a)-S((x+t_0)\mathrm{/}a))\mathrm{/}2$ is the $D$ above after substituting $x\mathrm{/}a$ for the lemma variable and $t_0\mathrm{/}a$ for $t$. The lemma domain uses $s=1\mathrm{/}a$, so $s+t=1$, and $g=\delta \mathrm{/}(4a)$ gives $t=3g$; its inner and outer thresholds are $t-g=\delta \mathrm{/}(2a)$ and $t+g=\delta \mathrm{/}a$. For OP1A, take $\eta =2v$ with its parameter $v=e\mathrm{/}(1000P_{\max })$; then the required approximation error is $\eta \mathrm{/}2=v$. Subject to the OP1A SignPoly certificate proving that error and the bound $\mathrm{\mid }S\mathrm{\mid }\le 1$, all evaluations stay on $[-1,1]$, where OP1A states those properties. It does not prove the separate Chebyshev interpolation, inverse approximation, Bernstein-refinement termination, or bit-cost obligations of OP1A. The displayed formula in Gilyén et al. Lemma 29 is not invoked here.

A finite coherent variable-time algorithm has a finite family of stopping times $0<t_1<\cdots <t_m=T_{\max }$, a designated output space, and a finite clock/step register. A run is unfinished at stage $j$ if it has not entered a stopping subspace by $t_j$; otherwise it is stopped. The stopping subspaces are pairwise orthogonal, and the output register labels each stopped branch as good or bad. Every later stage is controlled on the unfinished projector, so a stopped branch is not advanced. Admissibility requires the first-stop subspaces to exhaust the reachable state at $T_{\max }$ for every allowed input; no branch remains unfinished after the final stage. The input specifies each stage unitary, its inverse and every controlled form used, and the gate/query cost for each.

For a normalized input state, let $p_i$ be the Born probability mass in the subspace that first stops at $t_i$. These are nonnegative masses of orthogonal subspaces whose sum is the reachable state at the final time, so $p_i\ge 0$ and ${\sum }_{i=1}^m{p}_i=1$. Define the root-mean-square stopping time $T_{\mathrm{a}\mathrm{v}}:={\left({\sum }_{i=1}^m{p}_i{t}_i^2\right)}^{1\mathrm{/}2}\mathrm{.}$ Let $p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}$ be the total Born probability of the good-output subspace. When $p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}>0$, the good output means the normalized conditional state of the declared good projector; it is defined only on that positive-probability branch. The mean stopping time ${\sum }_i{p}_i{t}_i$ is a different quantity and is not substituted for $T_{\mathrm{a}\mathrm{v}}$.

A measured adaptive procedure qualifies only if it has a finite coherent implementation with the same stopped/unfinished branch semantics and the required inverse/coherent access. Measurement records used to choose a circuit may be classical construction data; no intermediate measurement is inserted into a branch whose later inverse must erase that record. All stopping times, branch probabilities, reflections, inverses, controlled calls, and state preparation remain explicit resource inputs. Complexity statements use an actual normalized primitive-operation coordinate: positive counts are at least one, and the declared interval budgets include the preparation, controlled/inverse and input/selected-reflection operations used in the construction. Other weighted time coordinates may be recorded, but arbitrary uncharged subunit weights do not inherit logarithmic operation-count bounds.

A supplied-probability production regime must specify finite probability/schedule certificates rather than infer them from black-box unitary access. For $h+1\le n$ dyadic intervals indexed $j=0,\dots ,h$, initialize $s_{-1}=r_{-1}=1$ and require $p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}>0$. The original good-or-unfinished masses satisfy $1\ge s_{j-1}\ge s_j\ge p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}>0$ and $s_h=p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}$, so $q_j=r_{j-1}{s}_j\mathrm{/}{s}_{j-1}$ is defined. Supply odd multipliers $d_j=2k_j+1$ and certificates for the actual amplified selected masses satisfying $r_j\ge 1\mathrm{/}(16n)$ and $r_j\ge (1-2\mathrm{/}(5n))d_j^2{q}_j$; an unamplified interval has $d_j=1$ and $r_j=q_j$. Supply also a rational $\mathrm{\ell }$ with $r_h\mathrm{/}2\le \mathrm{\ell }\le r_h$. These are the finite schedule inequalities for the supplied-data production regime. Data may use exact rational/algebraic representations, certified rational enclosures with the stated valid inequalities, or a separately declared exact-real representation/comparison resource. The finite construction and verification cost $C_{\mathrm{b}\mathrm{u}\mathrm{i}\mathrm{l}\mathrm{d}}$ includes every oracle call used to acquire or certify probability information, as well as classical arithmetic, list generation and output costs. No zero-query method obtaining these data is assumed. A uniform regime without those certificates must instead state its supplied probability floor, confidence and complete estimation/production costs. Branch probabilities defined above remain valid analysis quantities even when they are unknown to the implementation.

Let $A:{\mathbb{C}}^n\to {\mathbb{C}}^m$ with $m,n\ge 1$, $0<\alpha$, and $0<\gamma \le \alpha$. The input is an exact or approximate $(\alpha ,a,{ϵ}_{\mathrm{B}\mathrm{E}})$ block encoding of $A$ under the access contract of Block-encoding oracle and implementation cost model, together with the QLSP state-output data of Quantum linear-systems state-output task. The latter means a supplied unitary prepares a normalized $\mathrm{\mid }b\mathrm{/}\mathrm{\parallel }b\mathrm{\parallel }\mathrm{\mid }⟩$ from a designated zero input, $b\in \mathrm{ran}A\setminus \{0\}$, the target is $A^{+}b\mathrm{/}\mathrm{\parallel }{A}^{+}b\mathrm{\parallel }$ on the domain register, and every singular vector with nonzero coefficient in $b$ has singular value at least $\gamma$.

Put $\bar{A}=A\mathrm{/}\alpha$ and $\delta =\gamma \mathrm{/}\alpha \in (0,1]$. The support-gap promise then says every nonzero supported singular value of $\bar{A}$ is at least $\delta$; it makes no promise about singular values in $(0,\delta )$ outside the support of $b$. In the QSVT branch below we use $\delta \le 1\mathrm{/}2$ and $0<ϵ\le \delta$ as additional algorithm inputs. The block-encoding approximation and all phase, inverse, controlled, reflection, and state-preparation access costs are separate input data. A finite polynomial or a matrix alone is not an oracle.

The QSVT target map is $(\delta \mathrm{/}2){\bar{A}}^{+}=(\gamma \mathrm{/}2)A^{+}$. It has the same normalized output on $b$ as $A^{+}$ because $\gamma \mathrm{/}2>0$. The scale conversion and nonzero normalization of this target are established by Normalization and nonzero success weight of the supported pseudoinverse target ↗.

Let $A_j:{\mathbb{C}}^n\to {\mathbb{C}}^n$ have exact $({\alpha }_j,a_j,0)$ block encodings $U_j$, let ${\beta }_j\mathrm{\ne }0$, and put $\mathrm{\Lambda }={\sum }_j\mathrm{\mid }{\beta }_j\mathrm{\mid }{\alpha }_j>0$. Set $a={\max }_j{a}_j$ and extend each component to the common ordered ancilla/system register by ${\tilde{U}}_j=I_{2^{a-a_j}}\otimes U_j$, with unused ancillas preceding its original ancillas. Let $P$ be a supplied unitary with $P\mathrm{\mid }0⟩={\sum }_j\sqrt{\mathrm{\mid }{\beta }_j\mathrm{\mid }{\alpha }_j\mathrm{/}\mathrm{\Lambda }}\mathrm{\mid }j⟩$, and let the separately supplied unitary SELECT act as ${\tilde{U}}_j$ with phase ${\beta }_j\mathrm{/}\mathrm{\mid }{\beta }_j\mathrm{\mid }$ on index $j$. With $W=P^{†}\mathrm{S}\mathrm{E}\mathrm{L}\mathrm{E}\mathrm{C}\mathrm{T}P$, the all-zero coefficient and component-ancilla block of $W$ is ${\sum }_j\frac{{\beta }_j}{\mathrm{\Lambda }}{A}_j\mathrm{.}$ This is a conditional matrix identity. It does not construct SELECT from an XOR-valued function oracle or assign a cost to any supplied operation.

In the block-encoded QLSP model, let $\mathrm{\mid }b⟩$ be the normalized codomain input, let $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \alpha$, and suppose $\mathrm{\mid }b⟩={\sum }_{j=1}^r{\beta }_j\mathrm{\mid }{u}_j⟩$ is supported on positive singular values ${\sigma }_j\ge \gamma >0$. Then $\frac{(\delta \mathrm{/}2){\bar{A}}^{+}\mathrm{\mid }b⟩}{\mathrm{\parallel }(\delta \mathrm{/}2){\bar{A}}^{+}\mathrm{\mid }b⟩\mathrm{\parallel }}=\frac{A^{+}\mathrm{\mid }b⟩}{\mathrm{\parallel }{A}^{+}\mathrm{\mid }b⟩\mathrm{\parallel }},{\parallel (\delta \mathrm{/}2){\bar{A}}^{+}\mathrm{\mid }b⟩\parallel }^2\ge \frac{{\delta }^2}{4},\delta =\gamma \mathrm{/}\alpha ,\bar{A}=A\mathrm{/}\alpha \mathrm{.}$ In particular the ideal inverse-branch success probability is positive and has the stated crude lower bound.

Input. An exact or approximate projected-unitary encoding of $\bar{A}=A\mathrm{/}\alpha$, its supplied inverse and every controlled form used, left/right singular-space projectors, a unitary preparing normalized $\mathrm{\mid }b⟩$ in the promised left singular space, rational $0<e\le \delta =\gamma \mathrm{/}\alpha \le 1\mathrm{/}2$, and explicit block, phase, reflection, state-preparation, arithmetic, and gate costs. The algorithm returns a success flag and the conditional right-space state, or the declared failure result.

Bare-gap generation branch (binding OP1A). Run the finite InversePoly($\delta,e$) construction in the binding OP1A section of research/quantum-algorithms-planning/operational-contracts.md: set ${\kappa }_0=2\mathrm{/}\delta$, $u=e\mathrm{/}(100\delta )$, $b=\lceil {\kappa }_0^2\ln ({\kappa }_0\mathrm{/}u)\rceil$, and $J=\lceil \sqrt{b\ln (4b\mathrm{/}u)}\rceil$ using certified upper endpoints. Generate the finite binomial sums $a_j=4(-1{)}^j{2}^{-2b}{\sum }_{i=j+1}^b\left(\genfrac{}{}{0px}{}{2b}{b+i}\right)$ and $P(x)=(\delta \mathrm{/}2){\sum }_j{a}_j{T}_{2j+1}(x)$ by the Chebyshev recurrence. Retain $P_{\max }=1+2\delta (J+1)$ as the declared coarse bound.

Run SignPoly(g,v) from OP1A with $t=3\delta \mathrm{/}4$, $a_0=1+t$, $g=\delta \mathrm{/}(4a_0)$, and $v=e\mathrm{/}(1000P_{\max })$. The routine evaluates the declared erf Chebyshev interpolant with its finite node, tail, coefficient-rounding, and division steps and returns its rational odd polynomial and ellipse/tail certificate. Form $C_{\mathrm{c}\mathrm{u}\mathrm{t}}(x)=1+\frac{S((x-t)\mathrm{/}{a}_0)-S((x+t)\mathrm{/}{a}_0)}{2},p(x)=\frac{P(x)C_{\mathrm{c}\mathrm{u}\mathrm{t}}(x)}{1+e\mathrm{/}10}\mathrm{.}$ Generate every product coefficient with the stated total rounding budget. Check exact odd parity and degree. Run the OP1 exact critical-point check for $\mathrm{\mid }p(x)\mathrm{\mid }\le 1$ on $[-1,1]$. Construct the reciprocal certificate on $[\delta ,1]$ by the specified dyadic rational partitions and nonnegative Bernstein coefficients for both $ex\pm (xp(x)-\delta \mathrm{/}2)$. Refine precision when intervals are undecided; on an actually failed certificate halve $u,v$ and regenerate. Any declared cap returns CONSTRUCTION_TIMEOUT; any failed exact certificate returns its stated non-success branch.

On a successful polynomial certificate, set the rational phase-synthesis tolerance to $e\mathrm{/}100$ and call Real bounded-polynomial QSP phase synthesis in efficient-numerical mode with the checked real odd polynomial $p$, its degree, and that tolerance. Retain the exact pre-angle target $p_0$ produced by its deterministic shrink/round rule, complementary pair $B,C$, exact phase-scalar descriptors, and numerical phase certificates. Charge its target shrink/round error and numerical-angle/compiler errors to the separate phase term in the supplied error budget. Before any QSVT call, form the ordered matrix product from the returned exact phase-scalar descriptors, using the recurrence in QSP signal matrix and ordered phase sequence and coefficient arithmetic in the basis $\mathbb{C}[x]\oplus \sqrt{1-x^2}\mathbb{C}[x]$. Compare its four entries coefficientwise with $\left(\begin{array}{cc}{p}_0+iB& \sqrt{1-x^2}C\\ (-1{)}^{d+1}\sqrt{1-x^2}{C}^{\ast }& (-1{)}^d(p_0-iB)\end{array}\right)\mathrm{.}$ This finite exact check validates the phase list actually returned by the peeling routine, rather than relying on existence of some phase list. Charge its arithmetic and certificate output with phase generation. If any comparison fails, return PHASE_PRODUCT_ERROR with the generated polynomial record and mismatch witness, and do not execute QSVT. Only after the check passes may the execution use the returned phase list. The subsequent rational-angle and optional compiler errors remain separately bounded by the returned phase certificates and the supplied error budget; the exact product check does not replace those bounds. No exact phase rotation or finite-basis compiler is free.

Execution. Execute the QA24 odd QSVT sequence on the adjoint projected-unitary encoding of $\bar{A}$, with left and right projectors swapped, using the generated phase list and the separately supplied controlled/inverse access. The ideal supported singular-value multiplier is $p(\sigma \mathrm{/}\alpha )$; the intended target is $(\delta \mathrm{/}2){\bar{A}}^{+}\mathrm{\mid }b⟩=(\gamma \mathrm{/}2)A^{+}\mathrm{\mid }b⟩$. Apply the declared success projector and return its conditional state only on a positive-probability success branch. The scalar polynomial, block-encoding, phase-synthesis, and circuit-implementation errors are separate terms in the supplied error budget.

An optional certified-input branch accepts finite polynomial, phase, and reciprocal-certificate lists; it verifies their parity, interval, identity, and Bernstein checks before execution and returns INVALID if a check fails. It does not prove that bare rational inputs can be converted into such a certificate.

This is the binding OP1A procedure, not merely an existence-based choice of polynomial. lem-qa-27-even-sign-window proves a bounded-window estimate for its declared sign approximant and shows why the printed formula of Gilyén et al. Lemma 29 is unnecessary for this cutoff. The separate polynomial-degree result establishes its uncapped termination, interpolation, coefficient/cutoff margins, certificate refinement, degree, and the exact link from the returned phase list to its completed polynomial pair. Finite caps retain their timeout result. Exact-root/phase generation and implementation use the actual QA23 contract; all generation, comparison and arithmetic bit costs stay separately charged, with no total bit-time bound inferred from this Definition.

Fix $N\ge 1$, a sparsity bound $d\ge 1$, and an $N\times N$ Hermitian matrix $A$ with $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 1$. The sparse QLSP promises that the normalized input state $\mathrm{\mid }b⟩$ is supported on eigenvectors with $\mathrm{\mid }\lambda \mathrm{\mid }\ge 1\mathrm{/}\kappa$ for some declared $\kappa \ge 1$; equivalently these are singular values at least $1\mathrm{/}\kappa$. The QLSP target is the normalized state proportional to $A^{+}b$ from Quantum linear-systems state-output task. The zero matrix is excluded by the nonzero supported-state promise.

The access input supplies the following reversible operations and records every forward, inverse, and controlled call separately.

1. Row location. For each row $i$ and slot $\mathrm{\ell }\in [d]$, a total finite function $f(i,\mathrm{\ell })$ returns the $\mathrm{\ell }$th nonzero column in that row, or a designated invalid sentinel for a padded slot. The input supplies a reversible in-place row permutation implementing $(i,\mathrm{\ell })\mapsto (i,f(i,\mathrm{\ell }))$ on valid slots, together with a completion on every padded basis input and its inverse.
2. Reverse location. For each valid nonzero entry $(i,j)$, a reversible map returns its unique slot $\mathrm{\ell }$. Its completion on invalid and padded inputs is specified and charged. This reverse map is an explicit capability; it is not inferred from forward XOR access.
3. Values. A finite-precision reversible oracle returns the encoded complex entry $A_{ij}$ at valid pairs and zero at invalid pairs. Its value precision and the induced matrix approximation error are stated separately.
4. Input preparation. A supplied unitary $B$ prepares $\mathrm{\mid }b⟩$ from a designated zero state. $B$, $B^{†}$, controlled calls, and their circuit/query/gate costs are explicit. No state loading, QRAM, or coordinate list is free.

The paper's row-location and value XOR oracles may be included as component access, but they do not by themselves certify the in-place reversible permutations, reverse map, or their implementation costs. In particular Sparse Hamiltonian row and value oracles defines total XOR row-location and value maps; this item requires the stronger reversible-location capabilities above whenever the sparse block-encoding construction is used. The parameter $d$, support condition number $\kappa$, value precision, oracle query count, gate cost, and classical data cost remain separate.

For rational $0<e\le \delta \le 1\mathrm{/}2$, the uncapped bare-gap OP1A construction terminates and returns an odd real polynomial $p$ of degree $O({\delta }^{-1}\log (1\mathrm{/}e))$ satisfying $\mathrm{\mid }p(x)\mathrm{\mid }\le 1$ on $[-1,1]$, $p(0)=0$, and ${\sup }_{x\in [\delta ,1]}\mid p(x)-\frac{\delta }{2x}\mid \le e\mathrm{.}$ For a normalized block $\bar{A}=A\mathrm{/}\alpha$ whose supported singular values lie in $\{0\}\cup [\delta ,1]$, this gives the singular-space approximation $p^{\mathrm{S}\mathrm{V}}({\bar{A}}^{†})\approx (\delta \mathrm{/}2){\bar{A}}^{+}=(\gamma \mathrm{/}2)A^{+}$ on the supported input, where $\delta =\gamma \mathrm{/}\alpha$.

In the uncapped phase-generation route, the exact phase list returned by QSVT regularized pseudoinverse transformation has ordered QSP product equal to the completed polynomial pair used by its generator, and the algorithm's coefficientwise product check passes before QSVT execution. Numerical angle and compiler errors remain subject to their separate certificates; a failed exact product check returns PHASE_PRODUCT_ERROR and is never treated as a successful transform.

For every integer $k\ge 2$, put $M=2^k$. There is a deterministic uniformly generated finite reversible circuit with the action

$\mathrm{\mid }y,z,0^w⟩⟼\mathrm{\mid }y,z<mrow><mi\; mathvariant="normal">X</mi><mi\; mathvariant="normal">O</mi><mi\; mathvariant="normal">R</mi></mrow>a_M(y),0^w⟩$

for every $k$-bit integer $0\le y<M$ and every $(2k+1)$-bit target $z$, where $a_M(y)$ is an integer satisfying

$0\le a_M(y)\le M^2,a_M(0)=0,\mid \frac{a_M(y)}{M^2}-{\sin }^2\left(\frac{\pi y}{M}\right)\mid \le \frac{3}{4M^2}\mathrm{.}$

Circuit generation time, gate count in $X$, CNOT and Toffoli, serial depth, and clean workspace are all polynomial in $k$. The identity holds on arbitrary coherent inputs and with finite reference registers. Its actual inverse and coherent controls have the same polynomial resource order. The algorithm uses only bounded exact integer/rational arithmetic with fixed loop counts depending on $k$; it performs no real equality test or equality-dependent precision refinement. The output encodes the rational $a_M(y)\mathrm{/}{M}^2$ by its numerator and the known fixed denominator.