19Block encoding and quantum walks

A Hamiltonian need not be exponentiated directly

The time-evolution builders in Lesson 18 approximate an exponential of a fixed Hamiltonian. They are not the only way to expose its eigenvalues to a quantum algorithm. Another route embeds a normalized Hamiltonian into a larger unitary, then builds a walk whose phases encode the Hamiltonian spectrum through a known nonlinear relation.

Our chemical target remains neutral singlet N₂ at 1.85 Å in the selected active-space model. This new representation does not restore discarded virtual orbitals, replace cc-pVDZ with a complete basis, or correct a poor trial state. It changes the quantum algorithm used for the represented operator.

We will first derive ordinary Pauli LCU block encoding and its walk, then trace the repository’s factorized sum-of-squares route. The latter is concrete implemented functionality, but it has a specialized circuit and phase-estimation interface. It must not be mistaken for a generic controlled version of the ordinary LCU walk. No circuits, factorization, simulation, or resource estimates are executed in this lesson.

What “a block of a unitary” means

An ancilla is a working register in addition to the system register describing the electronic state. Let $B$ be a unitary on both. It block-encodes $H/\alpha$ when

Here $|0\rangle_a$ means all the designated ancillas are zero, and $\alpha>0$ is a normalization. A subblock of a unitary cannot have operator norm greater than one, so $\alpha\ge\|H\|$ is necessary for this exact form. The complete unitary is not the Hamiltonian; it contains additional blocks needed to preserve norm and reversibility.

Applied to a normalized system state, it has the structure

where the second term is orthogonal to the all-zero ancilla subspace. If the ancillas were measured and only zero outcomes retained, the success probability would be $\|H|\psi\rangle\|^2/\alpha^2$. The surviving system state would require normalization. Thus “implement a block encoding” does not mean deterministically apply the generally nonunitary $H$ to every input.

A quantum-walk algorithm can instead use that larger unitary coherently, without measuring those ancillas after each application. Understanding this distinction prevents a mistaken postselection cost model and the equally mistaken claim that a unitary circuit directly outputs all Hamiltonian information.

LCU: put coefficient magnitudes in PREPARE and signs in SELECT

Let

For real coefficients, define signed unitaries $V_j=\operatorname{sign}(h_j)P_j$. Pauli words are unitary and Hermitian. Since $\|P_j\|=1$, the triangle inequality gives $\|H\|\le\lambda$. The normalization can be larger than the actual operator norm, sometimes substantially.

PREPARE, denoted $A$, loads

These are amplitudes, not probabilities. SELECT applies the signed Pauli word conditioned on the index:

The complete block unitary is $B=A^\dagger S A$. Projecting the ancillas onto zero on both sides gives

The two square-root amplitudes, from prepare and unprepare, multiply to the required magnitude. Negative signs must survive in SELECT. Omitting them would block-encode another Hamiltonian with all-positive coefficients.

For a hand-worked example, take $H=0.6X-0.4Z$. Then $\lambda=1$, PREPARE amplitudes are $\sqrt{0.6}$ and $\sqrt{0.4}$, and SELECT applies X on address zero and −Z on address one. For system $|0\rangle$, the all-zero-ancilla branch is $-0.4|0\rangle+0.6|1\rangle$, with probability $0.16+0.36=0.52$ if measured. This is illustrative arithmetic, not a molecular or executed circuit result.

The current LCU builder and its numerical boundaries

The registered method is hamiltonian_unitary_builder/lcu. Its implementation accepts a Pauli-decomposition QubitOperator and checks Hermiticity. Settings are power=1, quantum_walk=False, and tolerance=1e-12. Here tolerance is the minimum acceptable coefficient L1 norm, not a requested block-encoding error and not a universal per-term truncation setting.

The builder counts terms to choose an index width, constructs a one-bit-per-mode synthetic wavefunction for the PREPARE amplitudes, and constructs a Select object containing integer control states, Pauli labels, signs, and system/index dimensions. These synthetic modes are coefficient-address bits, not extra chemical orbitals. With quantum_walk=False, the result wraps an LCUContainer; with true, it wraps an LCUWalkContainer with scale set to the coefficient absolute-sum. Both still require a circuit mapper.

A zero coefficient norm is rejected by default. Non-Hermitian complex coefficients are rejected by the container’s Hermiticity check; allowed negligible imaginary components are not a general complex non-Hermitian block-encoding capability. Combining duplicate Pauli labels before building is useful: otherwise the list length and coefficient absolute-sum can be needlessly enlarged, even when terms cancel.

There is a concrete screening subtlety. The norm and initial term count use stored coefficients, whereas PREPARE/SELECT construction calls get_real_coefficients() with its own default 1e-12 per-term filter. Tiny filtered entries can therefore leave a normalization or address-width mismatch relative to the retained list. At a sufficiently small total scale, an accepted norm can coexist with an empty filtered list. For a precision-controlled workflow, combine and screen an explicitly chosen operator first, budget that change, and make the norm and retained term list consistent rather than assuming the LCU tolerance controls all screening.

For a singleton, the builder constructs a zero-mode PREPARE wavefunction. That represents zero necessary address bits, but the generic default dense loader has a minimum declared width of one; abstract minimum address size and actual mapped ancillary allocation are not always identical. The PSP mapper also contains a no-PREPARE branch, but do not infer it is automatically used for every singleton constructed by the current LCU builder.

The LCU tests check square-root amplitudes, signs, address widths, zero-norm rejection, serialization, and particular full-block actions. They are source evidence, not tests run here. The block builder does not know an ordinary molecular core_energy: its input is the qubit operator. The active energy from the standard molecular mapping still needs the separately retained scalar added once.

PREPARE may have workspace, and that changes the circuit contract

A realistic PREPARE can act on index bits and workspace. Alias sampling, for example, prepares $\sum_j\sqrt{p_j}|j\rangle|g_j\rangle$, with garbage correlated with the index. That does not prepare a clean molecular trial state, as Lesson 16 emphasized. It can nevertheless be a valid LCU PREPARE if SELECT acts on the correct index and PREPARE-adjoint acts on the entire register afterward. The zero-ancilla block then uses the marginal probabilities $p_j$.

With finite alias precision, those probabilities become $\widetilde p_j$, so the represented block changes accordingly. Exact cleanup and the right sign phases still matter. Correct marginal probabilities alone do not establish that an arbitrary state-preparation routine has a usable adjoint after SELECT has imprinted phases.

The PSP mapper, registered as circuit_mapper/prepare_select_prepare, builds these subroutines with a nested prepare AlgorithmRef, defaulting to dense_pure_state. It requires a Q# callable, a declared width covering the SELECT index, and no externally owned phase-gradient suffix. A self-contained QROM loader may be appropriate; a shared-gradient variant is explicitly rejected by this mapper. A QASM-only child is not automatically interchangeable with a composable Q# operation.

The mapped register is [system | all PREPARE ancillas]. Alias sampling can increase the second portion far beyond the address width. SELECT uses only the leading index portion, while unprepare and the walk reflection must account for the necessary workspace. The controlled PSP variant supports one control at position zero and controls only SELECT, leaving PREPARE/unprepare unconditional. Its Q# specialization makes the control-zero branch cancel to identity. The controlled mapper does not provide arbitrary inherited target-index remapping.

QROM means a circuit for fixed classical lookup data, not a unit-cost physical QRAM promise. Alias comparisons, lookup words, signs, phase-gradient initialization where used, and uncomputation all contribute to the final resource count.

Why a walk has two phases for one energy

For the ideal signed-Pauli SELECT, $S=S^\dagger$ and $S^2=I$. Therefore $B=A^\dagger S A$ is also a Hermitian unitary. Define the reflection about the zero-ancilla subspace,

and the walk $W=RB$. A reflection leaves the specified subspace unchanged and negates its orthogonal complement. The repository’s PrepSelPrep.qs implements this order, including sign/global-phase corrections needed under outer control.

Let $H|E\rangle=E|E\rangle$, put $\mu=E/\lambda$, and define $|a\rangle=|0\rangle_a|E\rangle$. For $|\mu|<1$, there is a normalized orthogonal companion $|b\rangle$ such that

Because $B$ is a Hermitian involution, it acts within the two-dimensional span as

The walk eigenvalues are

This derivation explains the essential extra space. The raw unextended electronic eigenstate is not generally itself a single walk eigenstate. Even $|0\rangle_a|E\rangle$ lies in an enlarged invariant subspace and typically decomposes into the two walk eigenphase branches. At the endpoints the companion construction degenerates appropriately. A notebook shorthand writing one walk phase directly on a raw chemical state must not replace this contract.

If phase estimation measures fraction $\varphi$, the LCU-walk container reconstructs

The two branches $\varphi$ and $1-\varphi$ give the same energy. This is not the linear $-\mathrm{angle}/t$ decoder for time evolution. Powers introduce their own modular ambiguity and must be handled by the phase-estimation schedule, not ignored in a standalone decoder call.

An ideal block and walk can expose the spectrum without Trotter splitting error for the represented Hamiltonian. Integral truncation, coefficient screening, imperfect PREPARE probabilities, rotation synthesis, finite phase resolution, trial overlap, and physical noise remain. “No Trotter error” does not mean “exact chemistry” or “automatically lowest total cost.”

From the factorized Hamiltonian to squares

The factorized route uses the matrices from Lesson 12 rather than expanding every contribution into a long Pauli sum. Use $K$ active spatial orbitals, ranks $R$, basis rows $B_f$, and copies $C_f$. We use subscripts on the last two symbols to avoid confusing the basis count with the block unitary $B$.

For each rank/copy pair, define

Each real row $u_b^r$ is unit normalized, but different rows need not be orthogonal in the general factorized container. The two-electron tensor is reconstructed as $g_{pqrs}=\sum_{rc}M^{rc}_{pq}M^{rc}_{rs}$. In operator form, normal ordering introduces a one-body correction:

A hat here means the corresponding spin-summed one-body operator. The subtraction follows from anticommuting annihilation and creation operators; squaring a one-body operator is not purely a two-electron interaction.

The container also carries identity weights $w_B^{rc}$. They do not change the reconstructed integral tensor, but they change the square decomposition and its normalization. Put $q_{rc}=w_B^{rc}-\operatorname{tr}M^{rc}$, and define

Completing the square gives $\widehat h_1^{\prime}+\frac12\sum F_{rc}^2$, with the corresponding scalar subtraction. This is a representation identity before numerical truncation, not an effective Hamiltonian that removes more electrons.

Diagonalize the real symmetric $h_1^{\prime}$. A positive eigenvalue $v$ contributes $v n$, expressible as $(\sqrt v\,a)^\dagger(\sqrt v\,a)$. A negative eigenvalue $-v$, with $v>0$, can instead be written $v(1-n)-v$, using a hole generator $\sqrt v\,a^\dagger$. Hole here means absence of occupation in that rotated mode. There are two spin channels, hence two copies of the negative-mode scalar subtraction.

With these explicit generator definitions, the positive shifted operator is

The factor one-half on the spin-free squares belongs to these definitions. Alternatively one can absorb it into a generator $F_{rc}/\sqrt2$. Omitting it while retaining the same stored weights changes the Hamiltonian. The independent matrix constructions in the SOSSA tests and full-block tests make this normalization concrete.

The actual sum-of-squares data and mapper

The current class is SumOfSquaresContainer, wrapped in QubitOperator, not an assumed additional SumOfSquaresOperatorContainer API. It stores RotatedPaulis blocks containing rotation-angle rows, complex coefficient rows, and small Pauli label sets, plus dimensions and energy_shift metadata. .to_matrix() deliberately raises NotImplementedError; an ordinary Pauli representation must be rebuilt for a small direct matrix reference.

The registered qubit_mapper/sum_of_squares requires a FactorizedHamiltonianContainer, matching $2K$ modes, and untapered Jordan–Wigner mapping. Its validation checks the mapping name/count/tapering rather than proving an arbitrary custom table is canonical JW; use the factory mapping.

Its threshold=1e-12 screens eigenvalues of $h_1^{\prime}$, not final Pauli coefficients. Screened modes retain their outer-register slots with zero amplitude. Positive and screened slots precede negative slots. Negative tolerance and NaN are rejected; valid numerical data and a physically appropriate factorization remain prerequisites.

The one-body coefficient rows are $\sqrt{|v|}(1,\pm i)/2$, weighting X and Y in the rotated frame. The plus sign describes a particle annihilation generator and the minus sign a hole creation generator. For the spin-free term,

The stored two-body coefficient row is therefore the negative basis weights followed by the identity weight. Coherent spin selection supplies the explicit half in that expression. The mapper’s energy_shift includes the original core scalar. Do not add core_energy again after a decoder that already adds this shift.

Rotation rows encode unit vectors through $K-1$ neighboring Givens rotations, two-coordinate rotations that successively eliminate vector components. The Python routine works from the bottom using arctan2 and a hypotenuse update, preserving signs and quadrants. These rotations describe which orbital combination the simple X/Y/Z generator acts on; they are not a list of independently sampled physical orbitals.

The direct source-backed input route is native double factorization from Lesson 12, whose output has basis count $B_f=K$, copies $C_f=1$, and zero identity weights. General factorized containers with other dimensions can also feed this route when their data satisfies the contract, but there is no separately registered general nonlinear DFTHC fitting optimizer in the repository. Factorization can be truncated; its model error must still be accounted for. Abstract effective-Hamiltonian/downfolding interfaces from Lesson 11 do not supply a missing concrete preprocessing method here.

SOSSA’s normalization and amplitude tables

The registered hamiltonian_unitary_builder/sossa means Sum of Squares Spectral Amplification, as stated in the implementation. It requires a sum-of-squares container labelled blocked Jordan–Wigner. It validates the fixed one-body slot count and X/Y particle/hole relation, real Z/identity spin-free coefficients, their dimensions, and positive finite normalization.

There are $X_o=K+RC_f$ outer generator slots. In the actual code, a one-body coefficient row has absolute-sum $\sqrt{|v_r|}$, and the builder’s outer weight is $c_r=\sqrt{2|v_r|}$, including the two-spin factor. A spin-free outer weight is

The outer PREPARE amplitudes are $c_x/\sqrt{2\Lambda}$, where

This matches the factorized normalization convention of Lesson 12 for the retained data, not necessarily the ordinary Pauli coefficient norm $\lambda$. A docstring formula that omits the explicit two-spin factor must not override the implemented outer-weight calculation and its tests.

The inner table has shape [K + R*C_f, B_f + 1]. One-body slots use a delta at inner index zero. Spin-free rows contain sign(weight)*sqrt(abs(weight)) for the stored negative-Z and identity weights. Inner PREPARE squares/normalizes magnitudes; SELECT reads the sign separately. Zero rows receive a harmless fallback entry because their outer amplitude is zero, not because a new generator was inserted into the Hamiltonian.

One-body angles have shape [K,K-1]; the operator’s spin-free angles have shape [R*B_f,K-1]. The builder repacks SELECT angles to [R*(B_f+1),K-1] in basis-major/rank-minor address order, padding the identity basis with zero rotations. “Free-rider” bits record generator type and rank alongside an index. Their table is required when the layout reserves them. Structural dimensions affect actual lookup widths, not just printed summaries. The builder tests check weights, slots, sign relations, and missing-table failures.

The specialized circuit and its walk spectrum

The SOSSA circuit mapper returns a Hermitian, self-inverse block operation whose selected block is

For an energy $E$, its signal eigenvalue is $\mu=(E-E_s)/\Lambda-1$, in the interval [−1,1] for the valid ideal represented construction. An outer reflection completes the associated walk, with paired phases

The SOSSABlockEncodingContainer.eigenvalue_from_phase consequently uses

This is neither the ordinary LCU decoder nor a time-evolution decoder. It describes the phase of the completed walk, not an arbitrary eigenphase of the standalone block. Both paired branches give the same energy. The shifted energy window is $0\le E-E_s\le2\Lambda$.

The optional builder settings reference_ground_state_energy and reference_energy_gap both default to NaN, meaning unset, and are mutually exclusive. The first is a total model energy including core; the second is the distance $E_{\mathrm{gap}}=E_{\mathrm{gs}}-E_s$. This “gap” is not the excitation gap between ground and first excited states.

They supply an optional effective normalization

It reflects the local phase-to-energy sensitivity: $|dE/d\theta|=\Lambda|\sin\theta|$ at that reference energy. It is useful for algorithmic precision/resource planning, not an extra measured energy. The code requires the supplied reference gap strictly inside $(0,2\Lambda)$; endpoints, out-of-window inputs, and supplying both settings raise. Without a reference, block construction is still possible, but accessing lambda_eff raises. The phase decoder itself uses $\Lambda$ and $E_s$, not a fabricated default for the missing reference. A classically affordable estimate can be supplied with its uncertainty; exact prior knowledge of an intractable ground state is not presumed.

A small square-completion check

Take a one-spatial-orbital toy with one-body integral −0.3, Coulomb integral 0.8, zero core scalar, one normalized basis vector, weight $w=\sqrt{0.8}$, and identity weight zero. Normal ordering gives $h_1^{\prime}=0.1$. With $n=n_\alpha+n_\beta$,

Empty, singly occupied, and doubly occupied active states therefore have shifted energies 0.4, 0.1, and 0.6; adding the shift gives 0, −0.3, and 0.2, which agrees with $-0.3n+0.8n_\alpha n_\beta$. The normalization is $\Lambda=0.1+0.8/4=0.3$, so the signal eigenvalue of a singly occupied state is $0.1/0.3-1=-2/3$. Substituting its walk phase into the SOSSA decoder returns −0.3.

This is hand arithmetic demonstrating factors and shifts. It is not nitrogen, not a run of the factorizer, and not an execution of the SOSSA circuit. It shows why losing either the one-half in the square or the scalar shift would produce a scientifically different answer.

Where the generator cost is paid

The SOSSA circuit mapper defaults to outer alias sampling, inner conditional alias sampling, and QROM/phase-gradient SELECT, with coefficient and rotation precision both 10 bits. Inner direct and SELECT direct alternatives are available. The parent sets applicable child alias precision and external-gradient ownership; nested settings do not universally override parent decisions.

SELECT computes spin-selection flags, conditionally swaps spin blocks, rotates the selected orbital combination toward a designated mode, applies the simple Majorana-derived action, and uncomputes the rotation/spin selection. In the direct Q# path, a neighboring Givens step uses a CNOT sandwich around a neighbor-controlled $R_y(2\theta)$. It acts in the one-excitation subspace and leaves zero/double occupation unchanged. Rotating every orbital as an independent one-qubit gate would not have that number-preserving action.

The phase-gradient path loads angle words and implements the same neighboring action using arithmetic. Its Givens angle quantization uses $x=\operatorname{Round}(2^b\theta/(4\pi))$ modulo $2^b$, because its decomposition needs uncontrolled half-angle rotations; this differs from the probability-tree QROM loader’s angle convention in Lesson 16. Negative modular values are handled explicitly. The routine checks finite/range-compatible angles, and branch-specific measurement erasure requires the matching phase correction for what was actually loaded.

SelectSwap.qs trades selection size against swap-network scratch, and can use measurement-based erasure with phase fixups. It also chooses whether free-rider data should be loaded separately or carried in repeated inner lookups using its logical cost model. This is real scheduling/lookup logic, not evidence that every selected option minimizes complete hardware cost.

UnaryIteration.qs constructs one address indicator at a time using reversible AND recursion rather than allocating a permanent one-hot flag for every table entry. For non-power-of-two tables, unused address states can route to valid subtrees; the classical erasure mirror deliberately reproduces that routing. Padding and phase fixups are part of the coherent implementation, not irrelevant indexing details.

The circuit remains an uncontrolled, Adj-only, unit-power block. circuit_mapper/sossa rejects other powers. The current unary QPE builder owns the outer reflection and query schedule; ordinary iterative/standard controlled mappers do not accept SOSSA as a generic controlled walk. Full unary scheduling belongs to Lesson 21.

Its declared register includes the system, retained outer/inner reflection registers, two spin ancillas, and a shared phase-gradient suffix where needed. Additional inner lookup/free-rider scratch is allocated internally. The gradient must be initialized by the composing caller and excluded from zero-ancilla reflections. The standalone factory instead initializes its own gradient and resets outputs for cleanup. Neither structural container width nor callable argument width equals a physical-qubit estimate.

Independent full-block tests explicitly convert their interleaved classical matrix basis into the Q# blocked convention, including the fermionic permutation sign, not just reversing a bitstring. This validates the target operator across that stated basis change. It does not prove that an arbitrary trial state with a matching text encoding label is aligned automatically. Retain the orbital, mode-order, and phase conventions from Lessons 14–17.

Comparing the two routes fairly

Ordinary Pauli LCU needs the signed coefficient list, its norm $\lambda$, the index distribution, and a valid PREPARE/SELECT circuit. Factorized SOSSA needs $h_1^{\prime}$, ranks/bases/copies, signed generator weights, rotations, $\Lambda$, the scalar shift, and optional reference data for $\lambda_{\mathrm{eff}}$. A smaller factor count can reduce lookup structure without guaranteeing a smaller normalization or cheaper complete circuit. A smaller normalization can help phase resolution while still requiring expensive generators.

For an unexecuted ordinary route:

from qdk_chemistry.algorithms import create
from qdk_chemistry.data import AlgorithmRef

walk_plan = create(
    "hamiltonian_unitary_builder", "lcu", quantum_walk=True, power=1
).run(qubit_hamiltonian)
walk_circuit = create(
    "circuit_mapper", "prepare_select_prepare",
    prepare=AlgorithmRef("state_prep", "dense_pure_state"),
).run(walk_plan)

For the specialized route, assuming factorized_hamiltonian is already the intended real factorized active model:

from qdk_chemistry.data import MajoranaMapping

k = factorized_hamiltonian.get_one_body_integrals()[0].shape[0]
mapping = MajoranaMapping.jordan_wigner(2 * k)
sos_operator = create("qubit_mapper", "sum_of_squares").run(factorized_hamiltonian, mapping)
sos_plan = create("hamiltonian_unitary_builder", "sossa", power=1).run(sos_operator)
sos_block = create("circuit_mapper", "sossa").run(sos_plan)

The second result is a block, not a ready interchangeable controlled phase-estimation circuit. Neither snippet supplies a chemistry trial state or a complete workload. Optional QDK runtime/arithmetic and later resource-estimation/QEC models are external contributions; their internals were not reviewed or run here.

A fair comparison keeps the same chemical model, target sector, desired energy uncertainty, and state-preparation assumptions, then includes coefficient/factor preparation, all lookup and rotation precision, control/reflection requirements, repeated uses, and final readout. Bare Pauli LCU needs the ordinary core scalar added separately; SOSSA’s decoder already includes it through $E_s$. Do not compare differently shifted energies or differently truncated Hamiltonians and call the difference a quantum algorithm improvement.

We now have two ways to turn Hamiltonian information into coherent operations. Before deriving complete phase-estimation protocols, we next examine the simpler measurement task: estimating the expectation of an observable on a prepared trial state, including exactly what finite shots and term grouping do to the reported uncertainty.