Normalized output law for finite quantum query branches

The standard input register vector and zero-work-register vector are supplied by [F1]; they are computational-basis vectors and hence unit vectors by [F9]–[F10]. Their combined basis vector is unit by the same orthonormal product-basis fact. Its rank-one projector is a density operator by [F11], so the root state has trace one and is nonnegative.

If $\rho$ is a density operator and $U$ is a unitary endomorphism node, then [F12] supplies the unitary denotation for circuit blocks; any other unitary edge is explicit in [A1]. The operator $U\rho U^{†}$ is self-adjoint by [F6] and ${\rho }^{†}=\rho$. For every $v$, the adjoint identity gives $⟨U\rho U^{†}v,v⟩=⟨\rho U^{†}v,U^{†}v⟩\ge 0$. Cyclicity and [F7] give $\mathrm{tr}(U\rho U^{†})=\mathrm{tr}(\rho U^{†}U)=\mathrm{tr}(\rho )=1$. Thus the successor state is a density operator and the edge preserves its branch weight.

At an instrument node with density input ${\rho }_h$, [F3] gives $q_{h,a}\ge 0$ and ${\sum }_a{q}_{h,a}=1$. If $q_{h,a}>0$, [F4] gives a density operator at that child; if $q_{h,a}=0$, the child weight is zero and no conditional state is used. Therefore the sum of child weights is $w(h){\sum }_a{q}_{h,a}=w(h)$.

At depth zero the frontier consists only of the root, whose weight is one and whose state is a density operator by step 1.1. Assume the same assertions for a finite frontier. At each live unitary node, step 1.2 preserves the state property and weight; at each instrument node, step 1.3 gives density states on positive children and preserves the sum of child weights. For the induction, carry an already-terminal positive-weight node forward along a single identity-unitary edge, retaining its state and weight; carry a zero-weight terminal node forward at weight zero without assigning a state. These padding edges add no outcome branch. Summing over the finite frontier by [F13] shows that the next frontier again has total weight one and a density state at every positive-weight node.

Let $D$ be the maximum depth of the original tree. Repeating the extension from step 2.1 carries each earlier positive-weight leaf to depth $D$ without changing its state, weight, or assigned output wires; zero-weight leaves remain weight zero and have no assigned state. The base and successor cases are those in step 2.1, so induction [F14] reaches this common frontier. Therefore the original positive-weight leaves have total weight one and density-operator states.

At a positive-weight leaf, each pair $(z,v)$ specifies exactly one full computational-basis word because the output-wire tuple has distinct indices and $W_{\mathrm{\ell }}$ is its complement. Conversely every full word has exactly one such pair. Thus [F9]–[F10] make the vectors $e_{\mathrm{\ell },z,v}$ a complete orthonormal basis. Each $⟨{\rho }_{\mathrm{\ell }}{e}_{\mathrm{\ell },z,v},e_{\mathrm{\ell },z,v}⟩$ is nonnegative by [F5], and their finite sum over $(z,v)$ is $\mathrm{tr}({\rho }_{\mathrm{\ell }})=1$ by [F8]. Therefore $q_{\mathrm{\ell }}(z)\ge 0$ and ${\sum }_z{q}_{\mathrm{\ell }}(z)=1$, including the empty-output or empty-work-register cases.

Summing the definition of $P(z\mid x)$ over all output strings and interchanging its finite leaf and output sums by [F13] gives ${\sum }_{z}P(z\mid x)={\sum }_{\mathrm{\ell }}w(\mathrm{\ell }){\sum }_z{q}_{\mathrm{\ell }}(z)={\sum }_{\mathrm{\ell }}w(\mathrm{\ell })=1$ by steps 3.1 and 4.1. Each term is nonnegative, so any predicate-selected subset has probability between zero and one. The terminal marginal is normalized directly by the basis-and-trace calculation in step 4.1; instrument branch normalization and conditional-state density use [F3] and [F4] in step 1.3.