Block Encoding Algebra

English · 简体中文

Category C2 · Module oracq.algorithms.input_model.block_encoding · Stage V1

Overview

A block encoding hides the matrix \(A\) in the corner block of a larger unitary: the zero-signal block of \(U\) satisfies \((\langle 0| \otimes I)\, U\, (|0\rangle \otimes I) = A/\alpha\), with the normalization \(\alpha\) stored alongside the operation as the RIR module attribute be_alpha; precision is not part of the language core. This module provides the compositional arithmetic of BEs: linear combination (LCU), tensor, adjoint, signal-space dilation, direct sum, Kronecker sum, Boolean embedding, and explicit Pauli expansion of small matrices. Upper-layer algorithms (QSVT, qubitization, QLSS, low-rank decomposition, ODE solvers) all assemble their inputs on this algebra; the lowest-layer BlockEncoding type and the binary primitives identity / pauli_x / zero / scale / linear_combination / product live in operators.py.

Interface and input model

The input model is unified as BE: all entry points receive and return BlockEncoding (reflect_zero is a Builder helper).

lcu(terms)
tensor(a, b)
adjoint_be(a)
pad_signal(a, width)
kronecker_sum(a, b=None)
direct_sum(a, b)
projector(width, accepted)
truncated_shift(width, last)
pauli_word(word)
matrix_pauli_encoding(matrix, *, drop_tolerance=1e-12)
reflect_zero(builder, register, *, positive=False)

API entry points: lcu, tensor, adjoint_be, pad_signal

Semantics and output normalization of the main entry points:

Entry point	Semantics	Output alpha
lcu(terms)	PREPARE/SELECT composition of \(\sum_j c_j A_j\) (complex phases via a global phase; zero coefficients dropped, a single term degenerates to scale)	\(\sum_j \lvert c_j\rvert\, \alpha_j\)
tensor(a, b)	\(A \otimes B\)	\(\alpha_A \alpha_B\)
adjoint_be(a)	\(A^\dagger\)	\(\alpha_A\)
kronecker_sum(a, b)	\(A \otimes I + I \otimes B\)	\(\alpha_A + \alpha_B\)
direct_sum(a, b)	direct sum of same-width matrices (single select bit)	\(\alpha_A + \alpha_B\)
pauli_word(word) / matrix_pauli_encoding(matrix)	Pauli-word BE / explicit Pauli LCU of a small matrix	1 / LCU normalization

matrix_pauli_encoding computes the expansion coefficients analytically by accumulating phases column by column according to \(\operatorname{Tr}(P^\dagger M)/2^n\), drops terms with magnitude below drop_tolerance, and degenerates to zero when everything is zero; it accepts only square matrices of power-of-two dimension and at most 5 bits, is positioned as an explicit gate implementation for small-scale applications, and claims no quantum speedup for matrix input or classical expansion.

Implementation notes

lcu is the core combinator: the selector bit width is \(\lceil\log_2 L\rceil\), the weights \(\sqrt{\lvert c_j\rvert \alpha_j / \alpha}\) are prepared via gate_state_prep, each term is invoked controlled on its own signal partition, and an inverse preparation closes it; the binary linear_combination in operators.py is the isomorphic special case with a single selector, and together they cover the composition semantics. pad_signal only allows enlarging the signal space (shrinking is rejected), for late binding under the same signature. projector / truncated_shift construct the \(\alpha = 1\) BEs of Boolean embeddings, feeding structured assembly such as direct_sum; reflect_zero implements the positive/negative reflection about the signal zero state and is a shared building block for walk-type operators.

Applicability boundary: all compositions guarantee only corner-block semantics and alpha arithmetic; the mathematical claims of the input BEs are not checked; be_alpha must be a finite positive number — invalid values (0, negative numbers, True, inf) are rejected at construction time.

Validation approach

Category C2 (approximate continuous semantics; acceptance criteria in ../development/validation-plan.md §2). Consistent with the sparse.py / block_encoding.py rows of the validation coverage matrix; all three layers of evidence are in tests/core/test_language.py:BlockEncodingTests:

• Structural: in-class constructions and attribute assertions; test_invalid_alpha covers alpha validity (0, −1, True, and inf all raise ValidationError).

• Numerical: test_unequal_normalization_and_signed_sum (\(\mathrm{lc}(-0.5,\ 2I,\ 2,\ 3X)\) with normalization 7 and matrix \([[-1, 6], [6, -1]]\)), test_complex_coefficients (phases of complex coefficients enter the corner block), test_product_order_and_independent_signal_spaces (product order and signal-space partitioning, cross-checked element by element at \(k = 2\cos(0.4)/\sqrt{2}\)), test_zero_and_zero_coefficient (zero-coefficient and zero-matrix degeneration). The witnessing technique simulates each initial target basis state column by column, reads the zero-signal block amplitudes, and multiplies alpha back in (the same convention as assert_block_equals in tests/core/witness.py).

• Binding: test_alpha_survives_ir_serialization — after a JSON dumps/loads round trip of scale(4, identity(2)), be_alpha stays 4.

Known gaps and planned stages

No known gaps; stage V1 (the gap column of the sparse.py / block_encoding.py rows in the validation coverage matrix is empty).

Related links

• Source: src/oracq/algorithms/input_model/block_encoding.py (combinators) and src/oracq/algorithms/input_model/operators.py (the BlockEncoding type and binary primitives)

• Same-family pages: sparse matrix block encoding, QSVT matrix inversion, truncated Taylor block encoding

• API reference: Block-encoding composition

• Concepts: Oracles and operator representations

• Validation matrix: Validation coverage matrix

Numerical validation

Paper-level numerical validation script: tests/verification/verify_blockencoding.py (executed on real backends, no mocks, no skips; as of 2026-09-16 all 73 cases pass), artifact out/verification/blockencoding.json. This page corresponds to 12 cases: matrix-pauli-encoding-*, be-algebra-*, pauli-word-YZX, projector-w2-03, truncated-shift-w2-l3.

Experiment design: random Hermitian / non-Hermitian small matrices with a fixed seed are encoded via matrix_pauli_encoding, and seven combinators (tensor / adjoint / pad_signal / lcu with complex coefficients / kronecker_sum / direct_sum / product) each assemble one; the full program unitary is exported via OriginIR-ext and extracted with UniQC Circuit.to_matrix; harness.effective_block extracts the zero-signal effective block and reports an upper bound on the leakage of failure branches (signal ≠ 0); the expected matrices are assembled independently with numpy (Pauli-word convention: word[0] acts on the least significant bit). pauli_word (no signal bit, leakage exactly 0) and the Boolean embeddings projector / truncated_shift are likewise cross-checked element by element against explicit classical matrices. Each case is additionally crossed column by column with reference / rir-pysparq / adapter-pysparq (all deviations exactly 0), and α is cross-checked against an independently computed Pauli l1 bound.

Case	Scale	Backend paths	Metric	Value
matrix-pauli-encoding-2x2-general	2×2 non-Hermitian	originir-ext + to_matrix, three-backend cross	max_error	1.3e-16
matrix-pauli-encoding-4x4-hermitian	4×4 Hermitian	ditto	max_error	4.6e-16
same as above	—	—	α − independent Pauli l1	0 (exactly equal to the bound)
be-algebra-tensor	2×2 ⊗ 2×2	originir-ext + to_matrix	max_error	1.3e-16
be-algebra-adjoint	2×2 non-Hermitian	ditto	max_error	2.3e-16
be-algebra-pad-signal	signal +2 bits	ditto	max_error	1.2e-16
be-algebra-lcu-complex	complex coefficients 0.6+0.3j / −0.8	ditto	max_error	2.4e-16
be-algebra-kronecker-sum	A⊗I+I⊗B	ditto	max_error	2.5e-16
be-algebra-direct-sum	same-width direct sum	ditto	max_error	1.1e-16
be-algebra-product	A·C (non-Hermitian)	ditto	max_error	2.2e-16
pauli-word-YZX	3 bits, α=1	originir-ext + to_matrix	max_error / leakage	0 / 0
projector-w2-03 / truncated-shift-w2-l3	2 bits	ditto	max_error	0

Reproduction command:

PYTHONPATH=src /path/to/backend/python tests/verification/verify_blockencoding.py

Artifact: out/verification/blockencoding.json.