Block encoding¶

Build a unitary circuit U whose all-zero ancilla block is A / alpha for a square matrix, a Pauli sum or a circulant A, and get alpha, the ancilla count and an error bound with it. U on a + n qubits is an (alpha, a, eps) block encoding of the n-qubit operator A when || A - alpha (<0^a| ⊗ I) U (|0^a> ⊗ I) || <= eps (Gilyén, Su, Low and Wiebe, arXiv:1806.01838v1, Definition 43).

Import the functions and records below from nwqlib.subroutines.block_encoding. Plan the two general constructions of A = Z + 0.5 X, then build the second:

import numpy as np
from nwqlib.subroutines.block_encoding import (
    build_block_encoding_from_plan,
    plan_block_encoding,
)

A = np.array([[1.0, 0.5], [0.5, -1.0]])
for name in ("pauli_lcu", "dense_dilation"):
    plan = plan_block_encoding(A, implementation=name)
    print(plan.implementation, round(plan.alpha, 10), plan.num_ancillas)
encoding = build_block_encoding_from_plan(plan)
print(encoding.circuit.num_qubits)

multiplexed_pauli 1.5 1
dense_dilation 1.1180339887 1
2

The Pauli construction's alpha is the coefficient 1-norm 1 + 0.5, and the dense dilation's is the spectral norm sqrt(5)/2. build_block_encoding(A) plans and builds in one call, and its default implementation="auto" chooses the construction. Inside a Program, select_block_encoding chooses the encoding of a block, and Compose blocks explains composition, control, adjoints and circuit construction.

Constructions¶

Every implementation places A / alpha in the all-zero ancilla block. Ancilla registers precede the system register, so they occupy the low-order bits of Qiskit's little-endian index, and block_encoding_top_left reads the block at stride 2**num_ancillas.

Implementation	Encoded operator and `alpha`	Ancillas	Reason for the construction
`multiplexed_pauli`, requested as `pauli_lcu`	`A = sum_j c_j P_j` from a Pauli decomposition, with `alpha` the coefficient 1-norm	`ceil(log2 L)` address qubits for `L` terms	Exact for the supplied terms and applicable to any square power-of-two matrix. Each system qubit's multiplexor reads only the address bits on which its Pauli factor depends. The cost grows with the number of terms.
`banded`	Circulant `A = sum_b beta_b S^b`, with `alpha` the band-coefficient 1-norm	`ceil(log2 B)` address qubits for `B` bands	Exact without forming a dense matrix. Its `alpha` never exceeds `s * max_b abs(beta_b)`, the normalization of the sparse-access circulant circuit of Camps et al. (arXiv:2203.10236v4) with `s` padded bands.
`dense_dilation`	Any square power-of-two matrix, with `alpha` equal to the spectral norm unless a normalization is supplied	One ancilla, circuit qubit 0	Exact with the smallest `alpha` that admits zero error, at the cost of synthesizing one dense unitary on `n + 1` qubits. It serves small validation instances.

Build an encoding¶

build_block_encoding ¶

build_block_encoding(operator: Any, *, implementation: str = 'auto', max_bytes: int = DEFAULT_MAX_BYTES, max_work: int = DEFAULT_MAX_BLOCK_WORK) -> BlockEncoding

Build a block-encoding circuit of a square matrix, a Pauli sum or a circulant.

The function chooses the construction as plan_block_encoding does and builds it. It computes one dense SVD and uses it for the normalization, an equal-cost comparison and the completion. The constructions table lists what each construction encodes, its alpha and its ancillas.

Parameters:

operator (array_like | PauliDecomposition | BandSpecification) –

A dense square matrix (power-of-two dimension), a PauliDecomposition whose kept terms define the operator, or a BandSpecification describing a periodic banded Toeplitz operator without forming its matrix.
implementation (str, default: 'auto' ) –

"auto" (default), "pauli_lcu", "banded", or "dense_dilation". "multiplexed_pauli" is accepted as the resolved name of "pauli_lcu". "auto" looks for exact banded structure first, then compares the per-query CX counts of the Pauli and dense-dilation constructions without building either one.
max_bytes (int, default: DEFAULT_MAX_BYTES ) –

Default 10 GB (decimal, 10_000_000_000 bytes). Limit in bytes on the array data that each planning or construction step holds at the same time, checked before the step allocates it. NumPy, LAPACK and Qiskit internal workspace and Python object overhead are not counted, except in the circulant classification of a Pauli input, which counts its Python integers, parsed tuples, Fraction wrappers and dictionary entries, and a fixed allowance of 65,536 bytes for scalar bookkeeping and ndarray headers.
max_work (int, default: DEFAULT_MAX_BLOCK_WORK ) –

Default 1_000_000_000. Limit on the work of each step, in NWQLib's work units, which estimate scalar operations: d**3 for a product of two d-square matrices and 8 d**3 for a dense SVD. Planning, the dense SVD and construction are each checked against it separately.

Returns:

encoding ( BlockEncoding ) –

The circuit with its alpha, num_ancillas and error_bound.

Raises:

ValueError –

For unknown implementation names, operator and implementation mismatches, or a step that exceeds max_bytes or max_work.
OverflowError –

If structural error-bound arithmetic overflows.
FloatingPointError –

If a structural error bound is nonfinite.

Examples:

A = [[1, 0.5], [0.5, -1]] has spectral norm sqrt(5)/2 = 1.1180339887.... For this one-qubit matrix "auto" chooses the one-ancilla dense dilation, whose alpha is that norm, and alpha times the all-zero ancilla block of the circuit's unitary is A:

>>> import numpy as np
>>> from qiskit.quantum_info import Operator
>>> from nwqlib.subroutines.block_encoding import (
...     block_encoding_top_left, build_block_encoding)
>>> A = np.array([[1.0, 0.5], [0.5, -1.0]])
>>> encoding = build_block_encoding(A)
>>> print(encoding.implementation, round(encoding.alpha, 10))
dense_dilation 1.1180339887
>>> U = Operator(encoding.circuit).data
>>> block = block_encoding_top_left(U, num_ancillas=1)
>>> print(np.allclose(encoding.alpha * block, A))
True

plan_block_encoding ¶

plan_block_encoding(operator: Any, *, implementation: str = 'auto', normalization: float | None = None, max_bytes: int = DEFAULT_MAX_BYTES, max_work: int = DEFAULT_MAX_BLOCK_WORK) -> BlockEncodingPlan

Choose a block encoding and compute its alpha, width and error bound without building it.

An exact circulant, either a supplied BandSpecification or structure detected with zero error, goes to banded first. Otherwise "auto" compares the per-query CX counts of multiplexed Pauli SELECT and dense dilation and selects the smaller. A tie selects the smaller alpha, with dense dilation winning when both alpha values are equal. Automatic routing never introduces an approximate structure. An explicit "banded" request keeps the detector tolerance and records the resulting bound as error_bound. build_block_encoding_from_plan builds the returned plan's construction without comparing candidates again. Pass it the same max_bytes and max_work.

A supplied normalization becomes alpha only when the plan uses dense dilation. Without one, dense dilation uses the optimal spectral normalization ||A||_2. Pauli SELECT always uses its coefficient 1-norm. Arithmetic failures in structural error bounds propagate rather than selecting another encoding without the required bound. For a PauliDecomposition, the target operator is its kept terms. The encoding bound does not include loss from an earlier decomposition, so its caller must carry any original-to-kept approximation separately. The plan computes the normalization without keeping the singular vectors, so building it later computes its own SVD for the synthesis.

Parameters:

operator (array_like | PauliDecomposition | BandSpecification) –

The operator A, as for build_block_encoding.
implementation (str, default: 'auto' ) –

"auto" (default), "pauli_lcu", "multiplexed_pauli", "banded" or "dense_dilation".
normalization (float | None, default: None ) –

alpha to use if the plan is a dense dilation. Default None, which selects ||A||_2.
max_bytes (int, default: DEFAULT_MAX_BYTES ) –

Default 10 GB (decimal, 10_000_000_000 bytes). Limit on the array bytes of each planning step, as for build_block_encoding.
max_work (int, default: DEFAULT_MAX_BLOCK_WORK ) –

Default 1_000_000_000. Limit on the work of each planning step, as for build_block_encoding.

Returns:

plan ( BlockEncodingPlan ) –

The chosen construction with its alpha, num_ancillas and error_bound.

Raises:

ValueError –

For unknown implementation names or operator/implementation mismatches.
OverflowError –

If structural error-bound arithmetic overflows.
FloatingPointError –

If a structural error bound is nonfinite.

build_block_encoding_from_plan ¶

build_block_encoding_from_plan(plan: BlockEncodingPlan, *, max_bytes=DEFAULT_MAX_BYTES, max_work=DEFAULT_MAX_BLOCK_WORK) -> BlockEncoding

Build the circuit of a BlockEncodingPlan without choosing again.

Parameters:

plan (BlockEncodingPlan) –

A plan from plan_block_encoding.
max_bytes (int, default: DEFAULT_MAX_BYTES ) –

Default 10 GB (decimal, 10_000_000_000 bytes). Pass the value used for the plan.
max_work (int, default: DEFAULT_MAX_BLOCK_WORK ) –

Default 1_000_000_000. Pass the value used for the plan.

Returns:

encoding ( BlockEncoding ) –

The circuit of plan.implementation, with the plan's alpha, num_ancillas and error_bound.

Raises:

ValueError –

If a construction step exceeds max_bytes or max_work.

build_banded_block_encoding ¶

build_banded_block_encoding(operator: Any, *, requested_implementation: str = 'banded') -> BlockEncoding

Block-encode a periodic banded Toeplitz operator as a linear combination of cyclic shifts.

The address PREP is the direct magnitude and phase tree of build_qiskit_state_preparation over the 2**a band addresses. It is not a declared PREP block, so a Run's max_direct_amplitudes does not apply to it. Planning checks it at 64 * 2**a * (q + 16) bytes and 32 * 2**a * q**2 work for q system qubits, and with at most 2**q distinct bands that allows at most 2**13 addresses at a max_work of 10**8 and 2**16 at the default of 10**9, which QLS shares.

Parameters:

operator (BandSpecification) –

The bands. No dense matrix is formed. build_block_encoding detects bands in a dense matrix.
requested_implementation (str, default: 'banded' ) –

Default "banded". Implementation name recorded as requested.

Returns:

encoding ( BlockEncoding ) –

The circuit with alpha = sum_b |beta_b|, ceil(log2 num_bands) ancillas in the low-order lcu_control register, and zero algebraic error for the given specification.

Raises:

TypeError –

If operator is not a BandSpecification.
ValueError –

For invalid band specifications.

block_encoding_top_left ¶

block_encoding_top_left(unitary: Any, *, num_ancillas: int) -> ndarray

Return the all-zero ancilla block of a block-encoding unitary matrix.

The ancilla register precedes the system register, so the ancilla bits are the low-order bits of Qiskit's little-endian index, and the block entry (A / alpha)[s', s] sits at row s' * 2**num_ancillas and column s * 2**num_ancillas. The function reads the matrix at that stride.

Parameters:

unitary (array_like) –

Full unitary matrix of the circuit, for example Operator(encoding.circuit).data.
num_ancillas (int) –

Number of ancilla qubits.

Returns:

block ( ndarray ) –

The encoded A / alpha block.

projector_complement_matrix ¶

projector_complement_matrix(state: Any, *, dimension: int | None = None) -> ndarray

Return the projector I - |state><state| onto the complement of a state, as a dense matrix.

The QLS shortcut forms G_t = Q_{b'} A_t with Q_b = I - b b^dagger (Dalzell, arXiv:2406.12086v2, Eqs. (2) and (11)). The input is normalized here, and a larger dimension zero-pads it.

Parameters:

state (array_like) –

Nonzero state vector.
dimension (int | None, default: None ) –

Default None, which uses the length of state. A larger value zero-pads the state.

Returns:

projector ( ndarray ) –

The complex dimension-square matrix I - |s><s| for the normalized, padded state s.

Raises:

ValueError –

If the state has zero norm or is longer than dimension.

Inputs and results¶

BandSpecification ¶

BandSpecification(*, offsets: tuple[int, ...], coefficients: tuple[complex, ...], num_qubits: int)

A periodic banded Toeplitz (circulant) matrix given by its bands, without forming the matrix.

The matrix is A = sum_b beta_b S^b with the cyclic shift S |x> = |x + 1 mod 2**num_qubits>. Build it with keyword arguments, for example BandSpecification(offsets=(-1, 0, 1), coefficients=(-1, 2, -1), num_qubits=3) for A = 2 I - S - S^-1 on 8 points, and pass it to build_block_encoding. All three arguments are required. The builder checks that num_qubits is positive, that there is one coefficient per offset and at least one band, that the offsets are distinct modulo 2**num_qubits and that no coefficient is zero.

This specification is periodic-only. For broader structured banded block encodings, see Camps et al., arXiv:2203.10236v4, Sec. 4.

Parameters:

offsets (tuple[int, ...]) –

Signed band offsets b. Band b couples |x> to |x + b mod 2**num_qubits>.
coefficients (tuple[complex, ...]) –

One nonzero complex coefficient beta_b per offset.
num_qubits (int) –

Number of system qubits (dimension 2**num_qubits).

to_dict ¶

to_dict() -> dict[str, Any]

Return a JSON-like band-specification record.

BlockEncoding ¶

BlockEncoding(*, circuit: QuantumCircuit, alpha: float, num_ancillas: int, system_qubits: int, error_bound: float | None, implementation: str, metadata: Mapping[str, Any])

A block-encoding circuit with its alpha, ancilla count and error bound.

build_block_encoding, build_block_encoding_from_plan and build_banded_block_encoding return it. The circuit is the answer: its all-zero ancilla block is A / alpha, which block_encoding_top_left reads from the circuit's unitary. Construction requires a finite positive alpha, a finite nonnegative error_bound when one is given, and nonnegative integer widths. These checks do not inspect the circuit or prove its operator relation. The fields below are read-only.

Attributes:

circuit (QuantumCircuit) –

Unitary circuit whose all-zero ancilla block encodes A / alpha.
alpha (float) –

Subnormalization alpha in the units of A.
num_ancillas (int) –

Number of ancilla qubits (placed before the system register, low-order bits).
system_qubits (int) –

Number of system qubits.
error_bound (float | None) –

Operator-norm bound on || A - alpha * encoded block || in the units of A, or None when unavailable.
implementation (str) –

Construction used: "multiplexed_pauli", "banded" or "dense_dilation".
metadata (Mapping[str, Any]) –

JSON-like record of how the circuit was built. Where it repeats the subnormalization, ancilla count, error or construction, the fields above are the values to use.

to_dict ¶

to_dict() -> dict[str, Any]

Return a JSON-like block-encoding summary.

BlockEncodingPlan ¶

BlockEncodingPlan(*, requested_implementation: str, implementation: str, alpha: float, num_ancillas: int, system_qubits: int, error_bound: float, source: Any, decomposition: Any | None, detail: Mapping[str, Any])

The block encoding to build, chosen before any circuit exists.

plan_block_encoding returns it, and build_block_encoding_from_plan builds exactly this construction from source and decomposition without choosing again. alpha, num_ancillas and error_bound are known before the circuit is built. Construction requires a finite alpha, positive except for "exact_zero", a finite nonnegative error_bound and nonnegative integer widths. The fields below are read-only.

Attributes:

requested_implementation (str) –

Name the caller passed: "auto", "pauli_lcu", "multiplexed_pauli", "banded" or "dense_dilation".
implementation (str) –

Construction the builder will use: "multiplexed_pauli", "banded" or "dense_dilation". LCHS's compiled QSP SELECT also records "exact_zero" for the H part of A = L + iH when relative pruning keeps none of its Pauli terms. No encoding is built for that part: the record has zero alpha, error and ancilla count, no source and no decomposition, it cannot be built into a circuit, and it introduces no division by zero.
alpha (float) –

Subnormalization in the units of A. The all-zero ancilla block of the unitary is A / alpha. It is the Pauli coefficient 1-norm for multiplexed Pauli, the band-coefficient 1-norm for banded, and ||A||_2 or the supplied normalization for dense dilation. Zero only for "exact_zero".
num_ancillas (int) –

Ancilla qubits of the encoding: ceil(log2 L) for L Pauli terms, ceil(log2 B) for B bands, 1 for dense dilation and 0 for "exact_zero".
system_qubits (int) –

Number n of system qubits. A acts on dimension 2**n.
error_bound (float) –

Upper bound on ||A - alpha * block||_2 in the units of A. plan_block_encoding sets 0 for multiplexed Pauli, the circulant-detection bound for a detected banded input, and the outward-rounded normalization residual bound for dense dilation. A caller that pruned Pauli terms first, such as LCHS's compiled QSP SELECT, adds the pruned coefficient mass.
source (Any) –

Input the builder reads: the complex128 2**n-square matrix for dense dilation (the converted input, or the dense expansion of a Pauli input), the BandSpecification for banded, the converted dense matrix or None (Pauli input) for multiplexed Pauli, and None for "exact_zero".
decomposition (Any | None) –

The PauliDecomposition whose terms SELECT applies for multiplexed Pauli. For dense dilation it is the Pauli form of the input, supplied or computed for the cost comparison, or None when dense dilation was requested for a dense matrix. plan_block_encoding sets None for banded plans. LCHS's compiled QSP SELECT attaches its kept terms to every plan it returns except "exact_zero", which has None.
detail (Mapping[str, Any]) –

JSON-like record of the choice. After a Pauli cost comparison it holds the SELECT gate counts (term count, padded table size, per-qubit effective control counts, the per-qubit projected address supports and CX counts), the predicted per-query CX of both candidates, the Pauli alpha and, when it was computed, the dense-dilation alpha, and the reason for the choice. For banded it holds the band count, how the bands were detected and the gate counts. It is empty when dense dilation was requested for a dense matrix. The Pauli and dense-dilation builders copy it into the circuit metadata, the Pauli builder builds SELECT from its dependency_supports, and the banded builder reads how the bands were detected.

to_dict ¶

to_dict() -> dict[str, Any]

Return the plan's scalar fields and its detail record as JSON-like data.

Choice, error bound and limits¶

How "auto" chooses:

An exact circulant goes to banded: a supplied BandSpecification, or a matrix or Pauli table whose band structure is detected with zero error.
Otherwise planning compares the per-query CX costs of the Pauli and dense constructions before it evaluates the dense normalization. A strict Pauli winner leaves the dense normalization uncomputed. A dense winner and an equal-cost comparison evaluate it.
Automatic banded detection requires exact stored structure, and automatic Pauli decomposition removes only exact zeros. Nonzero roundoff coefficients therefore stay in the term count and may change the choice. A supplied Pauli table whose exact-rational circulant residual is nonzero keeps its Pauli or dense route.

What error_bound covers, in the units of the supplied operator:

For dense dilation it bounds the normalization loss with an entrywise rounding bound and a row and column norm bound. The dense complement is formed by column scaling and one matrix product, followed by one explicit unitarity check. The residual of that check is a separate numerical check and does not bound transpilation or hardware error.
An explicit implementation="banded" keeps its detector tolerance and reports a bound on the difference between the supplied and the banded operator: from row and column sums for dense input, or the exact-rational coefficient residual for Pauli input. Planning and circuit construction count that bound once.
An exact BandSpecification has zero algebraic error. Gate-synthesis roundoff is outside this algebraic statement.

SVDs and limits:

build_block_encoding(A) computes one dense SVD and uses it for the normalization, an equal-cost comparison and the completion. plan_block_encoding(A) computes the normalization without keeping the singular vectors, so building that saved plan later computes its own SVD for the synthesis.
The plan and build functions take keyword-only max_bytes (default 10,000,000,000) and max_work (default 1,000,000,000). Dense conversion, Pauli classification and table construction, and the dense completion are checked against them before allocation or decomposition. Pass the intended limits to both a standalone plan and its later build. A larger explicit value is forwarded to the nested construction.
The work count is an operation estimate, and the counted array bytes do not bound undocumented SDK synthesis workspace or process memory. The DEFAULT_MAX_BLOCK_WORK row of Engineering constants gives the counted terms.

Source map¶

Code paths are relative to nwqlib.subroutines. Equation and section numbers refer to the listed arXiv versions.

Scientific step	Source	Location	Code
Block-encoding definition and `alpha` bookkeeping	Gilyén et al., arXiv:1806.01838v1	Definition 43	`block_encoding.core.BlockEncoding`
Spectral norm as the smallest zero-error `alpha`	Gilyén et al., arXiv:1806.01838v1	Remark after Definition 43	`block_encoding.core._dense_dilation_encoding`
One-ancilla dilation `[[B, K], [K, -B]]` with `K = W sqrt(I - S^2) V^dagger`	NWQLib derivation, stated in its docstring		`block_encoding.core._dense_dilation_encoding`
LCU block with `alpha` the coefficient 1-norm	Low and Chuang, arXiv:1610.06546v3, and Gilyén et al., arXiv:1806.01838v1	Lemma 5 and Eq. (10), and Lemma 52	`block_encoding.core._pauli_lcu_encoding`
Removing select bits on which a multiplexor does not depend	Shende, Bullock and Markov, quant-ph/0406176v5	Sec. 3	`_multiplexors.project_unitary_table_dependencies`; Pauli SELECT tables use the equivalent packed letter-code test `_multiplexors.local_pauli_dependencies`
Uniformly controlled unitary CX count	Qiskit `UCGate` synthesis, pinned by tests		`_multiplexors.projected_unitary_resource_law`
Coefficient-phase diagonal	Shende, Bullock and Markov, quant-ph/0406176v5	Theorem 7	`_multiplexors.append_control_diagonal_phases`
Cyclic shifts diagonalized by the QFT	NWQLib derivation, stated in the module docstring		`block_encoding.banded.build_banded_block_encoding`
Circulant normalization comparison	Camps, Lin, Van Beeumen and Yang, arXiv:2203.10236v4	Theorem 4.1 and Sec. 4.2	`block_encoding.banded` module docstring
Circulant certificate from Pauli terms	NWQLib derivation from Pauli orthogonality, stated in its docstring		`block_encoding.core._detect_banded_pauli_structure`
Dense routing CX count	Shende, Bullock and Markov, quant-ph/0406176v5	Eq. (19), p. 16, and Table 1, row QSD (l = 2, optimized), p. 14	`block_encoding.core._dense_dilation_predicted_cx`
Banded UCRZ tables at `2a` CX each, and for both Pauli and banded routes an address diagonal and a positive PREP tree at `2a - 2` CX each	Shende, Bullock and Markov, quant-ph/0406176v5, and Mottonen et al., quant-ph/0407010v1	Theorems 7 and 8, pp. 10-11, and Sec. II, p. 2, and Sec. III, Eq. (7), p. 3	`block_encoding.core._pauli_plan_detail`, `block_encoding.core._banded_plan`
Choice of construction, limit checks and plan reuse	NWQLib, described above and in `plan_block_encoding`		`block_encoding.core._plan_block_encoding`

Entries on other pages¶

select_block_encoding is documented on Extending NWQLib.