# PREPARE–SELECT Decomposition

**English** · <a href="../../zh/manual/algorithms/prepare-select.html">简体中文</a>

> Category C5/C1 · Module [`oracq.algorithms.common.prepare_select`](../../api/algorithms/common/prepare_select.rst) · 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](alias-preparation.md)).

## Interface and input model

```python
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: {obj}`abstract_prepare <oracq.algorithms.common.prepare_select.abstract_prepare>`, {obj}`gate_prepare <oracq.algorithms.common.prepare_select.gate_prepare>`, {obj}`qram_prepare <oracq.algorithms.common.prepare_select.qram_prepare>`, {obj}`select_pauli <oracq.algorithms.common.prepare_select.select_pauli>`

- `coefficients`: at least two finite complex coefficients, not all zero (for a single term use {obj}`scale <oracq.algorithms.input_model.operators.scale>` directly).
- {obj}`abstract_prepare <oracq.algorithms.common.prepare_select.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).
- {obj}`qram_prepare <oracq.algorithms.common.prepare_select.qram_prepare>`: returns {obj}`QramPreparation(preparation, memory) <oracq.algorithms.common.prepare_select.QramPreparation>`, with the angle table `memory = {"angles": ...}` bound as QRAM data by the caller (`angle_width` 2..32).
- `terms` of {obj}`select_pauli <oracq.algorithms.common.prepare_select.select_pauli>` / {obj}`lcu_prepare_select <oracq.algorithms.common.prepare_select.lcu_prepare_select>`: a sequence of `(coefficient, Pauli word)` pairs or a {obj}`PauliHamiltonian <oracq.algorithms.common.hamiltonian.PauliHamiltonian>`; words allow only `IXYZ`, all terms are of equal width, and SELECT requires at least two terms.
- `lcu_prepare_select`: `prepare` defaults to {obj}`gate_prepare <oracq.algorithms.common.prepare_select.gate_prepare>` and may also be given an abstract / QRAM / alias handle (adapted via {obj}`as_state_preparation <oracq.algorithms.input_model.interfaces.as_state_preparation>`); a single term degenerates to `scale(c, pauli_word)`.

Attributes of the returned objects:

| Object | Attributes |
|---|---|
| PREPARE variants ({obj}`StatePreparation <oracq.algorithms.input_model.oracles.StatePreparation>`) | `width` = selector width; module attributes `prepare_terms` / `prepare_alpha` / `selector_width` |
| `select_pauli` ({obj}`Operation <oracq.infrastructure.builder.Operation>`) | registers `selector` / `target`; attributes `algorithm="select_pauli"`, `select_terms`, `selector_width` |
| `lcu_prepare_select` ({obj}`BlockEncoding <oracq.algorithms.input_model.operators.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 {obj}`gate_state_prep <oracq.algorithms.input_model.oracles.gate_state_prep>` (amplitudes $\sqrt{|c_i|/\alpha}$ zero-padded to $2^{\text{selector}}$); the QRAM variant reuses the {obj}`qram_state_prep <oracq.algorithms.input_model.oracles.qram_state_prep>` rotation tree, with the angle table generated by {obj}`qram_state_angles <oracq.algorithms.input_model.oracles.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 {obj}`qubitization_walk <oracq.algorithms.common.transforms.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 {obj}`bind <oracq.infrastructure.linking.bind>` the distribution is exactly unchanged, and after the QRAM binding attaches the angle table via {obj}`Binding <oracq.infrastructure.linking.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](alias-preparation.md)); 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](alias-preparation.md), [State preparation oracle](state-preparation.md), [XOR database](xor-database.md)
- API reference: [PREPARE-SELECT decomposition](../../api/algorithms/common/prepare_select.rst)
- Concepts: [Oracles and operator representations](../operators.md)
- Validation matrix: [Validation coverage matrix](../../development/validation-coverage.md)

## 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:

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

Artifacts: `out/verification/blockencoding.json`.