Block Encodings and QSVT

A block encoding replaces direct access to a generally nonunitary operator by a unitary whose action between two declared signal subspaces is the normalized operator. Quantum singular-value transformation (QSVT) then gives the central result: for a degree-$d$ admissible polynomial, one can transform the exposed singular values using exactly $d$ calls to the encoded unitary or its inverse. That statement is conditional on executable coherent access, a declared normalization, implementable projector phases, inverse and any controlled calls, a globally bounded parity-compatible polynomial, a synthesized and verified phase list, and an explicit output and success contract. A matrix written on paper is not a block encoding, and a block-encoding query theorem is not by itself an end-to-end runtime or advantage theorem.

Required background. Quantum Oracles supplies complete coherent interfaces, inverse and control capabilities, full-space action, and query conventions. Singular Value Decomposition supplies left and right singular vectors, zero singular subspaces, rank, and the Moore–Penrose pseudoinverse.

Helpful background. The chapter guide sets the claim discipline, Algorithmic Primitives gives a compact pattern-level preview, and Qubitization and Quantum Signal Processing owns the Hamiltonian-specialized signal chain and its phase-convention workflow.

The Projected-Unitary Encoding Problem

Quantum circuits are unitary, whereas matrices used in optimization, simulation, data analysis, and linear algebra may be rectangular, non-normal, rank deficient, or contractive. The access problem is therefore not merely how to write a matrix $A$, but how to realize a coherent circuit whose declared input and output subspaces expose $A$ while specifying every operation later algorithms may call. Let $U$ act on a finite-dimensional ambient Hilbert space, and let $\Pi$ and $\widetilde\Pi$ be orthogonal projectors onto the input and output signal spaces. The projected map is

$$B:=\widetilde\Pi U\Pi.$$

As an ambient operator this compression is an endomorphism, but the encoding restricts and identifies it as $B:\operatorname{im}\Pi\to\operatorname{im}\widetilde\Pi$. Because it is a compression of a unitary, $\lVert B\rVert\leq1$. An encoding of a target $A$ declares a positive scale $\alpha$ and arranges $B=A/\alpha$, exactly or approximately, under that identification. Keep the input and output roles explicit, and use distinct projectors when the declared signal spaces differ, especially for a genuinely rectangular map. Non-normality alone does not require $\Pi\ne\widetilde\Pi$ for a square map. Replacing unequal projectors by one anonymous ancilla condition can erase the typing needed to state the odd singular-value transform.

The projectors need not have equal rank. One may describe them through isometries $V_R:\mathbb C^n\to\mathcal H$ and $V_L:\mathbb C^m\to\mathcal H$, with $\Pi=V_RV_R^\dagger$, $\widetilde\Pi=V_LV_L^\dagger$, and matrix representative $V_L^\dagger U V_R$. This makes basis choices and dimensions explicit while leaving the ambient completion of $U$ nonunique. QSVT depends only on the declared projected access and the ability to phase its signal projectors, but implementation cost can depend strongly on that completion. Two unitaries exposing the same selected matrix are therefore mathematically interchangeable for the ideal transform and operationally different once controls, inverses, and gates are counted.

The access promise must be operational. It names registers, dimensions, the full unitary or an implementing circuit, inverse access, controlled access when used, and the cost of the reflections or phase rotations about both signal spaces. It also distinguishes three outputs: an encoded operator that can be queried coherently, a heralded state proportional to $A\lvert\psi\rangle$, and classical estimates obtained only after measurement. The projected-unitary framework developed by Gilyén, Su, Low, and Wiebe makes those distinctions part of the theorem rather than post-processing folklore.

The Ten-Field Block-Encoding and QSVT Claim Record

A useful claim is short enough to audit but complete enough to reproduce. Fill every field below; write a reasoned N/A when a field genuinely does not apply. A complexity statement without the first four fields has not yet specified an input model, and one without the last four has not yet specified an algorithmic output.

1. Target operator and domain. Give the linear map, its input and output dimensions, and the promised family of instances. State whether it is Hermitian, rectangular, sparse, or rank deficient when that affects the construction.
2. Encoding and normalization. State whether the access is projected-unitary or a standard block encoding, give $\alpha$, the ancilla count, and the selected-block error in a named norm. For an exact encoding verify $\alpha\geq\lVert A\rVert$.
3. Projectors and registers. Define $\Pi$ and $\widetilde\Pi$, register order, signal dimensions, and all zero padding. A diagram is optional; an unambiguous tensor-factor declaration is not.
4. Oracle capabilities. List calls to $U$, $U^\dagger$, controlled variants, PREPARE, SELECT, data access, and projector phases. Say which capabilities are supplied and which must be synthesized.
5. Polynomial and spectral promise. Give the target function, degree, approximation set, transition gap, parity, global bound, and phase convention. Record any complex-completion conditions rather than checking only sample points.
6. Output block and parity. Identify the selected projectors, whether the transform is right-to-left or stays in a right or left signal space, and the action on zero singular directions.
7. Error and success. Separate input block error, polynomial error, phase error, full-unitary implementation error, postselection probability, and failure probability. State the metric for a normalized output state.
8. Query and gate ledger. Count encoded-unitary and inverse calls, controls, reflections, rotations, gates, depth, clean and dirty ancillas, and repetitions or amplification. Never promote a query count to a gate count silently.
9. Classical work and verification. Include coefficient generation, phase synthesis, precision, data loading, compilation, and numerical checks of the polynomial, phases, and selected block.
10. Conclusion and boundary. State exactly what was produced and what was not. Separate an oracle-model transform from a classical-output algorithm, and separate upper bounds from evidence of comparative advantage.

The record is deliberately representation neutral. It can document a hand-built circuit, a sparse-access construction, or a theorem-level oracle, but it prevents those access models from being substituted for one another without a cost conversion.

Block Encodings, Projectors, and Normalization

The common equal-projector specialization uses $a$ signal ancillas:

$$\Pi=\widetilde\Pi =\lvert0^a\rangle\langle0^a\rvert\otimes I.$$

A unitary $U_A$ is an $(\alpha,a,\epsilon_A)$ block encoding of $A$ when

$$\left\lVert A-\alpha (\langle0^a\rvert\otimes I) U_A (\lvert0^a\rangle\otimes I) \right\rVert \leq\epsilon_A.$$

Unless stated otherwise, the norm is the operator norm. Exactness means $\epsilon_A=0$, in which case compression contractivity forces $\alpha\geq\lVert A\rVert$. An approximate definition supplies only $\lVert A\rVert\leq\alpha+\epsilon_A$; it does not automatically make $A/\alpha$ a contraction. Whenever a later robustness theorem treats $A/\alpha$ as its target contraction, the additional promise $\lVert A\rVert\leq\alpha$ must be stated. Keeping $\alpha$ visible also reveals over-normalization: two encodings of the same $A$ can have identical query costs but very different heralding probabilities.

For an exact encoding and normalized $\lvert\psi\rangle$, applying $U_A$ to $\lvert0^a\rangle\lvert\psi\rangle$ produces a signal component

$$\lvert0^a\rangle\frac{A\lvert\psi\rangle}{\alpha}.$$

Measuring the ancillas and accepting $0^a$ therefore succeeds with

$$p_\psi =\frac{\lVert A\lvert\psi\rangle\rVert^2}{\alpha^2}.$$

Conditional on success, the system is $A\lvert\psi\rangle/\lVert A\lvert\psi\rangle\rVert$. If that numerator vanishes, there is no successful branch and hence no normalized output state. If the branch is small, repetitions or amplitude amplification must be charged separately. Neither outcome is a classical list of the entries of $A\lvert\psi\rangle$.

For a projected-unitary encoding of an $m\times n$ matrix, the right signal space has dimension at least $n$ and the left signal space at least $m$. A genuinely rectangular $A$ cannot appear literally in the standard equal-projector corner without a declared zero-padding or square embedding; otherwise one must use the two-projector definition directly. Ambient padding can be useful, but it changes which zero singular directions exist. Thus dimensions, projectors, and padding belong to the mathematical definition, not merely to circuit layout.

Constructing Encodings and Expanding Their Cost

Block-encoding constructions differ primarily in what access they assume. A supplied unitary $V$ is its own $(1,0,0)$ encoding. This observation is exact but does not explain how $V$ is obtained, so it is meaningful only when the input model already supplies or compiles that circuit.

For $A=\sum_j c_jV_j$ with unitary $V_j$, linear combinations of unitaries use a PREPARE operation for coefficient amplitudes and a SELECT operation applying the indexed $V_j$. Absorbing coefficient phases into SELECT gives the natural normalization

$$\lambda=\sum_j\lvert c_j\rvert.$$

One invocation of the composite encoding can contain two state-preparation calls, a multiplexed selection, uncomputation, coefficient arithmetic, and controls. Consequently, “one block query” and “one elementary gate” are different currencies.

Sparse position/value access can coherently enumerate nonzero entries and load their values. In the concrete Gilyén–Su–Low–Wiebe Lemma 48 model, an $s_r$-row-sparse, $s_c$-column-sparse matrix with $\lvert a_{ij}\rvert\leq1$ and explicit row, column, and $b$-bit value oracles has normalization $\sqrt{s_rs_c}$, uses $w+3$ ancillas, and achieves selected-block error $\epsilon$. One encoding call makes one row-oracle call, one column-oracle call, and two value-oracle calls, in addition to precision-dependent reversible arithmetic gates and ancillas; $w$ is the declared address width. Oracle definitions, invalid-index behavior, inverses, and query conversions remain explicit. The circuits of Camps, Lin, Van Beeumen, and Yang likewise show why a verified construction is stronger than simply asserting sparse access.

Row- and column-state preparation can expose overlaps equal to normalized matrix entries. QROM-like data structures may make those preparations efficient relative to a chosen architecture, but memory construction, classical preprocessing, loading bandwidth, finite precision, and coherent uncomputation remain costs. An input already resident in a tailored quantum data structure is a different problem from an arbitrary dense matrix supplied classically.

Coherent preparations also produce Gram, density, and projector encodings. For example, two isometries whose columns prepare indexed state families can yield their overlap matrix as a selected block; tracing or projecting a purification can expose a density operator. One must still state whether the preparation is exact, whether its inverse is available, and which subsystem is selected.

Finally, structure-specific circuits exploit tensor products, symmetries, local terms, or analytic factorizations. They should be assessed by their gate decomposition, numerical selected-block check, and hardware-independent resources. Chakraborty, Gilyén, and Jeffery demonstrate the algorithmic power available once matrix powers are coherently block encoded, but that power is conditional on the stated encoding access rather than a generic promise about classically stored matrices.

A reproducible ledger expands each logical query into PREPARE/SELECT or data-oracle calls, inverses, controls, projector phases, elementary rotations, precision bits, gates, depth, and qubits. It also records classical construction and verification. These columns prevent a favorable theorem in one access model from being compared directly with an implementation cost in another.

Verification should follow the same hierarchy. First prove or numerically test that the purported circuit is unitary on its full declared space; checking only the desired corner cannot detect a nonunitary completion. Next extract the selected block in the stated register order and compare it with $A/\alpha$ in operator norm. Then test inverse and controlled variants, because a compiler may implement those differently from the forward circuit. Finally expand one logical call into the primitive oracle and gate counts used by the surrounding algorithm. Small dense instances are useful regression tests for this pipeline, but they do not replace a uniform construction proof or certify asymptotic data-loading claims.

Adjoint, Product, and Linear-Combination Calculus

The following table is the page’s compact calculus. Errors refer to selected blocks; implementation errors of the full unitaries, preparations, SELECT operations, and controls are additional unless explicitly absorbed into the named terms.

operation	encoded map	normalization	signal space	leading block error	required access
adjoint	$A^\dagger$	$\alpha$	swap left and right	$\epsilon_A$	$U_A^\dagger$ and swapped projectors
tensor product	$A\otimes B$	$\alpha\beta$	tensor independent signal spaces	at most $\alpha\epsilon_B+\beta\epsilon_A$ with target-norm promises	$U_A,U_B$ on independent ancillas
product	$AB$	$\alpha\beta$	right space of $B$ to left space of $A$	at most $\alpha\epsilon_B+\beta\epsilon_A$ with target-norm promises	ordered calls and independent signal ancillas
LCU sum	$\sum_jc_jA_j$	$\lambda=\sum_j\lvert c_j\rvert\alpha_j$	common compatible signal spaces	$\sum_j\lvert c_j\rvert\epsilon_j$	exact PREPARE/SELECT plus constituent encodings
Hermitian dilation	$\mathcal H_A$	$\alpha$	direct sum of left and right spaces	$\epsilon_A$	controlled $U_A,U_A^\dagger$ and one selector
QSVT polynomial	$P^{(\mathrm{SV})}(A/\alpha)$	$1$	parity-dependent projected space	polynomial, block, phase, and oracle terms separated	$d$ alternating $U_A/U_A^\dagger$ calls and projector phases

For the adjoint rule, taking the adjoint of the selected block gives an $(\alpha,a,\epsilon_A)$ encoding of $A^\dagger$ in the equal-projector specialization. More generally, $(U,\Pi,\widetilde\Pi)$ for $B$ becomes $(U^\dagger,\widetilde\Pi,\Pi)$ for $B^\dagger$: the projectors swap. For tensor products and compatible products, independent signal ancillas ensure that the intermediate projection actually occurs. If $X$ and $Y$ are the selected normalized blocks, then under $\lVert A\rVert\leq\alpha$ and $\lVert B\rVert\leq\beta$,

$$\lVert AB-\alpha\beta XY\rVert \leq \alpha\epsilon_B+\beta\epsilon_A.$$

The same bound follows for tensor products. Without those target-norm promises, the universally safe bound is

$$\alpha\epsilon_B +\beta\epsilon_A +\epsilon_A\epsilon_B.$$

The construction is not $U_A^\dagger U_A$ on the same flag. Unitarity makes that product the identity on the entire ambient space, so its selected block is the identity even when $A^\dagger A/\alpha^2$ is not. Independent flags retain the two projections and prevent garbage from returning coherently to the signal branch.

For $A=\sum_jc_jA_j$, exact PREPARE/SELECT access to constituent $(\alpha_j,a_j,\epsilon_j)$ encodings yields normalization

$$\lambda=\sum_j\lvert c_j\rvert\alpha_j$$

and selected-block error at most $\sum_j\lvert c_j\rvert\epsilon_j$. Finite PREPARE and SELECT errors must be added separately under their own norm model. Negative or complex $c_j$ require coherent phases; they are not represented by probabilities alone.

For rectangular $A$, the Hermitian dilation

$$\mathcal H_A = \begin{pmatrix} 0&A\\ A^\dagger&0 \end{pmatrix}$$

has nonzero eigenvalues $\pm\sigma_k(A)$. A controlled construction can preserve normalization while adding a selector qubit, but its controlled and inverse calls and enlarged registers remain in the ledger. Hermitianization provides a useful construction; it does not license replacing a requested singular-value function by an unrelated eigenvalue function.

Singular Subspaces of a Projected Unitary

Let the normalized projected map $B:\mathcal H_R\to\mathcal H_L$ have singular-value decomposition

$$B = \sum_{k=1}^{r} \sigma_k \lvert w_k\rangle\langle v_k\rvert, \qquad 0<\sigma_k\leq1.$$

The vectors $\lvert v_k\rangle$ occupy the right signal space and $\lvert w_k\rangle$ the left signal space. The SVD owner supplies the factorization and pseudoinverse theory; here the decomposition identifies the invariant two-dimensional sectors on which alternating projected-unitary phases act. Rank deficiency leaves additional right and left zero-singular subspaces, and their dimensions need not match.

For an odd function $P$, define the right-to-left transform

$$P^{(\mathrm{SV})}(B) := \sum_{k=1}^{r} P(\sigma_k) \lvert w_k\rangle\langle v_k\rvert.$$

Oddness makes $P(0)=0$, so right-null vectors are annihilated. For an even function, complete the right singular vectors to a basis, assign $\sigma_k=0$ on the right null space, and define

$$P^{(\mathrm{SV})}(B) := \sum_k P(\sigma_k) \lvert v_k\rangle\langle v_k\rvert.$$

This operator remains in the right signal space and acts as $P(0)$ on every padded right-null direction. The corresponding left-space transform follows from the adjoint convention. One expression called merely $P(\Sigma)$ is insufficient because it hides both the change of codomain and the action on zero singular directions.

Polynomial Admissibility and Phase Realization

The safe real-polynomial theorem begins with global, not sampled, conditions. Let $P_R\in\mathbb R[x]$ have degree $d$, parity $d\bmod2$, and

$$\max_{x\in[-1,1]}\lvert P_R(x)\rvert\leq1.$$

Corollary 10 of Gilyén–Su–Low–Wiebe supplies a complex completion $P$ with $\operatorname{Re}P=P_R$. Their Theorem 17 gives

$$\Pi' U_\Phi\Pi=P^{(\mathrm{SV})}(B), \qquad \Pi'= \begin{cases} \widetilde\Pi,&d\ \text{odd},\\ \Pi,&d\ \text{even}. \end{cases}$$

The raw selected block generally transforms by the complex completion $P$, not directly by $P_R$. Corollary 18 obtains the real transform with a coherent selector:

$$P_R^{(\mathrm{SV})}(B) = (\langle+\rvert\otimes\Pi') \left( \lvert0\rangle\langle0\rvert\otimes U_\Phi +\lvert1\rangle\langle1\rvert\otimes U_{-\Phi} \right) (\lvert+\rangle\otimes\Pi).$$

The multiplexer still uses exactly $d$ total calls to $U$ or $U^\dagger$; it adds one selector qubit and controlled projector-phase rotations, not two independent $d$-query sequences.

With

$$D_\Pi(\phi)=e^{i\phi(2\Pi-I)},$$

one explicit convention is

$$U_\Phi = \begin{cases} D_{\widetilde\Pi}(\phi_1)U \displaystyle\prod_{j=1}^{(d-1)/2} \left[ D_\Pi(\phi_{2j})U^\dagger D_{\widetilde\Pi}(\phi_{2j+1})U \right],&d\ \text{odd},\\[6pt] \displaystyle\prod_{j=1}^{d/2} \left[ D_\Pi(\phi_{2j-1})U^\dagger D_{\widetilde\Pi}(\phi_{2j})U \right],&d\ \text{even}. \end{cases}$$

The displayed ordering is a convention, not a portable list of angles. A synthesis routine and circuit must agree on product order, signal convention, phase offsets, and which sequence is conjugated. Low and Chuang established the signal-processing framework and its Hamiltonian specialization; Gilyén and collaborators formulated the general singular-value transformation, while Martyn, Rossi, Tan, and Chuang organize many algorithmic uses around the same polynomial mechanism.

Lemma 19 gives the corresponding resource ledger: one work ancilla, $d$ total uses of $U$ or $U^\dagger$, $d$ uses each of controlled-$\Pi$ NOT and controlled-$\widetilde\Pi$ NOT, and $d$ one-qubit phase gates. The real $\Phi/-\Phi$ multiplexer adds its selector without doubling the $U/U^\dagger$ count. If a separately controlled $U_\Phi$ is required, its phase gates are controlled and, for odd $d$, one occurrence of $U$ is replaced by controlled-$U$. These controls, elementary gates, and classical phase construction remain separate from the block-query count.

The bounded real theorem deliberately avoids hiding the completion problem. In a paired complex-QSP form, $P$ has parity $d$, $Q$ has parity $d-1$, their degrees are at most $d$ and $d-1$, and

$$\lvert P(x)\rvert^2 +(1-x^2)\lvert Q(x)\rvert^2 =1 \qquad(x\in[-1,1]).$$

A prescribed complex degree-$d$ polynomial $P$ alone must satisfy the full Corollary 8 conditions: parity $d$,

$$\lvert P(x)\rvert\leq1 \quad(x\in[-1,1]), \qquad \lvert P(x)\rvert\geq1 \quad(x\in(-\infty,-1]\cup[1,\infty)),$$

and, for even $d$,

$$P(ix)P^*(ix)\geq1 \qquad(x\in\mathbb R),$$

where $P^*$ means coefficientwise conjugation. The last quantity is not $\lvert P(ix)\rvert^2$. Pointwise boundedness only on the target spectral set is insufficient.

A mixed-parity function may be split and recombined with an explicit normalization and ancilla cost, or treated by a separately stated theorem. For rectangular $B$, the odd part maps $\operatorname{im}\Pi$ to $\operatorname{im}\widetilde\Pi$, whereas the even part acts within $\operatorname{im}\Pi$; the two operators cannot be added until a common embedding or Hermitian dilation is declared. Theorem 56 supplies one precise Hermitian route: if $U$ is an $(\alpha,a,\epsilon_A)$ block encoding of Hermitian $A$, a real degree-$d$ polynomial $P$ obeys $\lvert P(x)\rvert\leq1/2$ on $[-1,1]$, and $\delta_{\mathrm{synth}}\geq0$, then the construction is a

$$\left(1,a+2, 4d\sqrt{\epsilon_A/\alpha}+\delta_{\mathrm{synth}} \right)$$

block encoding of $P(A/\alpha)$. It uses $d$ total applications of $U$ or $U^\dagger$, one controlled-$U$, and $O((a+1)d)$ other one- and two-qubit gates. When $\delta_{\mathrm{synth}}>0$, the classical construction time is polynomial in $d$ and $\log(1/\delta_{\mathrm{synth}})$; the existence statement also permits $\delta_{\mathrm{synth}}=0$, without that finite-runtime assertion. The synthesis tolerance is not a spectral-gap symbol. This theorem and generalized QSP are alternatives with their own hypotheses, not silent replacements for standard QSVT.

For source traceability, Gilyén–Su–Low–Wiebe Definitions 11, 16, and 43 define projected-unitary encodings, parity-dependent singular-value transforms, and block encodings. Theorem 3 and Corollaries 8 and 10 supply paired QSP, the prescribed-complex conditions, and real completion; Theorem 17, Corollary 18, and Lemma 19 supply the raw complex transform, coherent real selector, and resources. Lemmas 47, 48, 52, and 53 cover coherent Gram, sparse-oracle, LCU, and independent-ancilla product encodings under the access and error contracts stated here. Lemmas 22 and 23 are respectively the contraction-based square-root robustness result and the separately conditioned linear result. Theorem 56 is the Hermitian arbitrary-parity construction just stated. Lemma 25 and Theorems 30, 31, 41, and 73 provide gap-dependent polynomial amplification, sign or threshold transforms, scaled pseudoinversion, and the query lower bound used below. This numbering follows the full version, arXiv:1806.01838; the bibliography records its peer-reviewed STOC publication.

Chebyshev polynomials provide finite admissible checks: $T_d(\cos\theta)=\cos(d\theta)$, so $\lvert T_d(x)\rvert\leq1$ on $[-1,1]$ and $T_d$ has parity $d$. More useful inverse, sign, step, and threshold approximants require a promised gap or transition band. Uniform approximation to a discontinuity on an interval containing the jump is impossible.

Polynomial completion and phase extraction are separate classical stages. Berntson and Sünderhauf give an FFT-based algorithm that constructs a complementary polynomial $Q$ with explicit error and runtime guarantees; that $Q$ then feeds a distinct phase-factor extraction procedure. Dong, Meng, Whaley, and Lin analyze efficient phase-factor evaluation, Haah supplies a product-factorization route, and Ying develops stable phase-factor factorization. Together these stages motivate three checks: evaluate the achieved polynomial densely over its full admissibility interval, compare the extracted phases and circuit convention, and test the selected block on finite matrices. A small completion error is not automatically a small phase error, and a phase list that works under one convention may fail under another.

Odd and Even Quantum Singular-Value Transforms

Parity determines both algebra and register typing. For odd degree, the selected operator

$$\widetilde\Pi U_\Phi\Pi = \sum_{k=1}^{r}P(\sigma_k) \lvert w_k\rangle\langle v_k\rvert$$

maps the right signal space to the left. For even degree,

$$\Pi U_\Phi\Pi = \sum_kP(\sigma_k) \lvert v_k\rangle\langle v_k\rvert$$

acts within the right space, including $P(0)$ on its declared null padding. Applying the adjoint convention yields the analogous left-space even transform. These expressions explain why an even polynomial of a rectangular map is not another rectangular map of the same shape.

For $P=T_d$, degree is also the encoded-unitary query count: the transform uses $d$ alternating calls, regardless of how many coefficients appear when $T_d$ is expanded in monomials. Degree does not count projector phases, the real-part selector, phase-synthesis work, or the internal cost of $U$. Conversely, an implementation should not charge both a controlled $U$ and its decomposition as separate oracle queries unless the chosen accounting convention explicitly reports nested currencies.

The selected block is still an encoded operator. To obtain a state, prepare an input, run the transform, and project onto the appropriate output signal space. Its success probability is the squared norm of the selected action on that input. Estimating an expectation value or printing singular values requires additional measurement, sampling, and classical processing. QSVT changes coherent spectral response; it does not perform tomography for free.

When the desired response has both parities, write $f=f_{\mathrm e}+f_{\mathrm o}$ with $f_{\mathrm e}(x)=[f(x)+f(-x)]/2$ and $f_{\mathrm o}(x)=[f(x)-f(-x)]/2$. Synthesize the parts under their correct output-space conventions, align their types if necessary through a dilation, and combine them with an LCU or another explicitly stated theorem. The recombination scale and success probability belong in the claim.

Approximate Encodings and End-to-End Error

A reliable design proceeds in a fixed order:

1. Rescale the encoded spectrum into $[-1,1]$ and record $\alpha$.
2. Declare the promised spectral set and any transition gap.
3. Choose odd, even, or explicitly recombined mixed parity.
4. Approximate the target uniformly on the promised set.
5. Enforce boundedness on all of $[-1,1]$, including transition regions.
6. Compute and verify a phase list under one convention.
7. Allocate block, polynomial, phase, oracle, and output errors separately.
8. Expand queries into gates, depth, qubits, and classical synthesis work.

Two perturbation models must remain distinct. Let $B$ and $\widetilde B$ be contractions, and let $P$ be a degree-$d$ polynomial satisfying the complex-QSP admissibility conditions. The robust selected-block theorem gives

$$\left\lVert P^{(\mathrm{SV})}(B) -P^{(\mathrm{SV})}(\widetilde B) \right\rVert \leq 4d\sqrt{\lVert B-\widetilde B\rVert}.$$

This is the unconditional square-root robustness statement of Lemma 22 once both inputs are contractions and $P$ meets complex-QSP admissibility; no spectral-margin hypothesis is added. For an $(\alpha,a,\epsilon_A)$ block encoding, the selected unitary block $\widetilde B$ is automatically a contraction and $\lVert\widetilde B-A/\alpha\rVert\leq\epsilon_A/\alpha$. The definition alone permits $\lVert A\rVert>\alpha$, so require explicitly $\lVert A\rVert\leq\alpha$ before setting the target contraction to $B=A/\alpha$. Under that promise, a representative input-block contribution is

$$4d\sqrt{\epsilon_A/\alpha},$$

Lemma 22 does not justify replacing this by $d\epsilon_A/\alpha$. A linear estimate comes instead from Lemma 23 under the separate condition

$$\lVert B-\widetilde B\rVert +\left\lVert\frac{B+\widetilde B}{2}\right\rVert^2 \leq1,$$

when its perturbation term is

$$d\sqrt{ \frac{2}{1-\left\lVert(B+\widetilde B)/2\right\rVert^2} } \lVert B-\widetilde B\rVert.$$

The square-root bound is generally conservative, but the linear form cannot be used without its midpoint-norm headroom.

Separately, suppose every implemented full-unitary query differs from the nominal $U$ or $U^\dagger$ by at most $\eta_U$ in operator norm. Replacing calls one at a time in a product of $d$ unitaries gives the telescoping contribution $d\eta_U$. Add projector-phase, real-part-control, and phase-synthesis errors under compatible norms. Do not charge one physical defect once as selected-block error and again as full-unitary error; choose the model supported by the implementation evidence.

If the polynomial approximates an ideal response $f$ within $\epsilon_{\mathrm{poly}}$ on the promised singular-value set, a schematic operator budget is

$$\eta \leq \epsilon_{\mathrm{poly}} +4d\sqrt{\epsilon_A/\alpha} +d\eta_U +\epsilon_{\mathrm{phase}} +\epsilon_{\mathrm{ctrl}},$$

with only independently sourced terms included. This budget controls an encoded operator, not automatically a conditional state. If $F$ is the ideal selected operator, $\lVert\widetilde F-F\rVert\leq\eta$, and

$$r=\lVert F\lvert\psi\rangle\rVert>\eta,$$

then normalization amplifies error according to

$$\left\lVert \frac{\widetilde F\lvert\psi\rangle} {\lVert\widetilde F\lvert\psi\rangle\rVert} - \frac{F\lvert\psi\rangle} {\lVert F\lvert\psi\rangle\rVert} \right\rVert \leq \frac{2\eta}{r-\eta}.$$

The condition $r>\eta$ is essential: a tiny ideal branch cannot define a stable normalized output. Postselection probability, repetitions or amplitude amplification, input-state preparation, observable estimation, classical readout, and independent verification all lie outside the bare transform theorem.

Probability error also needs its own conversion. For normalized input $\lvert\psi\rangle$, the reverse triangle inequality gives

$$\left\lvert \lVert\widetilde F\lvert\psi\rangle\rVert -\lVert F\lvert\psi\rangle\rVert \right\rvert \leq\eta.$$

Thus the success amplitude can move by at most $\eta$, while the corresponding probability difference is at most $\eta(2r+\eta)$ when the ideal amplitude is $r$. This does not guarantee a useful relative error when $r$ is small. An amplification schedule must be designed for a proved lower bound or use an unknown-success procedure, and its extra calls multiply the cost and can tighten the required per-call accuracy.

Applications, Outputs, and Canonical Boundaries

QSVT is a general spectral-response engine, but each application inherits a specialized promise and output contract.

• Polynomial functions of Hermitian operators use the eigenvalue specialization. Hamiltonian evolution, its sine/cosine signal convention, phase workflow, and fault-tolerant ledger belong to Qubitization and Quantum Signal Processing, following the signal-processing and qubitization constructions of Low and Chuang.

• Scaled inverse and pseudoinverse filters approximate $1/x$ only away from zero. For Theorem 41, take $0<\epsilon\leq\delta\leq1/2$, let the normalized map $B$ have promised zero-or-at-least-$\delta$ singular subspaces, and let $\Pi_{0,\geq\delta}$ and $\widetilde\Pi_{0,\geq\delta}$ project onto their right and left parts. The reverse-direction guarantee is

  $$\left\lVert (\langle+\rvert\otimes\Pi_{0,\geq\delta})U_\Phi (\lvert+\rangle\otimes\widetilde\Pi_{0,\geq\delta}) - \Pi_{0,\geq\delta}\frac{\delta}{2}B^+ \widetilde\Pi_{0,\geq\delta} \right\rVert \leq\epsilon.$$

  It uses $m=O(\delta^{-1}\log(1/\epsilon))$ total $U/U^\dagger$ calls. Call this a global operator-norm approximation only when the entire declared signal spectrum lies in $\{0\}\cup[\delta,1]$. It is an encoded-operator primitive; solution-state success, conditioning, verification, readout, and classical comparison belong to Quantum Linear Algebra.

• Singular-value threshold projectors and discrimination filters require an explicit transition band. Values inside that band are not promised to behave like an ideal discontinuous step.

• Uniform singular-value amplification requires headroom. In Theorem 30, $\delta,\epsilon\in(0,1/2)$, $\gamma>1$, and every positive target singular value obeys $\sigma_i\leq(1-\delta)/\gamma$. The transformed value satisfies

  $$\left\lvert \frac{\widetilde\sigma_i}{\gamma\sigma_i}-1 \right\rvert \leq\epsilon,$$

  while zero maps to zero, using $m=O((\gamma/\delta)\log(\gamma/\epsilon))$ total $U/U^\dagger$ calls. Singular values cannot be amplified uniformly through $1$. Fixed-point and robust oblivious variants use related responses, while generic two-reflection geometry, schedules, and success accounting belong to Amplitude Amplification.

• Noncommutative measurements and coherent spectral filters can preserve a useful operator output, but extracting classical statistics still invokes sampling and state-preparation costs.

• Quantum Walk Algorithms owns discrete- and continuous-time walk models, graph-access contracts, spectral and hitting-time guarantees, and walk-specific search and detection algorithms. This page retains only the block-encoding and QSVT representation of walk operators, including normalization, error, and query accounting.

The block-power and regression results of Chakraborty, Gilyén, and Jeffery illustrate how encoded matrix functions can improve query-model algorithms. The unification developed by Martyn and collaborators clarifies the shared polynomial structure. In both cases, the scientific conclusion is conditional: access, normalization, precision, success probability, and output type remain part of the claim.

There is also an oracle lower-bound boundary. Let an unknown Hermitian $H$ be supplied by an exact $(1,a,0)$ block encoding, with $\operatorname{spec}(H)\subseteq I\subseteq[-1,1]$. Theorem 73 states that any circuit producing a $(1,b,\epsilon)$ block encoding of $f(H)$ for every promised input, using $T$ applications of $U$, satisfies for every distinct $x,y\in I\cap[-1/2,1/2]$,

$$T = \Omega\!\left( \frac{\lvert f(x)-f(y)\rvert-2\epsilon} {\lvert x-y\rvert} \right),$$

whenever the numerator is positive. This is an eigenvalue-transform oracle lower bound, not a universal gate, depth, wall-clock, or classical-comparison bound; a nonpositive numerator gives no conclusion. The proof’s hard-family encodings are reflections, hence self-inverse, so the same lower bound holds under a $U/U^\dagger$ query convention for that family. This is the reason for the extension, rather than a silent change to the theorem’s $U$-only wording.

Generalized quantum signal processing, developed in peer-reviewed form by Motlagh and Wiebe, uses general $SU(2)$ rotations to relax practical polynomial-family restrictions. It is an extension with a different theorem and synthesis convention, not the definition of standard QSVT. A claim invoking it must replace, rather than silently bypass, the standard parity and completion fields.

The current-literature boundary is active but separate. Laneve’s adversary characterization, Lu, Liu, and Lin’s $U(N)$ framework, and Ito, Mori, Sakamoto, and Fujii’s constructive multivariable decision algorithm concern multivariate or higher-dimensional extensions. Berntson–Sünderhauf instead advances complementary-polynomial construction, which supplies input to separate phase extraction. These works sharpen or broaden signal processing, but they do not replace the standard univariate theorem, completion contract, or eigenvalue-transform lower bound stated here.

An end-to-end advantage claim therefore needs at least three comparisons. The quantum side must expand the encoding, transform, success management, measurement, and classical synthesis. The classical side must receive the same input representation and return an output of comparable information content and accuracy. The theorem comparison must identify whether its lower or upper bound is in queries, gates, samples, or arithmetic operations. Block encoding and QSVT can be decisive components of such an argument, but neither name supplies these missing conversions.

Two Reproducible Finite Audits

Finite matrices cannot prove a uniform theorem, but they can expose projector, parity, normalization, and query-count errors before those errors enter a large application. The two audits below use exact rational values and are reproduced by the single JavaScript program following them.

Audit 1: A selected block and the same-ancilla product trap

Consider

$$A = \begin{pmatrix} 3/5&0\\ 0&0 \end{pmatrix}, \qquad U_A = \begin{pmatrix} 3/5&0&4/5&0\\ 0&0&0&1\\ 4/5&0&-3/5&0\\ 0&1&0&0 \end{pmatrix}.$$

Order the basis by one signal flag followed by the two-dimensional system, so selecting the first two rows and columns means flag zero. The columns of $U_A$ are orthonormal. On input $(1,0,0,0)^{\mathsf T}$, the signal and garbage amplitudes are $3/5$ and $4/5$.

check	exact calculation	result
dimensions	$A:2\times2$, $U_A:4\times4$	compatible one-flag encoding
unitarity	$U_A^\dagger U_A=I_4$	pass
selected block	top-left $2\times2$ block	$A$ with $\alpha=1$
first input image	$U_A(1,0,0,0)^{\mathsf T}$	$(3/5,0,4/5,0)^{\mathsf T}$
total norm	$9/25+16/25$	$1$
signal success	$\lvert3/5\rvert^2$	$9/25$
garbage probability	$\lvert4/5\rvert^2$	$16/25$
same-flag product	selected block of $U_A^\dagger U_A$ versus $A^\dagger A$	$I_2\neq\operatorname{diag}(9/25,0)$

The last row is the essential counterexample. Garbage created by the first call can return to the selected space under the inverse; without an independent intermediate flag, unitary cancellation replaces the intended projected product.

Audit 2: Rectangular odd and even transforms

Let

$$B = \begin{pmatrix} 3/5&0&0\\ 0&4/5&0 \end{pmatrix},$$

and choose $T_2(x)=2x^2-1$ and $T_3(x)=4x^3-3x$. The two nonzero right singular vectors map to their corresponding left vectors, while the third right basis vector spans the null space.

check	exact calculation	result
shape and spaces	$B:\mathbb C^3\to\mathbb C^2$	distinct right and left projectors required
singular values	diagonal rectangular entries	$3/5$, $4/5$, and right-null $0$
even samples	$T_2(3/5),T_2(4/5),T_2(0)$	$-7/25,7/25,-1$
even right block	right-space diagonal	$\operatorname{diag}(-7/25,7/25,-1)$
odd samples	$T_3(3/5),T_3(4/5),T_3(0)$	$-117/125,-44/125,0$
odd rectangular block	right-to-left $2\times3$ map	diagonal entries $-117/125,-44/125$ and zero third column
parity and bound	$T_2(-x)=T_2(x)$, $T_3(-x)=-T_3(x)$	both bounded by $1$ on $[-1,1]$
degree and queries	$\deg T_2=2$, $\deg T_3=3$	exactly $2$ and $3$ encoded-unitary calls

The audit supports the following repaired claim:

1. Target operator and domain. The target is the displayed $2\times3$ contraction $B:\mathbb C^3\to\mathbb C^2$, including its one-dimensional right null space.
2. Encoding and normalization. Assume an exact projected-unitary encoding with normalization $\alpha=1$; $\lVert B\rVert=4/5$.
3. Projectors and registers. The right projector selects a three-dimensional input space and the left projector a two-dimensional output space, with register order fixed by the implementing unitary.
4. Oracle capabilities. The algorithm has $U$, $U^\dagger$, controlled real-part selection, and both projector phase operations.
5. Polynomial and spectral promise. Use $T_2$ or $T_3$ on $[-1,1]$; each has the required parity and global unit bound.
6. Output block and parity. $T_2$ gives the three-dimensional right-space diagonal including $-1$ on the null vector; $T_3$ gives the displayed right-to-left $2\times3$ map.
7. Error and success. The finite algebra is exact. A state-generation claim must additionally compute the selected output norm for its chosen input.
8. Query and gate ledger. The transforms use two or three $U/U^\dagger$ calls, plus projector phases, controls, one real-part selector, and the internal implementation of $U$.
9. Classical work and verification. Evaluate the Chebyshev responses exactly, verify parity on $x\mapsto-x$, verify the unit bound, and compare the selected finite blocks.
10. Conclusion and boundary. The audit verifies register typing and finite constants; it neither synthesizes a physical phase list nor establishes an end-to-end advantage.

The executable audit checks the matrix, norm, probability, polynomial, parity, block, and record constants. It deliberately uses no package or random input.

const tol = 1e-12;
const assert = (condition, message) => {
  if (!condition) throw new Error(message);
};
const close = (x, y) => Math.abs(x - y) <= tol;
const transpose = (matrix) =>
  matrix[0].map((_, column) => matrix.map((row) => row[column]));
const multiply = (left, right) =>
  left.map((row) =>
    right[0].map((_, column) =>
      row.reduce((sum, value, index) => sum + value * right[index][column], 0),
    ),
  );
const apply = (matrix, vector) =>
  matrix.map((row) => row.reduce((sum, value, index) => sum + value * vector[index], 0));
const normSquared = (vector) => vector.reduce((sum, value) => sum + value * value, 0);
const topLeft = (matrix, rows, columns) =>
  matrix.slice(0, rows).map((row) => row.slice(0, columns));
const sameMatrix = (left, right) =>
  left.length === right.length &&
  left.every((row, i) =>
    row.length === right[i].length && row.every((value, j) => close(value, right[i][j])),
  );

const A = [
  [3 / 5, 0],
  [0, 0],
];
const U = [
  [3 / 5, 0, 4 / 5, 0],
  [0, 0, 0, 1],
  [4 / 5, 0, -3 / 5, 0],
  [0, 1, 0, 0],
];
const I4 = [
  [1, 0, 0, 0],
  [0, 1, 0, 0],
  [0, 0, 1, 0],
  [0, 0, 0, 1],
];
const I2 = [
  [1, 0],
  [0, 1],
];

assert(sameMatrix(multiply(transpose(U), U), I4), 'unitarity');
assert(sameMatrix(topLeft(U, 2, 2), A), 'selected block');
assert(close(Math.max(Math.abs(A[0][0]), Math.abs(A[1][1])), 3 / 5), 'A norm');
const image = apply(U, [1, 0, 0, 0]);
assert(sameMatrix([image], [[3 / 5, 0, 4 / 5, 0]]), 'first input image');
assert(close(normSquared(image), 1), 'output norm');
assert(close(normSquared(image.slice(0, 2)), 9 / 25), 'success probability');
assert(close(normSquared(image.slice(2)), 16 / 25), 'garbage probability');
const selectedSameFlag = topLeft(multiply(transpose(U), U), 2, 2);
const AdaggerA = multiply(transpose(A), A);
assert(sameMatrix(selectedSameFlag, I2), 'same-flag product');
assert(sameMatrix(AdaggerA, [[9 / 25, 0], [0, 0]]), 'A dagger A');
assert(!sameMatrix(selectedSameFlag, AdaggerA), 'product counterexample');

const B = [
  [3 / 5, 0, 0],
  [0, 4 / 5, 0],
];
const T2 = (x) => 2 * x * x - 1;
const T3 = (x) => 4 * x * x * x - 3 * x;
assert(close(Math.max(3 / 5, 4 / 5), 4 / 5), 'B norm');
assert(close(T2(3 / 5), -7 / 25), 'T2 at 3/5');
assert(close(T2(4 / 5), 7 / 25), 'T2 at 4/5');
assert(close(T2(0), -1), 'T2 at zero');
assert(close(T3(3 / 5), -117 / 125), 'T3 at 3/5');
assert(close(T3(4 / 5), -44 / 125), 'T3 at 4/5');
assert(close(T3(0), 0), 'T3 at zero');
const evenBlock = [
  [T2(3 / 5), 0, 0],
  [0, T2(4 / 5), 0],
  [0, 0, T2(0)],
];
const oddBlock = [
  [T3(3 / 5), 0, 0],
  [0, T3(4 / 5), 0],
];
assert(sameMatrix(evenBlock, [[-7 / 25, 0, 0], [0, 7 / 25, 0], [0, 0, -1]]), 'even block');
assert(sameMatrix(oddBlock, [[-117 / 125, 0, 0], [0, -44 / 125, 0]]), 'odd block');
for (let index = 0; index <= 2000; index += 1) {
  const x = -1 + index / 1000;
  assert(close(T2(-x), T2(x)), 'even parity');
  assert(close(T3(-x), -T3(x)), 'odd parity');
  assert(Math.abs(T2(x)) <= 1 + tol, 'T2 bound');
  assert(Math.abs(T3(x)) <= 1 + tol, 'T3 bound');
}

const record = {
  leftDimension: 2,
  rightDimension: 3,
  alpha: 1,
  operatorNorm: 4 / 5,
  evenDegree: 2,
  oddDegree: 3,
  evenQueries: 2,
  oddQueries: 3,
  evenNullValue: -1,
  oddNullValue: 0,
};
assert(record.leftDimension === B.length, 'left dimension');
assert(record.rightDimension === B[0].length, 'right dimension');
assert(record.alpha >= record.operatorNorm, 'normalization record');
assert(record.evenDegree === record.evenQueries, 'even query record');
assert(record.oddDegree === record.oddQueries, 'odd query record');
assert(close(record.evenNullValue, T2(0)), 'even null record');
assert(close(record.oddNullValue, T3(0)), 'odd null record');

console.log('Block-encoding and QSVT audits: PASS');

Common Block-Encoding and QSVT Claim Failures

Treating stored data as coherent access. A classical array does not supply reversible row preparation, inverse calls, or controlled SELECT. State the loading model and count its construction and precision costs.

Suppressing normalization. Writing only “encode $A$” hides both admissibility and success. Carry $\alpha$ through composition, polynomial rescaling, and heralding, and explicitly require $\lVert A\rVert\leq\alpha$ when $A/\alpha$ must be a contraction.

Confusing same-flag multiplication with projected multiplication. The selected block of $U_A^\dagger U_A$ is the identity. Use independent signal flags or another construction that inserts the required intermediate projection.

Checking a polynomial only on promised eigenvalues. Accuracy on a spectral subset does not imply QSVT admissibility. Verify the parity and the unit bound on all of $[-1,1]$, along with the applicable complex-completion conditions.

Ignoring the odd/even output space. Odd transforms map right to left; even transforms remain in a chosen signal space and can act nontrivially on null padding. Declare the selected projectors and zero-singular action.

Merging error models. Robust selected-block error has a square-root bound, whereas repeated full-unitary implementation error telescopes linearly. Do not double count one defect or replace either theorem by an unsupported $d\epsilon_A/\alpha$ mnemonic.

Calling an encoded operator classical output. A selected block is coherent access. State preparation, amplification, observable estimation, tomography, and verification have their own costs and failure probabilities.

Exercises

Exercise 1: Normalization and heralding

Let $A=\operatorname{diag}(3,1)$ and suppose an exact block encoding uses $\alpha=5$. For input $\lvert+\rangle=(\lvert0\rangle+\lvert1\rangle)/\sqrt2$, compute the success probability and conditional system state. Repeat for an exact encoding with the smallest allowed normalization.

Solution

The unnormalized selected system vector is

$$\frac{A\lvert+\rangle}{5} = \frac{3\lvert0\rangle+\lvert1\rangle}{5\sqrt2}.$$

Since $\lVert A\lvert+\rangle\rVert^2=(9+1)/2=5$, the success probability is $5/25=1/5$. Conditional on success the state is $(3\lvert0\rangle+\lvert1\rangle)/\sqrt{10}$. The operator norm is $3$, so the smallest exact normalization is $\alpha=3$. It raises the success probability to $5/9$ but leaves the conditional state unchanged. Thus normalization affects heralding even when it does not affect the normalized mathematical answer.

Exercise 2: The product-ancilla counterexample

Use the first audit’s $A$ and $U_A$. Compute the selected block of $U_A^\dagger U_A$ and compare it with $A^\dagger A$. Explain in words how independent signal ancillas repair the product construction.

Solution

Unitarity gives $U_A^\dagger U_A=I_4$, so selecting flag zero gives $I_2$. In contrast,

$$A^\dagger A = \begin{pmatrix} 9/25&0\\ 0&0 \end{pmatrix}.$$

The mismatch occurs because the inverse returns both signal and garbage amplitudes; selection only after the complete product does not insert a projection between the calls. With independent flags, one unitary writes its signal condition into one ancilla register and the other reads through a separately selected register. Projecting both external flags to zero then retains the intermediate selected block, yielding the properly normalized product rather than coherent unitary cancellation.

Exercise 3: Rectangular odd and even transforms

For the second audit’s $B$, derive the $T_2$ and $T_3$ singular-value transforms without referring to the audit table. State their dimensions and their actions on the third right basis vector.

Solution

The nonzero singular values are $3/5$ and $4/5$. Even parity keeps the transform in the three-dimensional right space, and direct substitution gives

$$T_2^{(\mathrm{SV})}(B) = \begin{pmatrix} -7/25&0&0\\ 0&7/25&0\\ 0&0&-1 \end{pmatrix}.$$

The last entry is $T_2(0)=-1$, so the right-null vector is not discarded. Odd parity maps the right space to the two-dimensional left space:

$$T_3^{(\mathrm{SV})}(B) = \begin{pmatrix} -117/125&0&0\\ 0&-44/125&0 \end{pmatrix}.$$

Its third column vanishes because $T_3(0)=0$. The dimensions, $3\times3$ versus $2\times3$, are consequences of parity rather than cosmetic padding choices.

Exercise 4: Repairing mixed parity

The target response is $g(x)=1/2+x/4$. Why can it not be inserted directly into the definite-parity theorem? Give an explicit split-and-recombine construction and its LCU normalization, assuming exact unit-normalized transforms of the constant and linear polynomials.

Solution

The constant part is even and the linear part is odd, so $g$ has neither definite parity. Write

$$g_{\mathrm e}(x)=\frac12, \qquad g_{\mathrm o}(x)=\frac{x}{4}.$$

Implement $T_0(x)=1$ under the even convention and $T_1(x)=x$ under the odd convention. Their output types must first be aligned, for example with a declared Hermitian dilation or selector construction. An LCU with coefficients $1/2$ and $1/4$ then has normalization

$$\lambda=\frac12+\frac14=\frac34.$$

The selected block of the recombination is $g/\lambda$ under that normalization. PREPARE, SELECT, the selector ancilla, alignment operations, and resulting success probability are additional resources. This is an explicit reduction, not a claim that standard QSVT directly implements mixed parity.

Exercise 5: Chebyshev degree and query count

Consider $T_7(x)$. Establish admissibility for the real theorem, evaluate $T_7(1/2)$, and give the encoded-unitary query count. Which costs are absent from that count?

Solution

From $T_7(\cos\theta)=\cos(7\theta)$, $\lvert T_7(x)\rvert\leq1$ for every $x\in[-1,1]$. It is a real polynomial of degree seven and is odd, so its parity matches its degree. Since $1/2=\cos(\pi/3)$,

$$T_7(1/2) = \cos(7\pi/3) = \frac12.$$

The alternating QSVT sequence uses exactly seven calls to $U$ or $U^\dagger$. That number excludes projector phase operations, controlled selection between phase sequences, elementary synthesis of rotations, ancillas, classical phase computation, and the gates inside each encoded-unitary call.

Exercise 6: Separating two perturbation models

A degree-$25$ transform has normalized selected-block error $\epsilon_A/\alpha=10^{-8}$. Independently, each full-unitary call has error at most $\eta_U=2\times10^{-6}$. The polynomial and phase budgets are $2\times10^{-4}$ and $3\times10^{-5}$. Compute the stated conservative operator budget, and explain when including both hardware terms is legitimate.

Solution

The robust selected-block contribution is

$$4(25)\sqrt{10^{-8}}=10^{-2}.$$

The separate telescoping contribution is $25(2\times10^{-6})=5\times10^{-5}$. Adding the independently allocated polynomial and phase terms gives

$$\eta \leq 0.01+0.00005+0.00020+0.00003 =0.01028.$$

Both hardware terms may appear only if they describe distinct imperfections: for example, a verified mismatch in the selected mathematical block and an additional implementation error affecting each otherwise nominal full-unitary call. If both numbers were derived from the same faulty gates, adding them would double count. The calculation also assumes the target $A/\alpha$ and implemented selected block are contractions and that the polynomial satisfies complex-QSP admissibility.

Exercise 7: Gap-dependent inverse filtering

Let a contraction $B$ have singular values $1/4$ and $1$, with promised lower bound $\delta=1/8$. An inverse filter implements $F=(\delta/2)B^+=(1/16)B^+$ on the supported subspace. For an equal superposition of the two right singular vectors, compute the success probability, normalized amplitude ratio, characteristic approximation degree, and repetition improvement suggested by amplitude amplification.

Solution

The filter values are $(1/16)/(1/4)=1/4$ and $(1/16)/1=1/16$. Acting on the equal superposition therefore gives an unnormalized selected state with those amplitudes divided by $\sqrt2$. Its success probability is

$$p = \frac12\left(\frac1{16}+\frac1{256}\right) = \frac{17}{512}.$$

After normalization, the two amplitudes have ratio $4:1$. A standard bounded inverse approximation on a gap $\delta$ has characteristic degree $O(\delta^{-1}\log(1/\epsilon))=O(8\log(1/\epsilon))$, with constants depending on the precise transition design. Naive repetition costs order $1/p$, whereas amplitude amplification suggests order $1/\sqrt p=\sqrt{512/17}$ uses of the state-producing procedure, subject to the amplification owner’s schedule and error contract. The example produces a state, not the two inverse entries as classical data.

Exercise 8: Repairing a complete claim

Repair the statement: “Given a classical matrix, QSVT outputs all entries of its inverse in $O(\log(1/\epsilon))$ time.” Use a promised singular-value gap $\delta$, a scaled pseudoinverse polynomial, and an encoded-operator or heralded-state output.

Solution

One complete repaired claim is:

1. Target operator and domain. Let $A:\mathbb C^n\to\mathbb C^m$ have nonzero singular values in $[\delta,1]$ after normalization, and target a bounded scaled Moore–Penrose pseudoinverse on that supported subspace.
2. Encoding and normalization. Supply an $(\alpha,a,\epsilon_A)$ block encoding with the additional promise $\lVert A\rVert\leq\alpha$; the normalized target is $B=A/\alpha$ and its nonzero singular values lie in $[\delta,1]$.
3. Projectors and registers. Declare the $n$-dimensional right and $m$-dimensional left signal spaces, ancilla order, and zero-singular padding. The inverse transform reverses the left-to-right map on the support.
4. Oracle capabilities. Provide coherent $U_A$, $U_A^\dagger$, required controlled variants, and implementable phases about both projectors. A classical array alone is insufficient.
5. Polynomial and spectral promise. Choose a bounded odd polynomial approximating $c/x$ on $[-1,-\delta]\cup[\delta,1]$, with $c=O(\delta)$, uniform error $\epsilon_{\mathrm{poly}}$, definite parity, and unit bound on all of $[-1,1]$.
6. Output block and parity. The odd transform is a scaled pseudoinverse block from the left signal space to the right; alternatively, postselection on a declared left-space input yields a normalized solution state when the selected norm is nonzero.
7. Error and success. Combine polynomial, admissible robust-block, phase, and independently modeled full-unitary errors. For a state output report its selected norm, postselection probability, amplification schedule, and normalized-state error.
8. Query and gate ledger. A typical inverse approximation uses degree $O(\delta^{-1}\log(1/\epsilon_{\mathrm{poly}}))$ and that many $U_A/U_A^\dagger$ calls, plus projector phases, controls, encoding gates, ancillas, and any repetitions or amplification.
9. Classical work and verification. Count input loading, polynomial construction, phase synthesis, precision, circuit compilation, and finite checks of global boundedness and the selected block.
10. Conclusion and boundary. The result is coherent access to a scaled pseudoinverse or a heralded normalized state under explicit promises. It does not list all inverse entries, and it is not an $O(\log(1/\epsilon))$ end-to-end classical-output algorithm.

This repaired statement exposes the missing input model, gap dependence, normalization, output type, and readout cost. It also leaves solver-specific conditioning and verification with the quantum linear-algebra owner.

References

• B. K. Berntson and C. Sünderhauf, “Complementary Polynomials in Quantum Signal Processing,” Communications in Mathematical Physics 406, 161 (2025), doi:10.1007/s00220-025-05302-9.
• D. Camps, L. Lin, R. Van Beeumen, and C. Yang, “Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices,” SIAM Journal on Matrix Analysis and Applications 45, 801–827 (2024), doi:10.1137/22M1484298.
• S. Chakraborty, A. Gilyén, and S. Jeffery, “The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation,” in 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), LIPIcs 132, 33:1–33:14 (2019), doi:10.4230/LIPIcs.ICALP.2019.33.
• Y. Dong, X. Meng, K. B. Whaley, and L. Lin, “Efficient Phase-Factor Evaluation in Quantum Signal Processing,” Physical Review A 103, 042419 (2021), doi:10.1103/PhysRevA.103.042419.
• A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, “Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 193–204 (2019), doi:10.1145/3313276.3316366.
• J. Haah, “Product Decomposition of Periodic Functions in Quantum Signal Processing,” Quantum 3, 190 (2019), doi:10.22331/q-2019-10-07-190.
• Y. Ito, H. Mori, K. Sakamoto, and K. Fujii, “Polynomial Time Constructive Decision Algorithm for Multivariable Quantum Signal Processing,” Quantum 10, 2102 (2026), doi:10.22331/q-2026-05-12-2102.
• L. Laneve, “An Adversary Bound for Quantum Signal Processing,” Quantum 10, 2025 (2026), doi:10.22331/q-2026-03-13-2025.
• G. H. Low and I. L. Chuang, “Optimal Hamiltonian Simulation by Quantum Signal Processing,” Physical Review Letters 118, 010501 (2017), doi:10.1103/PhysRevLett.118.010501.
• G. H. Low and I. L. Chuang, “Hamiltonian Simulation by Qubitization,” Quantum 3, 163 (2019), doi:10.22331/q-2019-07-12-163.
• X. Lu, Y. Liu, and H. Lin, “Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$,” Quantum 10, 2048 (2026), doi:10.22331/q-2026-03-27-2048.
• J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, “Grand Unification of Quantum Algorithms,” PRX Quantum 2, 040203 (2021), doi:10.1103/PRXQuantum.2.040203.
• D. Motlagh and N. Wiebe, “Generalized Quantum Signal Processing,” PRX Quantum 5, 020368 (2024), doi:10.1103/PRXQuantum.5.020368.
• L. Ying, “Stable Factorization for Phase Factors of Quantum Signal Processing,” Quantum 6, 842 (2022), doi:10.22331/q-2022-10-20-842.