PREPARE–SELECT Decomposition

English · 简体中文

Category C5/C1 · Module oracq.algorithms.common.prepare_select · Stage V4

Overview

The standard block-encoding assembly of the LCU decomposition \(H = \sum_i c_i P_i\) (Low & Chuang 2019; Babbush et al. 2018, cited in the module docstring; BE / HAM in the input-model vocabulary):

\[ \mathrm{BE} = (\mathrm{PREPARE}^\dagger \otimes I)\cdot \mathrm{SELECT}\cdot(\mathrm{PREPARE} \otimes I), \qquad \alpha = \sum_i |c_i| . \]

PREPARE prepares, on the selector register, a state with amplitudes \(\propto \sqrt{|c_i|}\); SELECT applies the \(i\)-th Pauli word to target according to the selector value. The coefficient phases go into SELECT by repository convention (applied via global_phase), and PREPARE encodes only the magnitudes. This page covers the general decomposition and the gate / QRAM / abstract three layers of PREPARE; the alias-sampling route has its own page (see Alias sampling preparation).

Interface and input model

abstract_prepare(coefficients, *, work_width=0, name=None)
gate_prepare(coefficients, *, name=None)
qram_prepare(coefficients, *, angle_width=8)
select_pauli(terms)
lcu_prepare_select(terms, *, prepare=None)

API entry points: abstract_prepare, gate_prepare, qram_prepare, select_pauli

• coefficients: at least two finite complex coefficients, not all zero (for a single term use scale directly).

• abstract_prepare: an open declaration whose coefficients are written into declaration attributes; work_width must match the work width of the later bound implementation (0 for gate, selector width plus angle width for QRAM).

• qram_prepare: returns QramPreparation(preparation, memory), with the angle table memory = {"angles": ...} bound as QRAM data by the caller (angle_width 2..32).

• terms of select_pauli / lcu_prepare_select: a sequence of (coefficient, Pauli word) pairs or a PauliHamiltonian; words allow only IXYZ, all terms are of equal width, and SELECT requires at least two terms.

• lcu_prepare_select: prepare defaults to gate_prepare and may also be given an abstract / QRAM / alias handle (adapted via as_state_preparation); a single term degenerates to scale(c, pauli_word).

Attributes of the returned objects:

Object	Attributes
PREPARE variants (StatePreparation)	width = selector width; module attributes prepare_terms / prepare_alpha / selector_width
select_pauli (Operation)	registers selector / target; attributes algorithm="select_pauli", select_terms, selector_width
lcu_prepare_select (BlockEncoding)	be_alpha = α; attributes be_form="prepare_select", lcu_terms, selector_width, prepare_work

Implementation notes

The gate variant directly reuses the multiplexed Ry rotation tree of gate_state_prep (amplitudes \(\sqrt{|c_i|/\alpha}\) zero-padded to \(2^{\text{selector}}\)); the QRAM variant reuses the qram_state_prep rotation tree, with the angle table generated by qram_state_angles. Signal register layout of the block encoding: the low selector_width bits are the selector and the high bits are PREPARE’s work (in the alias variant, the purification junk); PREPARE must satisfy the zero_input contract and its target width must equal the selector width, otherwise it is rejected at generation time.

SELECT’s control conditions are expressed with the RIR Control primitive on the binary selector value; when unary iteration is needed, the backend lowers the multi-bit controls for implementation, and the generation stage does not expand them. The product can be handed directly to transforms.qubitization_walk. Applicability boundary: the gate PREPARE gate count grows exponentially with the number of terms; the QRAM variant carries angle-table quantization error (distribution cross-check tolerance 0.02).

Validation approach

Category C5/C1: the PREPARE / SELECT oracles belong to the data-access layer (C5), while the (0,0) block of the block-encoding assembly is cross-checked point by point against the dense matrix under C1 (acceptance criteria in ../development/validation-plan.md §2). Three layers of evidence live in tests/core/test_prepare_select.py:PrepareSelectTests (4-term test Hamiltonian TERMS, α = 2.2):

• Structure: the declaration and slot assertions of test_gate_and_qram_prepare_bindings_agree; test_pauli_hamiltonian_input_and_single_term_shortcut (PauliHamiltonian input, single-term scale shortcut); test_bad_inputs_fail_at_generation (single term / all-zero / non-finite coefficients, SELECT violations of term count, word width, and letters, PREPARE width mismatch, and other generation-time rejections).

• Numerical: test_select_applies_indexed_pauli_word_with_phase — SELECT is cross-checked element by element for every selector value against the dense Pauli matrix × coefficient phase (places = 11); test_block_encoding_recovers_hamiltonian_over_alpha — the (0,0) block of the BE is multiplied by α and cross-checked against the dense Hamiltonian (places = 10, via witness.assert_block_equals); test_qram_prepare_block_encoding_approaches_hamiltonian (QRAM PREPARE variant, delta = 0.02); test_qubitization_walk_composition (directly connected to qubitization_walk, signal = 0 block = H/α, places = 10).

• Binding: test_gate_and_qram_prepare_bindings_agree — the gate variant’s selector amplitudes are cross-checked against \(\sqrt{|c|/\alpha}\) (places = 11); after the abstract slot is bound to the gate implementation via bind the distribution is exactly unchanged, and after the QRAM binding attaches the angle table via Binding the amplitudes are cross-checked (delta = 0.02); the abstract → gate binding inside the block encoding is covered by test_abstract_prepare_binds_inside_block_encoding (block unchanged after binding, places = 10).

Known gaps and planned stages

The module-level gaps concentrate on the alias route (see Alias sampling preparation); beyond that, the unified three-binding consistency parameterization (cross-checking the same declaration binding by binding, rolled out across oracles / prepare_select / graph_walks / data_loading) waits for V4; gate / QRAM / abstract currently each have independent witnesses. Consistent with the prepare_select.py row of validation-coverage.md.

Related links

• Source: src/oracq/algorithms/common/prepare_select.py

• Same-group pages: Alias sampling preparation, State preparation oracle, XOR database

• API reference: PREPARE-SELECT decomposition

• Concepts: Oracles and operator representations

• Validation matrix: Validation coverage matrix

Numerical validation

Paper-grade numerical validation script: tests/verification/verify_blockencoding.py (real-backend execution, no mock substitutes, no skips; all 73 cases passed on 2026-09-16), artifact out/verification/blockencoding.json. This page corresponds to gate-prepare-*, select-pauli-*, lcu-prepare-select-*, qram-prepare-*, alias-prepare-*, and abstract-prepare-*, 12 cases in total.

Experiment design:

1. the gate PREPARE selector amplitudes are cross-checked point by point against \(\sqrt{|c_i|/\alpha}\) (two groups: 4 terms and 5 terms zero-padded; the padded slots must have zero amplitude), crossed over the reference / rir-pysparq / adapter-pysparq three paths;

2. select_pauli reads out the final state for every selector value and cross-checks element by element against the dense matrix of \(e^{i\varphi_i}P_i\);

3. the (0,0) block of lcu_prepare_select is multiplied by α and cross-checked against the independently numpy-assembled \(\sum_i c_i P_i\): w1 with two terms, w2 with real/complex coefficients, w3 with six terms across scales; w1/w2 additionally go through OriginIR-ext + UniQC to_matrix full-unitary extraction;

4. angle-table quantization of QRAM PREPARE: TVD convergence for angle_width 8→12 (reference and rir agree amplitude by amplitude);

5. alias-sampling PREPARE: the TVD of the target marginal distribution is compared against the analytic bound \(2^{\text{selector}}\cdot 2^{-\text{precision}}\), and the block error of the alias-variant PREPARE–SELECT block encoding is controlled by the same bound;

6. after the open declaration abstract_prepare is bound to the gate implementation inside the block encoding via bind, the block agrees amplitude by amplitude with the direct assembly.

Case	Scale	Paths	Metric	Value
gate-prepare-distribution-terms4	4 terms, selector 2	three paths	max amplitude error	0
gate-prepare-distribution-terms5-padded	5 terms (3 zero-padded slots)	three paths	max amplitude error	1.1e-16
select-pauli-indexed-words	4 terms (including complex phase 0.2j)	reference	max_error	0
lcu-prepare-select-block-w1-balanced	1 bit, 2 terms, α=1.4	to_matrix + three paths	max_error	3.5e-16
lcu-prepare-select-block-w2-mixed	2 bits, 3 terms, α=2.2	to_matrix + three paths	max_error	2.2e-16
lcu-prepare-select-block-w2-complex	2 bits, 4 complex-coefficient terms, α=2.14	three paths	max_error	1.7e-16
lcu-prepare-select-block-w3-six-terms	3 bits, 6 terms, α=2.35	three paths	max_error	2.3e-16
qram-prepare-quantization-a8 / -a12	4 terms	reference + rir	TVD	4.9e-3 / 4.0e-4
alias-prepare-distribution-p6 / -p10	4 terms	reference + rir	TVD (bound 6.3e-2 / 3.9e-3)	3.9e-3 / 2.4e-4
alias-prepare-select-block	α=2.2, precision 10	reference + rir	block error (bound 3.9e-3)	3.9e-4
abstract-prepare-bind-in-be	3 terms, α=2.2	reference	max_error / bind_deviation	2.2e-16 / 0

Reproduction command:

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

Artifacts: out/verification/blockencoding.json.