DefinitionDefinition: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite measurement branches and classical control

Definition

A measurement stage on a finite-dimensional input register is specified by a finite nonempty observed outcome set $Ω$ and an instrument $(I_{a})_{a \in Ω}$ as in Finite instruments and conditional states. For an input density operator $ρ$ , its unnormalized branch output is $τ_{a} = I_{a} (ρ)$ and its branch weight is $p_{a} = tr (τ_{a})$ . The positive weights sum to one by Instrument outcome weights normalize. The unique POVM induced by the instrument, supplied by Every finite instrument induces a unique POVM, has effects $E_{a}$ satisfying $p_{a} = tr (ρ E_{a})$ . A conditional output is assigned only when $p_{a} > 0$ , using the rule in Finite instruments and conditional states; when $p_{a} = 0$ the value is $⊥$ .

A finite classical controller may retain the observed history $a$ and select a specified finite unitary suffix $S_{a}$ on the quantum data. Its branch map is $X \mapsto S_{a} I_{a} (X) S_{a}^{†}$ . The index $a$ is the observed outcome; any Kraus index used to represent $I_{a}$ is an unobserved environment label and is not stored as classical data.

A finite measurement history tree for a circuit on the fixed register $D = Q_{n}$ is a finite rooted tree whose internal node $h$ carries a finite nonempty outcome set $Ω_{h}$ and an instrument $(I_{a}^{h})_{a \in Ω_{h}}$ from $D$ to $D$ . The edge from $h$ to its child $h a$ carries a specified finite unitary $S_{h, a} : D \to D$ ; its branch map is $X \mapsto S_{h, a} I_{a}^{h} (X) S_{h, a}^{†}$ . Leaves may carry a specified finite terminal POVM on $D$ . The fixed data register is the wire register of Finite circuit syntax and ordered wire labels. A history is the ordered list of observed edge labels from the root; a hidden Kraus index is never included in it. Since the tree is finite and each node has finitely many children, every history and every sum over histories below is finite.

For a coherent representation, order $Ω$ and use the computational basis $(e_{a})_{a \in Ω}$ of the finite label register $Q_{∣ Ω ∣}$ . On the orthogonal decomposition $Q_{∣ Ω ∣} \otimes K = ⨁_{a \in Ω} (span {e_{a}} \otimes K)$ , define the mathematical block operator by $B ⁣ (\sum_{a \in Ω} e_{a} \otimes x_{a}) : = \sum_{a \in Ω} e_{a} \otimes S_{a} x_{a} .$ Its control availability is part of the operation model. In the one-bit case, Controlled Unitary Access specifies the exact access meaning of $C (U)$ ; an ordinary black-box call to $U$ does not grant a controlled call. For larger outcome sets the displayed block gate is likewise an explicit operation, or must be constructed and charged by the chosen model. No gate-set implementation or efficiency bound is part of this definition. A finite history tree is interpreted by applying this definition at each node.

Facts & Assumptions

Given: A finite nonempty outcome set $Ω$ , a finite instrument, an ordered label basis, and a finite family of branch-specific unitaries $(S_{a})_{a \in Ω}$ .

[F1]

Finite instruments and conditional states: each branch map is completely positive, its trace contributes to the outcome law, and conditional outputs are divided by the branch weight only when that weight is positive.

[F2]

Instrument outcome weights normalize: for every density input, the branch weights form a finite probability distribution.

[F3]

Every finite instrument induces a unique POVM: there is a unique POVM $(E_{a})$ with $tr (I_{a} (X)) = tr (X E_{a})$ for every input operator $X$ .

[F4]

Finite registers and their ordered computational bases and Ordered tensor registers, their inner product, and wire permutations: the label register has an ordered orthonormal basis and the tensor product has the product inner product.

[F5]

Controlled Unitary Access: controlled access is an explicit operation capability and is not inferred from a matrix for $U$ .

Proof

1.1givenF4construct

Put $m = ∣ Ω ∣ \geq 1$ and write an arbitrary vector of $Q_{m} \otimes K$ uniquely as $\sum_{a \in Ω} e_{a} \otimes x_{a}$ . The block formula sends it to $\sum_{a} e_{a} \otimes S_{a} x_{a}$ ; orthogonality of the $e_{a}$ makes distinct label blocks orthogonal.

1.2givenF1F2F3

By [F1]–[F3], the observed law is the instrument branch law, equals the induced POVM law, and the conditional state is assigned only on a positive-weight branch. The $⊥$ convention applies on every zero-probability branch; the history tree records only its observed edge labels.

2.1givenstep 1.1algebra

For vectors $\sum_{a} e_{a} \otimes x_{a}$ and $\sum_{a} e_{a} \otimes y_{a}$ , the product inner product gives $⟨ B x, B y ⟩ = \sum_{a} ⟨ S_{a} x_{a}, S_{a} y_{a} ⟩ = \sum_{a} ⟨ x_{a}, y_{a} ⟩ = ⟨ x, y ⟩$ . The block map with $S_{a}^{†}$ in each block is its two-sided inverse, so $B$ is a surjective isometry.

3.1F5step 2.1∎

Step 2.1 establishes the mathematical block unitary. Its inclusion as a circuit operation still requires the explicit access or construction promised by the model, as required by [F5]; the definition grants no additional oracle or gate capability.

Depends on

Used by

Dense-coding procedure Algorithm
Qubit teleportation procedure Algorithm
Coherent variable-time algorithm model Definition
Fault-Tolerant Gadget and Proper-Code Contract Definition
Finite open-graph adaptive measurement pattern Definition
A Finite Four-Round Verified Shor Correction Circuit Lemma
All measurements may be moved to terminal readout Theorem
An Explicit Proper Code and Universal Fault-Tolerant Gadgets Theorem
CSS syndrome correction Theorem
Every finite open-graph pattern is a measurement circuit Theorem
Finite instruments can be coherently deferred Theorem

Dependency tree · two levels

40 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

John Preskill, Quantum Computation, Chapter 3: Foundations II: Measurement and Evolution (standard reference, not scraped)
John Preskill, Quantum Computation, Chapter 5: Classical and Quantum Circuits (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)