Block encodings
A block encoding embeds a (generally non-unitary) operator as a sub-block
of a larger unitary. Concretely, an encoding provides a unitary U_A
acting on a system register plus one or more ancilla (signal) qubits such
that projecting the ancillas onto their zero state recovers the target
operator up to a scalar:
Here alpha is the subnormalization (the encoding normalization): the
flagged block implements H / alpha, so alpha must be at least the
spectral norm of H. Because the ancilla register flags the good block,
the same U_A drives every downstream algorithm — the qubitization walk
and QSVT (see Qubitization and QSVT) are generic over which encoding
produced it. Everything below is pure-Python CUDA-Q kernels requiring only
cudaq and numpy; qubit ordering, integral-tensor, and normalization
conventions are collected in Conventions and Reference.
Two encodings ship in the package, and they play different roles.
PauliLCU is the front door for a Hamiltonian given as a Pauli sum: it
reads the terms and builds the encoding with an exact multiplexed-rotation
PREPARE by default, or with the alias-sampled PREPARE and unary-iteration
SELECT under backend="alias". LCUBlockEncoding is the body-programmed
primitive underneath such constructions (the alias backend delegates to
it): it takes term weights and, per term, a SELECT body in the
unary-iteration gate vocabulary — controlled Paulis, but also the extended
gates that use work qubits — so its terms need not be Pauli words; it
realizes an alias-sampled PREPARE and a unary-iteration SELECT. Encodings
built from structured data (the double-factorized example below, the
sparse-access encodings) program it directly. Any object satisfying the
structural cudaq_algorithms.block_encoding.BlockEncoding protocol
plugs into the same consumers. Two combinators, SumEncoding and
RotatedEncoding, build new protocol-conforming encodings out of existing
ones (see Combining encodings), and the worked double-factorized
encoding demonstrates the protocol at full scale.
The block-encoding idea and PauliLCU
PauliLCU block-encodes a linear combination of unitaries (LCU): a
Hamiltonian written as a weighted sum of Pauli words H = sum_i c_i P_i.
The subnormalization is the LCU one-norm alpha = sum_i |c_i|.
Construction is flexible — a coefficient dict, a cudaq.SpinOperator, or a
list of (coeff, word) pairs:
from cudaq_algorithms import PauliLCU
# Flexible construction: dict, SpinOperator, or (coeff, word) pairs.
enc = PauliLCU({"ZI": 0.70, "IZ": -0.43, "XX": 0.19, "YZ": 0.11})
enc = PauliLCU(spin_op, num_qubits=2)
enc = PauliLCU([(0.7, "ZI"), (-0.43, "IZ")])
enc = PauliLCU(spin_op, num_qubits=2, backend="alias", mu=4) # see below
The encoding exposes its geometry and coefficients for inspection:
enc.num_system, enc.num_ancilla, enc.num_terms
enc.alpha # LCU 1-norm, sum_i |c_i|
enc.terms # [(coeff, word), ...]
enc.constant_term # sum of identity terms
kernel = enc.encode_kernel() # @cudaq.kernel(state): full U_A
PREPARE, SELECT, UNPREPARE
The LCU unitary factors into three stages on the ancilla superposition:
PREPARE loads the coefficient amplitudes onto the ancilla register, producing a superposition weighted by
sqrt(|c_i| / alpha).SELECT applies each Pauli word
P_ito the system, controlled on the corresponding ancilla basis state (with the sign ofc_ifolded in).UNPREPARE is PREPARE-dagger, un-computing the ancilla so the flagged
|0...0>block holdsH / alpha.
These stages are available as composable, module-level device kernels
(cudaq_algorithms.pauli_lcu.prepare, select, apply) that compose
inside user kernels, with enc.kernel_args supplying the flattened arrays
they take as arguments. They live in the module namespace rather than the
package root because their names are too generic to re-export.
The "alias" backend
PauliLCU(..., backend="alias", mu=...) builds the same encoding from the
alias-sampled PREPARE and unary-iteration SELECT primitives by delegating to
LCUBlockEncoding (next section), with each Pauli word as a SELECT body.
The rotations of the exact PREPARE become Toffoli-style gates, at the cost
of extra ancillas — 3 m + 2 mu + 3 qubits for m index bits, so 20
rather than 3 for a five-term Hamiltonian at mu = 4 — and of rounding
each term weight to mu bits (alpha stays the exact one-norm). The
API is otherwise the same: every kernel factory, Walk, QSVT and
select_observable work unchanged, and kernel_args (the exact backend’s
flattened arrays) is the one member that raises.
The Block-encoding examples walkthrough compares exact and alias PREPARE/SELECT for the same two-qubit Hamiltonian:
The comparison shows the accuracy and resource cost of choosing a
coefficient-loading strategy while retaining the same action, Walk, and
QSVT interfaces. Exact preparation encodes the intended weights; alias
sampling rounds them to a finite table. Its represented Hamiltonian
H_mu therefore depends on the precision mu.
The default output leads with the absolute operator error
||H_mu-H||_2 and the demonstrations actually executed:
backend mu Hamiltonian error Executed demonstrations
exact - 0.00000 Action, Walk, QSVT
alias 2 0.04516 Action, Walk, QSVT
alias 3 0.04516 Action, Walk, QSVT
alias 4 0.01734 Action only
On this Hamiltonian, mu=3 gives the same rounded weights as mu=2;
mu=4 reduces the error by about 2.6 times, using more ancillas.
The general operator-error bound 1.5 alpha / 2^mu halves per extra bit,
while the realized error can plateau. These errors are absolute operator
norms, not percentages.
The following resource table shows the other side of this tradeoff: system and ancilla counts plus rotations, uncontrolled single-qubit gates, singly/doubly/higher-controlled Paulis, and Fredkins. Alias ancillas include preparation garbage and SELECT work; the good projector covers the entire register. Counts describe one encoding without input-state preparation and do not claim a synthesized T cost.
The example independently enumerates the alias tables to build H_mu.
It checks the executed action, Walk, and QSVT circuits against classical
references for that represented operator with tolerance 1e-10.
This circuit-agreement check is separate from the coefficient-rounding
error above: implementing H_mu accurately does not remove its distance
from H. Successful checks are summarized in one sentence; add
--verbose to print each numerical discrepancy, rounding bound, and
gate-accounting check. All checks remain active in either mode and print
diagnostics before raising on failure.
The Walk and QSVT circuits execute for exact preparation and alias
mu=2 and mu=3. At mu=4 the 19-qubit encoding executes its action
once and reports resources; its Walk/QSVT runs are skipped to keep CPU
runtime manageable. A separate one-qubit fixture, H = 0.6 Z - 0.4 X,
prints exact and alias-mu=2 measured moments T_0 through T_3, checking each
column against its represented Hamiltonian. Measured moments use
+H_mu/alpha; walk good blocks use T_k(-H_mu/alpha).
LCUBlockEncoding: alias-sampled PREPARE, unary-iteration SELECT
LCUBlockEncoding builds the same PREPARE-dagger . SELECT . PREPARE
structure from the circuit primitives in cudaq_algorithms.primitives:
PREPARE is coherent alias sampling over the term weights and SELECT is a
unary-iteration walk over the term index. It takes the Hamiltonian as term
data rather than Pauli strings — the weights |c_k| and, per term, a
SELECT body describing the Hermitian involution U_k in the
unary-iteration gate vocabulary — so the term unitaries need not be Pauli
words:
from cudaq_algorithms import LCUBlockEncoding
# H = 0.6 Z0 - 0.4 Y1 + 0.5 X0 X1: the weights |c_k| and one SELECT body
# per term; a negative coefficient is a ("sign",) op on its branch.
enc = LCUBlockEncoding(
num_system=2,
weights=[0.6, 0.4, 0.5],
bodies=[[("z", 0)], [("y", 1), ("sign",)], [("x", 0), ("x", 1)]],
mu=4)
enc.alpha # sum_k |c_k|
enc.num_ancilla # index + alias garbage + SELECT work
enc.discretized_weights # the weights the alias tables realize
enc.discretization_bound # per-bin rounding bound, set by mu
kernel = enc.encode_kernel() # @cudaq.kernel(state): full U_A
Every body op is validated at construction (known op, operand count,
system targets within num_system, and a Hermitian product for
Pauli-word bodies) with a ValueError naming the term and op. The alias
tables hold the weights to mu bits, so the encoded operator is H
with each weight |c_k| realized within alpha * discretization_bound
while alpha stays the exact one-norm. The ancilla register is
index(m) + garbage(2m + 2mu + 2) + work qubits with
m = max(1, ceil(log2(num_terms))), so mu drives the width: a
five-term, two-qubit Hamiltonian is 22 qubits in total at mu = 4 and
30 at the default mu = 8, sized for resource estimation rather than
for the CI simulators. The walk and QSVT consumers work unchanged. The
walk runs in the PREPARE frame like PauliLCU’s, so Walk.moment serves
odd orders through the derived select_observable whenever every body is
a Pauli word (a body in the extended vocabulary raises
NotImplementedError there); even orders use the geometry-only
reflection observable, whose 2^num_ancilla terms are practical only
at small mu.
The BlockEncoding protocol
Walk and QSVT are generic over the encoding: they receive an encoding
object and delegate every encoding-specific circuit to it, keeping only
sequencing, control conventions, and measurement for themselves. Any object
satisfying the cudaq_algorithms.block_encoding.BlockEncoding
protocol works — conformance is structural (typing.Protocol,
runtime-checkable), so implementations do not inherit from anything.
The contract that makes the composition work is data erasure at the kernel
boundary: every factory returns a @cudaq.kernel whose signature is fixed
by the protocol (registers only), with all encoding-specific data already
captured inside the kernel at factory time. The consumers can then call the
injected kernels without knowing anything about the encoding’s internals.
An implementation exposes three properties and a family of kernel factories:
num_system— number of system qubits the encoded operator acts on.num_ancilla— number of ancilla (signal) qubits flagging the encoded block. Consumers requirenum_ancilla >= 1: the walk’s-H/alphasign comes from a reflection about the ancilla zero state, which is a no-op on an empty register.PauliLCUnormalizes single-term inputs to one idle ancilla to satisfy this uniformly.alpha— the block-encoding normalization; the encoded block isH / alpha.
Kernel factories (the returned kernels’ signatures are fixed; all encoding data is captured inside at factory time):
prepare_kernel—(ancilla: qview): PREPARE the ancilla superposition.unprepare_kernel—(ancilla: qview): PREPARE-dagger.apply_kernel—(ancilla: qview, system: qview): the full block encodingU_A.controlled_apply_kernel—(control_and_ancilla: qview, system: qview):U_Acontrolled by qubit 0 of the combined register.walk_step_kernel—(ancilla: qview, system: qview): one qubitization walk stepW(block-encodes-H/alpha).adjoint_walk_step_kernel—(ancilla: qview, system: qview): one adjoint walk stepW dagger.controlled_walk_step_kernel/controlled_adjoint_walk_step_kernel— the controlled variants, each taking a combined[control, ancilla...]register.
There is also one observable hook:
select_observable— the odd-moment observable as acudaq.SpinOperator. Measured after PREPARE andpwalk steps (no UNPREPARE), its expectation is the odd Chebyshev moment<T_{2p+1}(H/alpha)>. The construction is encoding-specific (for an LCU it issum_i sign_i |i><i|_anc x P_i); the even-moment reflection observable2|0..0><0..0| - Ineeds only the register geometry, soWalkderives it without an encoding hook.
Register conventions shared by all implementations:
encode_kernel-produced kernels allocate the system register from acudaq.Statefirst, ancillas after it (so the good subspace is the first2**num_systemamplitudes; seesim_utils.good_subspace).Controlled variants take a combined
[control, ancilla...]register whose qubit 0 is the external control (a CUDA-Q Python control set cannot mix a bare qubit with a separate register); with control|0>they must reduce to the identity.The flagged block of the walk step is
-H/alpha(the sign folded into the walk construction);Walk.momentand the QSVT response conventions rely on this.
Implementing the protocol
Because conformance is structural, a block-diagonal or any other custom
encoding plugs into Walk and QSVT simply by implementing the surface
above — no base class, no registration. The worked example
06_bring_your_own_encoding.py (Getting-started walkthrough)
implements a minimal BlockEncoding from scratch and runs it through the
shared consumers, validating it against a dense reference.
Sparse-access encodings
cudaq_algorithms.sparse block-encodes a real sparse symmetric matrix
given as data (a dense array, a scipy.sparse matrix, or integer-indexed
(rows, cols, vals) triples) or as structure oracles.
SparseOracleEncoding is the sparse-access construction of Camps, Lin,
Van Beeumen and Yang (arXiv:2203.10236):
U_A = T† S T from a location oracle (the column structure) and a
value oracle (fixed-point matrix-element angles), bundled as
OracleKernels. alpha = d_padded * h pays the largest element h at
the padded slot count, so it is at its best on uniform structured matrices
with few nonzeros per row. banded_oracles builds the bundle for
constant-valued bands, qrom_oracles for arbitrary entries; the value
oracle writes quantized_angle fixed-point angles with value_bits of
precision. Negative off-diagonal entries are fine; a negative diagonal is
not representable directly (shift the diagonal, or encode the Hermitian
dilation).
from cudaq_algorithms import encode_sparse, Walk
enc = encode_sparse(matrix, value_bits=6) # qrom_oracles + SparseOracleEncoding
enc.report["alpha"], enc.report["slots"], enc.report["qubits"]
enc = encode_sparse(a, dilate=True) # [[0, A], [A^T, 0]] of a general A
walk = Walk(enc) # same consumers as PauliLCU
encode_sparse validates the data, prices the construction classically
and attaches the figures as encoding.report (alpha, qubits,
nnz, max_row_nnz, slots, dim, dilated,
value_bits). It encodes a symmetric matrix with a non-negative
diagonal: anything else raises unless dilate=True asks for the
Hermitian dilation [[0, A], [A^T, 0]] on one extra system qubit (the
halves bit is the most significant), as
SparseOracleEncoding.from_general_oracles does for oracles.
What the oracle contract requires. An OracleKernels bundle supplies
o_loc / o_val and their explicit inverses, the slot count d,
the value bound h, value_bits, the work-qubit count and the
reverse-slot involution; every inverse must hold on states whose work
register enters |0> (flat, work-free oracles such as banded_oracles
invert globally, table oracles built on unary-iteration walks only with
clean scratch). The bundle records the system width it was built for and
the encoding rejects a mismatch.
Register widths and moments. num_ancilla counts every ancilla,
scratch included; SparseOracleEncoding exposes num_block_ancilla and
num_scratch. The encoding provides no select_observable, so
Walk.moment serves even orders only, and at these widths the even-order
reflection observable would expand to 2^num_ancilla Pauli terms:
Walk refuses above 20 ancillas. Take Chebyshev data from walk_kernel
powers on a statevector simulator.
Matrix data versus arithmetic access
The Block-encoding examples sparse tutorial executes a 2x2
SPD matrix through both encode_sparse and arithmetic banded_oracles.
For the same matrix, table matching needs two slots (alpha=3), while three
bands pad to four (alpha=6). Slots encode reversible structure and need
not equal the maximum row nnz. Compare each block with its own normalization,
rather than expecting equal raw blocks.
The report’s qubit total includes the system, block ancillas, and deterministic value/sign/work scratch. A separate four-point arithmetic case checks that boundaries are clipped, including both zero corner entries. The NumPy and integer-triple constructor forms are also shown through metadata; the nonsymmetric dilation demonstration is metadata only.
Finite angle tables encode a represented matrix, not the exact input. For value bound h and b bits, independently compute
Rounding is nearest-even and the top code is clamped. Preserve structural zeros and coefficient signs; the largest entry also has finite precision error. An entry error is at most \(h\pi/(2\,2^b)\); summing row errors gives a conservative spectral bound for these symmetric fixtures. The tutorial checks the block against the represented matrix at fp64 precision, then reports its discrepancy from the requested matrix separately.
The same objects drive Walk and QSVT. Short walk blocks use
\(T_k(-\widetilde A/\alpha)\); an independent two-dimensional signal
model checks a complex QSVT response. These are statevector checks, not
measured moments.
A sparse inverse
Example 07 on Getting-started walkthrough solves a dense
five-dimensional system through PauliLCU and a power-of-two sparse SPD
system through encode_sparse, the latter with its own three-bit
quantization and freshly generated phases. Its CKS degree depends on the
represented minimum eigenvalue divided by alpha; phases from another
encoding cannot simply be reused.
For normalized input b/beta and target polynomial c/x, physical recovery is beta/(c*alpha). Odd parity of the negative-H walk and the QSP global phase are verified independently, without fitting a scalar to the NumPy solution. The example distinguishes coefficient, polynomial, phase-synthesis, and circuit error budgets, and checks a full vector and residual.
Full-state access and real-response extraction are simulator postprocessing. The raw good-block norm includes a complementary complex response and is not the success probability of an isolated inverse filter. The factory’s zero padding creates zero eigenvalues for non-power-of-two data; the reciprocal fixtures are power-of-two sized, and the dense case pads with an identity block instead.
Sparse inverse application: heat diffusion
Example 10 on Getting-started walkthrough advances a localized temperature profile by one implicit step in a rod with zero-temperature endpoints. Backward Euler and centered differences give \(A T^{n+1}=T^n\), with \(A=\operatorname{tridiag}(-r,1+2r,-r)\) and \(r=D\Delta t/\Delta x^2\). The fixed endpoints are eliminated, leaving a symmetric positive-definite interior problem with clipped boundaries. See the finite-difference derivation.
The default uses two interior points, r=0.25, and initial temperatures
[0,1]; --points 4 is the four-point rod with initial temperatures
[0,1,0,0]. banded_oracles supplies location shifts and boundary-masked
value loads; three bands pad to four slots. With h=1.5, alpha=6 and the
default four angle bits, the circuit has one system qubit, five block
ancillas and eight deterministic scratch qubits: 14 in total. Each doubling
of the points adds one system qubit and one block ancilla, and each extra
angle bit adds one scratch qubit, so four points use 16. Both projection and
reflection include the complete ancilla register.
An independent arcsine/nearest-even/clamp/sine-squared calculation builds the represented matrix before any circuit runs. The finite angle code rounds even the maximal diagonal. From four points on, the wrap-around corner entries are structural zeros, and the example checks that they remain zero. NumPy solves the ideal and represented systems separately. Column-by-column circuit checks verify the represented block, not a fitted reference.
The scaled odd CKS polynomial
uses \(x_{\min}=\lambda_{\min}(\widetilde A)/\alpha\).
Global boundedness follows from
\(|f_B(x)|\le\min(B|x|,1/|x|)\le\sqrt B\).
The default relative target 1e-2 needs B=104 and a full CKS degree of 207,
despite the small physical condition number: x_min carries the factor
1/alpha = 1/(4h) of the padded sparse normalization. Stable binomial
tails form coefficients. For practical CPU execution the example discards a
Chebyshev tail whose sum of absolute coefficients is below 1e-10, reducing
the executed degree to 89. Since every Chebyshev basis function has
magnitude at most one on [-1,1], this is a uniform error bound. The example
checks that the combined inverse bound still meets the requested target and
propagates the discarded tail into the physical error budget. Matrix
precision and the inverse target are unchanged. --full-cks executes all
207 degrees. Four points (--points 4) need B=130 (degree 259, executed
99) on 16 qubits, and the precision configuration --points 4
--value-bits 6 --inverse-epsilon 1e-3 needs B=206 (degree 411, executed
125) on 18 qubits. Degree and qubit guards reject excessive requests before
large allocation or phase generation.
QSPPACK synthesizes phases. An independent 2x2 signal model checks the raw complex QSVT response and the analytical odd-parity/global-phase correction. For beta=norm(T_initial), the physical recovery factor is beta/(c*alpha); it is fixed analytically from the input norm, the polynomial scale and the encoding normalization, not fitted to the circuit output, and the full-vector comparison with the quantized NumPy solve checks it.
The error budget separates matrix coefficient discretization, CKS approximation, the bounded Chebyshev tail, phase synthesis on the actual spectrum, and fp64 circuit roundoff. The per-node table and full-vector residual compare with the same discrete NumPy problem. They do not establish continuum PDE accuracy, which also depends on spatial and temporal discretization.
Full-state access and real-response extraction are simulator postprocessing.
The raw good-block norm includes a complementary imaginary response and is
not an isolated inverse-filter success probability. The example supports
--points, --r, --value-bits, --inverse-epsilon, and lazy headless
--plot; its default requires QSPPACK, and only plotting requires Matplotlib.
Bring your own encoding: the double-factorized example
The protocol’s worked, full-scale demonstration is a double-factorized
encoding of the electronic-structure Hamiltonian (von Burg et al., Phys.
Rev. Research 3, 033055 (2021);
arXiv:2007.14460), implemented
entirely against the public API as a runnable example — df_encoding.py
on the block-encodings examples page. Its dense-reference test
suite (tests/python/test_df_encoding.py) runs in CI, so the example is
held to library-grade correctness, and Walk/QSVT consume it unchanged:
import sys
sys.path.insert(0, "docs/sphinx/examples/python") # or copy the file
from df_encoding import DoubleFactorizedEncoding # the example module
from cudaq_algorithms import Walk, QSVT
from cudaq_algorithms import double_factorization as df
factorization = df.compressed_double_factorization(eri, num_leaves=T)
encoding = DoubleFactorizedEncoding(one_body, factorization,
scalar_offset=nuclear_repulsion)
walk = Walk(encoding) # same consumers as PauliLCU
kernel = QSVT(encoding).kernel(sequence)
Use the example file as the template for writing your own encoding; the
construction, its normalization, and a six-molecule benchmark against
PauliLCU are documented with the example itself (see
Block-encoding examples).
QROM-programmed real spatial frames
The same example also accepts rotation_backend="qrom", angle_bits=4;
"fixed" is the class default. The molecular driver defaults to
--rotation-backend both --angle-bits 4. The exact coefficient PREPARE
and retained Z/ZZ terms are identical across backends, so alpha is unchanged.
A frame on n spatial orbitals uses K=n(n-1)/2 real adjacent mixing slots.
Every slot is retained, including zero angles. QR elimination leaves a
sign diagonal D; the forward network realizes F=V D. These signs commute
with every diagonal Z word and cancel in conjugation. This cancellation
is specific to the present encoding; arbitrary basis changes and state
preparation need their phases. Each public spatial_givens_rotation
acts on both interleaved spin sectors, including Jordan-Wigner parity
through the intervening spectator qubit. Its real orbital block is
[[cos(theta), sin(theta)], [-sin(theta), cos(theta)]].
Unsigned little-endian words encode full turns with nearest-even rounding:
code=round(theta*2**b/(2*pi)) mod 2**b. Bit k controls a spatial
rotation of angle 2*pi*2**(k-b). A shared rounded frame F_b remains
orthogonal. Independently rounding separate columns would not ensure
this and could spoil Hermiticity of products of orbital reflections.
The ancilla layout is [term index | K*b angle bits | QROM ladder].
Term PREPARE/SELECT treat index qubit zero as the most significant
logical bit, while QROM addresses are little-endian; table rows are
therefore populated at bit-reversed term addresses. Identity and padded
rows load zero programs. For n=1 there are no mixing slots and no QROM
or program workspace is allocated.
SELECT runs lookup, programmable adjoint, index-controlled signed Z word, programmable forward, and adjoint lookup. Words and ladder return to zero at its boundaries; index and system can stay entangled. External controls act only on the middle word/sign, allowing the sandwiches to cancel on the inactive branch, including relative phase. PREPARE touches the index slice only. Walk reflections and QSVT good-projector phases cover the complete ancilla, including words and ladder.
rotation_report returns detached metadata: backend, width, mixing
slots, index/program/ladder widths, actual table size, packed rows, and
separate PREPARE, lookup, and programmable-rotation counts.
ideal_frame_matrices and represented_frame_matrices return copies
of F and F_b ordered by frame index. The fixed backend allocates no
program/lookup workspace; num_ancilla includes all required workspace
for either backend. These counts do not include an external enable or
fault-tolerant rotation synthesis.
The H2 driver builds independent NumPy Fock matrices using occupied-set
determinant minors of kron(F, eye(2)). It distinguishes the integral
Hamiltonian H_input, reconstructed-tensor H_DF, retained fixed terms
H_kept, and rounded-frame H_b. Tight circuit checks target H_b/alpha;
angle error H_b-H_kept is reported separately from factorization and
threshold error. For circular angle differences d, a two-spin frame has
bound delta_f=min(2,2*sum(abs(d))); summing
abs(c_j)*min(2,2*delta_f) bounds the operator error of retained terms.
The driver checks this bound and compares short Walk/QSVT actions with
independent scalar/matrix responses. Ground energies are classical NumPy
diagonalizations with the core offset added, not measured energies.
The four/six/eight-bit precision sweep is host-only; only the requested width executes circuits. Larger QROM molecular programs print complete qubit estimates and are explicitly resource-only. Fixed-backend moments are retained; QROM measured moments are omitted because the reflection observable grows exponentially with workspace.
This mechanism is motivated by von Burg et al., Phys. Rev. Research 3, 033055 (2021), arXiv:2007.14460, supplementary VII B.1 and VII C, and Lee et al., PRX Quantum 2, 030305 (2021), arXiv:2011.03494, Appendix C.2, Figure 16. The example retains flat term preparation and diagonal Z/ZZ expansion. It does not reproduce the papers’ nested DF preparation, degree-two Chebyshev construction, optimized normalization, phase-gradient synthesis, or optimized inverse-QROM costs. Its resource counts should not be substituted into those algorithms’ cost formulas.
Combining encodings
Two combinators in cudaq_algorithms.combinators take
BlockEncoding objects and return BlockEncoding objects, so Walk and
QSVT consume the result unchanged and the constructions nest:
SumEncoding([(c_1, enc_1), ..., (c_K, enc_K)])block-encodessum_i c_i H_ifrom encodings of theH_iwith real, nonzero coefficients (K >= 1; a single term is “scale by a constant”).RotatedEncoding(inner, enter, exit)block-encodesV H V^daggerfrom an encoding ofHand two(system: qview)kernels implementingV^dagger(enter) andV(exit).
from cudaq_algorithms import PauliLCU, RotatedEncoding, SumEncoding, Walk
hopping = RotatedEncoding.from_orbital_rotation(
PauliLCU(momentum_diagonal_words), modes) # T, diagonal in momentum space
interaction = PauliLCU(interaction_words) # U, diagonal in real space
combined = SumEncoding([(1.0, hopping), (1.0, interaction)])
combined.alpha # == hopping.alpha + interaction.alpha
walk = Walk(combined) # same consumers as PauliLCU
shifted = SumEncoding([(1.0, combined), (-e_ref, PauliLCU({"I" * n: 1.0}))])
Normalization. The sum’s subnormalization is the LCU triangle bound,
alpha = sum_i |c_i| alpha_i; a rotation leaves alpha unchanged. The
combinator itself therefore never lowers alpha — the saving comes from
choosing where each piece is encoded. A hopping term encoded in momentum
space costs sum_k |eps(k)|, less than the one-norm of its Jordan-Wigner
XX + YY strings, so the sum of a rotated momentum-space T and a
real-space U has a smaller alpha than one flat PauliLCU of the
whole Hamiltonian. (The identity part of U counts in both numbers.)
Ancilla layout. SumEncoding adds a slot register of
max(1, ceil(log2 K)) qubits selecting the summand and one flag qubit,
and the summands share one ancilla pool as wide as the widest of them:
num_ancilla = num_slots + 1 + max_i num_ancilla_i, in the order
[slot][flag][shared pool]. PREPARE puts amplitude
sqrt(|c_i| alpha_i / alpha) on slot |i>. For each summand, SELECT
uses the flag to control the signed operand on the contiguous
[flag | pool] view: toggle flag ^= (slot == i), apply the signed
operand, restore the flag, then repeat the signed operand. The two calls
cancel on inactive slots and apply the signed operand once on the selected
slot, regardless of the incoming flag state, because each operand is an
involution. The flag is restored even when it is entangled with the pool
or system. Pool sharing is sound because SELECT is block-diagonal over the
slot register, each block a unitary on the whole pool, and the encoded block is the
all-zero subspace of the entire [slot][flag][pool] register, which the
walk’s reflection covers; a summand’s ancillas need not return to |0>
(an alias-sampled summand’s garbage does not). RotatedEncoding adds no
ancillas.
Costs. Each slot PREPARE or unprepare uses 2^num_slots - 1 rotations;
a full block-encoding application uses both. SELECT adds two
num_slots-controlled flag flips and two calls to each summand’s
controlled_apply_kernel, including its PREPARE and unprepare costs. A
negative coefficient also adds two flag Z gates. For controlled SELECT,
the flag flips have one additional external control. The two operand calls
are needed even when the incoming flag happens to be zero, and the same
factor applies at each level of nested sums: a leaf below d sum levels
is called 2^d times per path. An orbital-rotation
network applies num_rotations adjacent Givens rotations per spin sector
on entry and again on exit. The alpha saving is bought with these gates
and the extra num_slots + 1 ancillas. The win is alpha and the
multi-controlled gate count, not the total gate count: on the 2x2 Hubbard
example, one combined apply_kernel is about 1270 gates (388 CNOTs plus
192 rx and 96 rz from the Givens network, run twice by the SELECT
echo) against about 520 for the flat PauliLCU of the same Hamiltonian,
of which 160 are multi-controlled, while alpha drops from 24 to 20 —
an advantage that grows with the lattice (1.20x at 2x2, 1.31x at 2x3,
1.39x at 3x3, 1.45x at 4x4).
Negative coefficients. A term with c_i < 0 is phased by -1 on
its slot branch, so SumEncoding([(1.0, encoding), (-e_ref, identity)])
with identity = PauliLCU({"I" * n: 1.0}) block-encodes
H - e_ref I at alpha + |e_ref| — the spectral shift ground-state
filters and QPE decoders need.
Nesting. Operands may themselves be sums or rotations: a
SumEncoding of a RotatedEncoding of a PauliLCU is one
BlockEncoding, and the walk’s reflection acts on the outermost ancilla
register as a whole.
Requirement on operands. Every operand’s apply_kernel must be
Hermitian, hence an involution (U_A^2 = I), on its entire ancilla and
system register. Its controlled_apply_kernel must implement exact
controlled-U_A for arbitrary incoming ancilla states. These are the
protocol’s requirements, which every encoding in this package satisfies;
matching its API members alone does not establish them. Verify both
properties for a foreign encoding before summing it, since the signed
operand cancellation and the walk and QSVT constructions rely on them.
The orbital-rotation constructor. RotatedEncoding.from_orbital_rotation(inner, orthogonal)
takes a real orthogonal n x n matrix whose columns are the target
modes, with 2 n == inner.num_system in the interleaved spin-orbital
layout (2p up, 2p + 1 down), and compiles it with the
cudaq_algorithms.stateprep orbital-rotation schedule to a network of
adjacent Givens rotations applied to both spin sectors (see
State preparation). The Givens sweep alone realizes V up to a sign per
mode (mode_signs reports those signs); the constructor cancels them
with a Z on both spin orbitals of each such mode, so the frame kernels
realize V exactly and any inner encoding is valid — hopping terms
included. For a rotation that is not a real orthogonal matrix on the
interleaved layout, supply your own enter/exit kernels.
Not available: the odd-moment observable. Both combinators raise
NotImplementedError from select_observable. The sum’s SELECT drives
each summand’s full block encoding — PREPARE trees included — so it has no
compact cudaq.SpinOperator form; a rotated encoding’s terms are not
computational-frame Pauli words. Even moments (Walk.moment with even
order), Walk.kernel statevectors at any power, and QSVT sequences are all
available; Walk.moments, which alternates even and odd orders, is not.
For an odd order on a statevector simulator, take the good-subspace block
of Walk(encoding).kernel(power=k), which applies T_k(-H/alpha).
The worked example 09_hubbard_combined_encoding.py
(Getting-started walkthrough) builds the Fermi-Hubbard
Hamiltonian this way — T in the analytic momentum basis, U in real
space — and verifies every block, the controlled variants, the walk
moments, a negative-coefficient shift, and a QSVT sequence against an
independent sparse Jordan-Wigner reference.