DefinitionDefinition: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite block encoding

Definition

Write $T^{†}$ for the adjoint $T^{*}$ characterized by The adjoint $T^{*} : W \to V$ is characterised by $⟨ T v, w ⟩_{W} = ⟨ v, T^{*} w ⟩_{V}$ . Fix integers $m, n \geq 1$ , $a \geq 0$ , and $d \geq \max (m, n)$ . On each coordinate space $C^{r}$ use $⟨ x, y ⟩_{r o o t} : = \sum_{q = 1}^{r} x_{q} \overline{y_{q}}$ , linear in the first argument. Put the ancilla register before the system register in every tensor product, and let $e_{0} = (1, 0, \dots, 0)$ be the first standard basis vector in $C^{2^{a}}$ . For $A : C^{n} \to C^{m}$ , choose as part of the data padding maps $E_{i n} : C^{n} \to C^{d}$ and $E_{o u t} : C^{m} \to C^{d}$ satisfying $E_{i n}^{†} E_{i n} = I_{n}$ and $E_{o u t}^{†} E_{o u t} = I_{m}$ . The default padding sends a coordinate vector to the same coordinates followed by zeros. Set $\hat{A} : = E_{o u t} A E_{i n}^{†} : C^{d} \to C^{d}$ .

Let $J_{a} : C^{d} \to C^{2^{a}} \otimes C^{d}$ be $J_{a} x = e_{0} \otimes x$ , where $e_{0}$ is the all-zero computational basis vector, and let $Π_{a} : = J_{a} J_{a}^{†}$ . For a unitary $U$ on $C^{2^{a}} \otimes C^{d}$ , its projected block is the endomorphism $B_{U} : = J_{a}^{†} U J_{a}$ of $C^{d}$ . It is not asserted to be unitary.

For $α > 0$ and $ε \geq 0$ , the tuple $(U, a, α, ε, d, E_{i n}, E_{o u t})$ is an $(α, a, ε)$ block encoding of $A$ when $α \geq ∥ A ∥_{o p}$ and $∥ B_{U} - \hat{A} / α ∥_{o p} \leq ε$ . The exact case is $ε = 0$ . For square $A$ , take $m = n = d$ and both embeddings equal to the identity. For rectangular $A$ , the dimensions and embeddings remain part of the encoding data.

The equivalent projector notation identifies $B_{U}$ with the restriction of $Π_{a} U Π_{a}$ to $ran (Π_{a})$ , transported to $C^{d}$ by $J_{a}$ ; it does not regard $Π_{a} U Π_{a}$ as a unitary.

Remarks

This item uses normalized compression error: its $ε$ corresponds to an unnormalized tolerance $α ε$ . In Gilyén et al., Definition 43, the stated condition is $∥ A - α B_{U} ∥_{o p} \leq ε_{s r c}$ , which implies $∥ A ∥_{o p} \leq α + ε_{s r c}$ ; the local promise $α \geq ∥ A ∥_{o p}$ is additional in the approximate case. The choice of $α \geq ∥ A ∥_{o p}$ follows the exact rescaling convention in Childs, §29.1.

Facts & Assumptions

Given: Finite coordinate spaces with their standard complex inner products, a unitary $U$ on $C^{2^{a}} \otimes C^{d}$ , and the declared dimensions and embeddings above.

[F1]

Real and complex inner-product spaces and their induced length: the complex inner product is linear in its first argument and its induced length is $∥ x ∥ = \sqrt{⟨ x, x ⟩}$ .

[F2]

The norm $∥ v ∥ = \sqrt{⟨ v, v ⟩}$ induced by a real or complex inner product: the inner-product norm is the nonnegative square root of the diagonal pairing.

[F3]

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: the operator norm on a nonzero finite-dimensional domain is the maximum of $∥ T x ∥$ over unit vectors, and on the zero domain it is zero.

[F4]

The adjoint $T^{*} : W \to V$ is characterised by $⟨ T v, w ⟩_{W} = ⟨ v, T^{*} w ⟩_{V}$ : $⟨ T x, y ⟩ = ⟨ x, T^{*} y ⟩$ for every $x, y$ ; this item writes $T^{*}$ as $T^{†}$ .

[F5]

Adjoints satisfy $(S + T)^{*} = S^{*} + T^{*}$ , $(λ T)^{*} = \overline{λ} T^{*}$ , $(S T)^{*} = T^{*} S^{*}$ , and $T^{* *} = T$ : adjoints reverse composition and $(T^{†})^{†} = T$ .

[F6]

Linear isometries, and orthogonal or unitary operators on finite-dimensional inner product spaces: a unitary on a finite-dimensional complex inner-product space is an invertible linear isometry.

Proof

1.1givenF1F4F5algebra

Since $e_{0}$ is a unit vector, $J_{a}^{†} J_{a} = I$ and $J_{a} J_{a}^{†} = Π_{a}$ . Therefore $J_{a}^{†} (Π_{a} U Π_{a}) J_{a} = J_{a}^{†} U J_{a} = B_{U}$ and $Π_{a} U Π_{a} = J_{a} B_{U} J_{a}^{†}$ . Thus $J_{a}$ identifies the restriction of $Π_{a} U Π_{a}$ on its range with $B_{U}$ .

1.2givenF1F2F4F5algebra

The padding conditions give $E_{i n}^{†} E_{i n} = I_{n}$ and $E_{o u t}^{†} E_{o u t} = I_{m}$ . Thus $P_{i n} : = E_{i n} E_{i n}^{†}$ is a self-adjoint idempotent. For every $z$ , $P_{i n} z$ and $(I - P_{i n}) z$ are orthogonal, so $∥ P_{i n} z ∥^{2} \leq ∥ z ∥^{2}$ . By [F4], $∥ E_{i n}^{†} z ∥^{2} = ⟨ P_{i n} z, z ⟩ = ∥ P_{i n} z ∥^{2}$ and $∥ E_{i n} x ∥^{2} = ⟨ x, E_{i n}^{†} E_{i n} x ⟩ = ∥ x ∥^{2}$ . The same adjoint identity gives $∥ E_{o u t} y ∥^{2} = ⟨ y, E_{o u t}^{†} E_{o u t} y ⟩ = ∥ y ∥^{2}$ . Thus the input adjoint is contractive and both padding maps preserve length.

2.1givenF6step 1.1algebra

For $a = 1$ and $U = X \otimes I_{d}$ , where $X = (\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array})$ , the displayed matrix satisfies $X^{†} X = X X^{†} = I$ , so $U$ is unitary, but $Π_{a} U Π_{a} = 0$ . Hence the full projected operator need not be unitary.

3.1step 1.2F1F2F3algebra∎

For a unit $z \in C^{d}$ , if $E_{i n}^{†} z \neq 0$ , normalize that vector in the maximum defining [F3]; if it is zero, its image under $A$ is zero. In either case, $∥ E_{o u t} A E_{i n}^{†} z ∥ \leq ∥ A ∥_{o p} ∥ E_{i n}^{†} z ∥ \leq ∥ A ∥_{o p}$ , so $∥ \hat{A} ∥_{o p} \leq ∥ A ∥_{o p}$ . Conversely, for each unit $x \in C^{n}$ , $E_{i n} x$ is unit and $∥ \hat{A} E_{i n} x ∥ = ∥ E_{o u t} A x ∥ = ∥ A x ∥$ . Taking suprema yields $∥ \hat{A} ∥_{o p} = ∥ A ∥_{o p}$ by [F3].

Depends on

Used by

LCU block-encoding construction Algorithm
Product block encoding with separate ancillas Algorithm
QSVT implementation of a bounded matrix function Algorithm
Block-encoded QLSP input and singular-gap promise Definition
Block-encoding oracle and implementation cost model Definition
Projected-unitary encoding and singular vectors Definition
Qubitization access model Definition
A bounded polynomial approximation to a scaled exponential Example
Sparse diagonal block-encoded linear system Example
A projected unitary block is a contraction Lemma
Clean sparse-state preparation from sorted XOR locations Lemma
Hermitian block-encoding signal subspaces Lemma
Projected block identity for a supplied LCU circuit Lemma
Rescaling a matrix-function target for QSVT Lemma
Adjoint block encoding from inverse access Theorem
Correctness and access cost of sparse block encoding Theorem
LCU projected-block correctness Theorem
Product block-encoding error bound Theorem
QSVT robustness, approximation error, and resources Theorem

Dependency tree · two levels

33 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Andrew M. Childs, Lecture Notes on Quantum Algorithms, Chapters 28–29 (17 April 2025) (standard reference, not scraped)
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, Quantum singular value transformation and beyond, Definition 43 (standard reference, not scraped)