Block Encodings

Write $T^{†}$ for the adjoint $T^{\ast }$ characterized by The adjoint $T^{\ast }:W\to V$ is characterised by $⟨Tv,w{⟩}_W=⟨v,T^{\ast }w{⟩}_V$. Fix integers $m,n\ge 1$, $a\ge 0$, and $d\ge \max (m,n)$. On each coordinate space ${\mathbb{C}}^r$ use $⟨x,y{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{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 ${\mathbb{C}}^{2^a}$. For $A:{\mathbb{C}}^n\to {\mathbb{C}}^m$, choose as part of the data padding maps $E_{\mathrm{i}\mathrm{n}}:{\mathbb{C}}^n\to {\mathbb{C}}^d$ and $E_{\mathrm{o}\mathrm{u}\mathrm{t}}:{\mathbb{C}}^m\to {\mathbb{C}}^d$ satisfying $E_{\mathrm{i}\mathrm{n}}^{†}{E}_{\mathrm{i}\mathrm{n}}=I_n$ and $E_{\mathrm{o}\mathrm{u}\mathrm{t}}^{†}{E}_{\mathrm{o}\mathrm{u}\mathrm{t}}=I_m$. The default padding sends a coordinate vector to the same coordinates followed by zeros. Set $\widehat{A}:=E_{\mathrm{o}\mathrm{u}\mathrm{t}}A{E}_{\mathrm{i}\mathrm{n}}^{†}:{\mathbb{C}}^d\to {\mathbb{C}}^d$.

Let $J_a:{\mathbb{C}}^d\to {\mathbb{C}}^{2^a}\otimes {\mathbb{C}}^d$ be $J_{a}x=e_0\otimes x$, where $e_0$ is the all-zero computational basis vector, and let ${\mathrm{\Pi }}_a:=J_a{J}_a^{†}$. For a unitary $U$ on ${\mathbb{C}}^{2^a}\otimes {\mathbb{C}}^d$, its projected block is the endomorphism $B_U:=J_a^{†}U{J}_a$ of ${\mathbb{C}}^d$. It is not asserted to be unitary.

For $\alpha >0$ and $\epsilon \ge 0$, the tuple $(U,a,\alpha ,\epsilon ,d,E_{\mathrm{i}\mathrm{n}},E_{\mathrm{o}\mathrm{u}\mathrm{t}})$ is an $(\alpha ,a,\epsilon )$ block encoding of $A$ when $\alpha \ge \mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$ and $\mathrm{\parallel }{B}_U-\widehat{A}\mathrm{/}\alpha {\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \epsilon$. The exact case is $\epsilon =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 ${\mathrm{\Pi }}_{a}U{\mathrm{\Pi }}_a$ to $\mathrm{ran}({\mathrm{\Pi }}_a)$, transported to ${\mathbb{C}}^d$ by $J_a$; it does not regard ${\mathrm{\Pi }}_{a}U{\mathrm{\Pi }}_a$ as a unitary.

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

For a finite system space, an ancilla injection $J_{a}x=e_0\otimes x$, and a unitary $U$ on the joint space, the projected block $B_U=J_a^{†}U{J}_a$ satisfies $\mathrm{\parallel }{B}_U{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 1$. Consequently, every exact $(\alpha ,a,0)$ block encoding of $A$ satisfies $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \alpha$.

An access instance for a finite family of block-encoding unitaries $U_j$ records, as separate supplied operations, each of $U_j$, $U_j^{†}$, controlled-$U_j$, and controlled-$U_j^{†}$ that an algorithm may call. A call to one operation does not imply access to another.

Whenever a family SELECT is used, the instance specifies extensions ${\tilde{U}}_j$ acting on one common ordered target register. For a nonempty family on the same system ${\mathbb{C}}^d$ with ancilla widths $a_j$, set $a_{\ast }:={\max }_j{a}_j$ and use ${\tilde{U}}_j:=I_{2^{a_{\ast }-a_j}}\otimes U_j$, with the unused ancillas preceding the original ancillas and the system. This identity extension preserves the all-zero block. If system registers also differ, the common system register, its identifications, and unitary extensions preserving the declared encoded blocks must be supplied explicitly before forming SELECT. For a family indexed by $0\le j<m$ and a selector register of dimension $D\ge \max \{m,1\}$, the family SELECT is

$\mathrm{S}\mathrm{E}\mathrm{L}\mathrm{E}\mathrm{C}\mathrm{T}:={\sum }_{j=0}^{m-1}\mathrm{\mid }j⟩⟨j\mathrm{\mid }\otimes {\tilde{U}}_j+{\sum }_{j=m}^{D-1}\mathrm{\mid }j⟩⟨j\mathrm{\mid }\otimes I,$

where $I$ acts on the common target register and empty sums are zero. The instance records whether this complete unitary is supplied as one oracle or must be assembled from separately controlled calls; any required extensions and register routing have declared implementation costs.

For every supplied circuit operation $O$, the instance records the applicable circuit-description length, gate count and gate set, depth, total width, and clean and dirty work-ancilla counts; for a uniform family it records the full-description generator time. It separately records each named oracle-query count, classical postprocessing time and space, matrix-data and coefficient-table reading or storage, state-preparation cost, and target precision and its bit encoding when the task is approximate. These coordinates follow Circuit-family and computation cost model and Full-list uniform quantum circuit family; an inapplicable coordinate is marked not applicable, not silently zero. A bare matrix $A$ supplies none of these circuits or access rights. If an operation is compiled from matrix entries or a coefficient table, its data access, synthesis, precision, and classical costs are recorded separately. The cost of a SELECT implementation includes its controls and relative phases unless those are listed as separate supplied primitives. These block-encoding constructions include no measurement or classical-output step; a consumer's measurement and output costs are accounted separately.

Inputs. An integer $n\ge 1$, square matrices $A,B\in {\mathbb{C}}^{n\times n}$, positive normalizations ${\alpha }_A,{\alpha }_B$, and unitaries $U_A,U_B$ giving $({\alpha }_A,a_A,{\epsilon }_A)$ and $({\alpha }_B,a_B,{\epsilon }_B)$ block encodings, with ${\alpha }_A\ge \mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$ and ${\alpha }_B\ge \mathrm{\parallel }B{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$. Their access and implementation costs are supplied separately under Block-encoding oracle and implementation cost model.

Construction. Put the ancillas in the fixed order $A$-ancilla, $B$-ancilla, system. Let $V_A$ act by $U_A$ on the $A$-ancilla and system and by the identity on the $B$-ancilla. Let $V_B$ act by $U_B$ on the $B$-ancilla and system and by the identity on the $A$-ancilla. Return the unitary $W:=V_A{V}_B$, so $V_B$ acts first, and use all $a_A+a_B$ ancillas for the projected block. No intermediate measurement or reset is performed. The resulting normalization is ${\alpha }_A{\alpha }_B$.

The precise normalized product error bound is proved in Product block-encoding error bound.

Suppose $U$ is an $(\alpha ,a,\epsilon )$ block encoding of a square matrix $A$ with $\alpha >0$. If an implementation of $U^{†}$ is separately supplied, then its zero-ancilla compression is $B_U^{†}$ and

${\parallel B_U^{†}-\frac{A^{†}}{\alpha }\parallel }_{\mathrm{o}\mathrm{p}}={\parallel B_U-\frac{A}{\alpha }\parallel }_{\mathrm{o}\mathrm{p}}\le \epsilon \mathrm{.}$

For the declared rectangular padding $(E_{\mathrm{i}\mathrm{n}},E_{\mathrm{o}\mathrm{u}\mathrm{t}})$ of Finite block encoding, the same unitary $U^{†}$ encodes $A^{†}$ with the input and output embeddings swapped to $(E_{\mathrm{o}\mathrm{u}\mathrm{t}},E_{\mathrm{i}\mathrm{n}})$. The inverse circuit is an access requirement, not a free consequence of a matrix description.

Under the inputs and register order of Product block encoding with separate ancillas, let $C_A$ and $C_B$ be the two normalized compressed blocks, so $\mathrm{\parallel }{C}_A-A\mathrm{/}{\alpha }_A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le {\epsilon }_A$ and $\mathrm{\parallel }{C}_B-B\mathrm{/}{\alpha }_B{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le {\epsilon }_B$. The all-zero block of the constructed unitary is $C_A{C}_B$. It obeys

${\parallel C_A{C}_B-\frac{AB}{{\alpha }_A{\alpha }_B}\parallel }_{\mathrm{o}\mathrm{p}}\le {\epsilon }_A\frac{\mathrm{\parallel }B{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}}{{\alpha }_B}+{\epsilon }_B\frac{\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}}{{\alpha }_A}+{\epsilon }_A{\epsilon }_B\le {\epsilon }_A+{\epsilon }_B+{\epsilon }_A{\epsilon }_B\mathrm{.}$

Because each $C_A$ is itself a projected unitary block and hence a contraction, the sharper bound $\mathrm{\parallel }{C}_A{C}_B-AB\mathrm{/}({\alpha }_A{\alpha }_B){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le {\epsilon }_B+{\epsilon }_A\mathrm{\parallel }B{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\mathrm{/}{\alpha }_B\le {\epsilon }_A+{\epsilon }_B$ also holds. In particular the product is an $({\alpha }_A{\alpha }_B,a_A+a_B,{\epsilon }_A+{\epsilon }_B+{\epsilon }_A{\epsilon }_B)$ block encoding of $AB$.

Let $n\ge 1$ and $k\ge 1$, let $A_i\in {\mathbb{C}}^{n\times n}$, and let ${\alpha }_i>0$ satisfy $\mathrm{\parallel }{A}_i{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le {\alpha }_i$. Suppose the separately padded block encodings have compressed blocks $B_i=A_i\mathrm{/}{\alpha }_i+E_i$ with $\mathrm{\parallel }{E}_i{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le {\epsilon }_i$ and ${\epsilon }_i\ge 0$. Composing them on separate ancillas in the declared order gives normalization ${\prod }_{i=1}^k{\alpha }_i$ and an all-zero block $B_1\cdots B_k$ satisfying

${\parallel B_1\cdots B_k-\frac{A_1\cdots A_k}{{\prod }_{i=1}^k{\alpha }_i}\parallel }_{\mathrm{o}\mathrm{p}}\le {\sum }_{i=1}^k{\epsilon }_i{\prod }_{j\mathrm{\ne }i}(1+{\epsilon }_j)\mathrm{.}$

Inputs. Integers $n\ge 1$ and $m\ge 1$, a finite family of square matrices $A_j\in {\mathbb{C}}^{n\times n}$, positive numbers ${\alpha }_j\ge \mathrm{\parallel }{A}_j{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$, and exact $({\alpha }_j,a_j,0)$ block-encoding unitaries $U_j$. Also supply coefficients ${\beta }_j\in \mathbb{C}$ after omitting zero coefficients, with $\mathrm{\Lambda }:={\sum }_{j=0}^{m-1}\mathrm{\mid }{\beta }_j\mathrm{\mid }{\alpha }_j>0$. The component circuits and their controlled access are separate access inputs.

Instructions. Let $a_{\ast }:={\max }_j{a}_j$. Extend each component unitary to the common ordered ancilla register by identities on its unused ancillas, so its all-zero block is unchanged. Let $b:=\lceil {\log }_{2}m\rceil$, $D:=2^b$, and provide a unitary $P$ on the $b$-qubit coefficient register satisfying

$P\mathrm{\mid }{0}^b⟩=\mathrm{\mid }\chi ⟩:={\sum }_{j=0}^{m-1}\sqrt{\frac{\mathrm{\mid }{\beta }_j\mathrm{\mid }{\alpha }_j}{\mathrm{\Lambda }}}\mathrm{\mid }j⟩\mathrm{.}$

The squared amplitudes sum to one by the definition of $\mathrm{\Lambda }$. Define the unitary

$\mathrm{S}\mathrm{E}\mathrm{L}\mathrm{E}\mathrm{C}\mathrm{T}:={\sum }_{j=0}^{m-1}\mathrm{\mid }j⟩⟨j\mathrm{\mid }\otimes \frac{{\beta }_j}{\mathrm{\mid }{\beta }_j\mathrm{\mid }}{U}_j+{\sum }_{j=m}^{D-1}\mathrm{\mid }j⟩⟨j\mathrm{\mid }\otimes I,$

where each $U_j$ acts on its padded component ancilla and the data register; an empty second sum is zero. Return $W:=P^{†}\mathrm{S}\mathrm{E}\mathrm{L}\mathrm{E}\mathrm{C}\mathrm{T}P$, acting on the coefficient register, common component ancillas, and data system.

The instance must supply or compile $P$, $P^{†}$, and SELECT, and state the cost of each separately. A coefficient table is not itself a state-preparation circuit; table access, synthesis, controlled component calls, phases, precision, and classical preprocessing are charged under Block-encoding oracle and implementation cost model.

If $P$ is synthesized from the explicit exact normalized amplitude table $(\sqrt{w_j}{)}_{j<D}$, where $w_j:=\mathrm{\mid }{\beta }_j\mathrm{\mid }{\alpha }_j\mathrm{/}\mathrm{\Lambda }$ for $j<m$ and $w_j:=0$ for $j\ge m$, the exact-table procedure QC24 State Preparation is an optional construction. Since zero coefficients were omitted and each ${\alpha }_j>0$, $w_0>0$ and the first nonzero amplitude $\sqrt{w_0}$ is positive real. The state-preparation procedure omits only this reference phase, which is $0$ here, so the prepared vector equals $\mathrm{\mid }\chi ⟩$ exactly. Under its ideal continuous-angle model, QC24 State Preparation Rotation Level Upper Bound gives at most $D-1$ prefix rotations, at most $D$ phases, $O((b+1)D)$ bounded-arity gates and serial depth, and at most $\max \{b-1,0\}$ reusable clean work bits. Supply or compile the inverse circuit $P^{†}$ separately and charge it separately. If the table uses exactly $s$ bits for each real and imaginary coordinate, QC24 Explicit State-Preparation Cost Guarantee separately charges its $2Ds$ input bits and full-table preprocessing scan. These suppliers assert no finite-alphabet arbitrary-angle implementation or Turing bit-time bound; a supplied circuit for $P$ instead carries its own declared costs.

The current XOR-valued interface Coherent XOR function oracle does not itself implement this unitary-valued SELECT; if SELECT is assembled from component calls, its separate controlled-call and phase construction must be supplied and costed.

The projected block and normalization of the returned unitary are proved in LCU projected-block correctness.

Under the exact inputs and instructions of LCU block-encoding construction, the all-zero coefficient-index and component-ancilla block of $W=P^{†}\mathrm{S}\mathrm{E}\mathrm{L}\mathrm{E}\mathrm{C}\mathrm{T}P$ is

$\frac{{\sum }_{j=0}^{m-1}{\beta }_j{A}_j}{\mathrm{\Lambda }}\mathrm{.}$

Moreover, $\mathrm{\parallel }{\sum }_j{\beta }_j{A}_j{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \mathrm{\Lambda }$, so the constructed unitary is an $(\mathrm{\Lambda },b+a_{\ast },0)$ block encoding of ${\sum }_j{\beta }_j{A}_j$.

For one LCU construction, the normalization is $\mathrm{\Lambda }$ and each additive cost coordinate for the sequential operations is the sum of the declared costs of PREPARE, SELECT, and PREPARE${}^{†}$; a SELECT implementation assembled from controlled component unitaries includes those calls and phases in its declared cost. For a two-factor product construction, the normalization is ${\alpha }_A{\alpha }_B$ and the query and gate counts are the sums of the two supplied encoding costs in the chosen order. Any explicit wire permutation or control wrapper is included in a supplied operation's cost or charged as a separate operation. The normalized error is bounded by Product block-encoding error bound.

Matrix-data access, coefficient-table access and storage, state preparation and its inverse, controlled access, angle or entry precision, classical preprocessing, and compilation remain separate cost coordinates. This result counts declared primitives; it does not synthesize a circuit from a bare matrix or assign an absent primitive zero cost.