Block Encodings and QSVT

A block encoding places a possibly nonunitary matrix inside a larger unitary circuit. Quantum singular-value transformation (QSVT) then changes how the circuit acts on each singular-vector pair: a singular value $\sigma$ becomes a polynomial response $P(\sigma)$. A degree-$d$ transform uses $d$ calls to the encoding or its inverse, together with phase rotations about selected subspaces. Normalization, polynomial constraints and the output subspace determine what this circuit actually computes.

The result is another encoded operator. Applying it to a state and accepting a selected outcome requires a success analysis; obtaining classical numbers requires measurement. The examples below show both the advantage of a unitary embedding and the mistakes caused by treating its selected block as the whole circuit.

Helpful background. Quantum oracles explains coherent input operations and their inverses. Singular-value decomposition distinguishes the left and right singular vectors. The Hamiltonian application is developed in qubitization and quantum signal processing.

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.

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 give overlap and density-operator encodings. If two actual isometries $V_L,V_R$ are available as parts of reversible circuits, $V_L^\dagger V_R$ is an overlap matrix. Merely listing a family of nonorthogonal vectors does not make those vectors the columns of an isometry.

For a density operator $\rho_A$, suppose $G|0\rangle_{AE}=|\Psi\rangle_{AE}$ is a purification. Prepare it, swap $A$ with a separate target register of the same dimension, and apply $G^\dagger$ to $AE$. Selecting $AE=0$ exposes $\rho$ on the target. This uses coherent preparation, SWAP and unpreparation; tracing out $E$ alone supplies a state, not a block-encoding oracle. Projecting $E$ alone generally produces a conditional pure state rather than $\rho$.

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.

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 and scale	Construction
Adjoint	$A^\dagger/\alpha$	Use $U_A^\dagger$ and exchange the left/right projectors.
Tensor product	$(A\otimes B)/(\alpha\beta)$	Tensor the encodings with independent signal spaces.
Product	$AB/(\alpha\beta)$	Use ordered calls with independent signal flags and compatible intermediate spaces.
Linear combination	$(\sum_jc_jA_j)/\lambda$	PREPARE/SELECT with $\lambda=\sum_j\lvert c_j\rvert\alpha_j$.
Hermitian dilation	$\mathcal H_A/\alpha$	Combine the encoding and its adjoint with a selector, padding unequal spaces when necessary.
QSVT	$P^{(\mathrm{SV})}(A/\alpha)$	Use $d$ alternating encoding/inverse calls and projector phases; output spaces depend on parity.

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)$. After compatible square padding, a controlled construction can preserve normalization while adding a selector qubit. Its inverse and controlled calls and larger registers are additional costs. 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. This decomposition identifies the invariant sectors, of dimension at most two, 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).$$

This averages the polynomial responses $P$ and $P^*$ in the same singular-vector bases. For complex singular vectors it is not an entrywise real part of the matrix. 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 operation counts: 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$ with $\|A\|\leq\alpha$, 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.

The theorem and lemma numbers here refer to the full Gilyén–Su–Low–Wiebe paper, rather than its shorter STOC proceedings version.

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. Dense numerical evaluation can reveal a bad polynomial or phase list, but a finite grid cannot prove a uniform bound between its samples. Use a proven polynomial construction or a certified global extremum/error bound, then check the chosen phase convention and selected blocks 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

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 when the midpoint has norm strictly below one and

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

Under these conditions, 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; use the bound that describes the actual imperfection.

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}.$$

The condition $r>\eta$ guarantees a nonzero approximate branch. The bound follows by inserting $\widetilde F|\psi\rangle/r$ between the normalized vectors and applying the reverse triangle inequality. Even a small operator error can give a large relative error when $r$ is small. 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.

What the transformed operator can do

Different polynomial responses solve different tasks. Each application must specify its spectral promise and how the transformed operator is used.

• Polynomial functions of Hermitian operators use the eigenvalue specialization. For Hamiltonian evolution, the sine/cosine construction and its implementation costs are developed in 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 the general two-reflection geometry and repetition schedules are explained in 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 applies related reflections and spectral transformations to search, detection and hitting problems.

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.

Multivariable and higher-dimensional extensions use different theorems. The univariate conditions above should not be silently dropped when citing an extension; current questions are discussed in quantum algorithm discovery. For an application, also count the encoding construction, successful-state preparation and measurement rather than only the polynomial degree.

Two explicit projected-unitary examples

Why multiplying a unitary and its inverse does not square its block

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.

A rectangular matrix gives different odd and even output spaces

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

These two Chebyshev transforms can also be checked by multiplying the full unitaries, rather than merely substituting singular values. Write $R_R=2\Pi-I$ and $R_L=2\widetilde\Pi-I$. In the displayed phase convention, choose

$$\begin{aligned} d=2:&\quad \Phi=(-\pi/2,\pi/2), &U_\Phi&=R_RU^\dagger R_LU,\\ d=3:&\quad \Phi=(\pi,\pi/2,\pi/2), &U_\Phi&=UR_RU^\dagger R_LU. \end{aligned}$$

Selecting the appropriate rows and columns gives $2B^\dagger B-I_R$ in the first case and $4BB^\dagger B-3B$ in the second. Their matrix shapes and values agree with the table, including the $-1$ action of the even transform on the right null vector. Each expression uses two or three encoding/inverse calls respectively. The leftmost factor acts last; changing the order changes the circuit.

For example, a real scalar block $s=3/5$ has the reflection completion $U=\left(\begin{smallmatrix}s&\sqrt{1-s^2}\\\sqrt{1-s^2}&-s\end{smallmatrix}\right)$. This short NumPy calculation evaluates the two sequences:

import numpy as np

s = 3/5
U = np.array([[s, np.sqrt(1-s*s)], [np.sqrt(1-s*s), -s]])
R = np.diag([1., -1.])
even = R @ U.T @ R @ U
odd = U @ R @ U.T @ R @ U
print(even[0, 0], odd[0, 0])  # -7/25 and -117/125

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 worked example’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 rectangular $B$ in the second worked example, derive the $T_2$ and $T_3$ singular-value transforms directly. 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 left 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, provided the preparation, its inverse and the required success reflections are available with sufficient accuracy. The example produces a state, not the two inverse entries as classical data.

Exercise 8: A bounded real response and its complex completion

The odd real polynomial $P_R(x)=x/2$ is bounded on $[-1,1]$. Explain why it can be implemented with a real-part selector but cannot be the raw complex selected polynomial of a one-query QSP sequence. Construct a complex completion and its one-query phase. For a complex rectangular $B$, does selecting its real response mean taking the entrywise real part of $B/2$?

Solution

A raw QSP polynomial must have magnitude one at $x=\pm1$, as follows from $|P(x)|^2+(1-x^2)|Q(x)|^2=1$. The proposed $P_R$ has magnitude $1/2$ there, so it cannot be that raw polynomial.

Choose $\phi=\pi/3$ and $P(x)=e^{i\phi}x$. It has the same parity and $\operatorname{Re}P(x)=x/2$ for real $x$. A one-query sequence $D_{\widetilde\Pi}(\phi)U$ selects $e^{i\phi}B$; using $-\phi$ selects $e^{-i\phi}B$. Coherently averaging the two with a $|+\rangle$ selector gives $\cos\phi\,B=B/2$.

This preserves the complex singular vectors and all complex entries of $B/2$. It is not the entrywise real part of that matrix. The extra selector makes the real polynomial possible without replacing one encoding query by two sequential queries.

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.
• 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.
• 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.