The partial-output acceptance law is a finite probability law

Write ${\psi }_x=U_{C_n}(\mathrm{\mid }x⟩\otimes \mathrm{\mid }{0}^{a(n)}⟩)$ and $\phi =P_{O_n}{\psi }_x$. The input and zero-auxiliary vector has norm one by the computational-basis orthonormality in [F3]. By [A1] the circuit denotation is unitary, so it preserves norm. The permutation in [F4] bijects an orthonormal product basis; expanding in that basis and applying [F5] shows that it also preserves norm. Hence $\mathrm{\parallel }\phi {\mathrm{\parallel }}^2=1$.

Expand $\phi ={\sum }_{z,w}{c}_{z,w}{e}_{z,w}$ in the finite product basis, where $c_{z,w}=⟨\phi ,e_{z,w}{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}$ by [F5] and [F6]. Parseval gives ${\sum }_{z,w}\mathrm{\mid }{c}_{z,w}{\mathrm{\mid }}^2=1$. Each $p_{C_n}(z\mid x)={\sum }_w\mathrm{\mid }{c}_{z,w}{\mathrm{\mid }}^2$ is nonnegative, and summing over $z$ gives one. By [F13] these weights form a finite probability space on the output strings. Its acceptance event is $\{z:A_n(x,z)=1\}$, so its probability is $p_{C_n}(x)$ and lies in $[0,1]$.

Let $\rho$ be the endomorphism with coordinate matrix $v{v}^{†}$, where $v=(c_{z,w}{)}_{z,w}$. This matrix is Hermitian, and for every coordinate vector $y$, $⟨\rho y,y{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}=y^{†}v{v}^{†}y=\mathrm{\mid }{v}^{†}y{\mathrm{\mid }}^2\ge 0$. Also $\mathrm{tr}(\rho )={\sum }_{z,w}\mathrm{\mid }{c}_{z,w}{\mathrm{\mid }}^2=1$ by [F11] and step 2.1. Thus $\rho$ is a density operator by [F7]. Put ${\rho }_O={\mathrm{Tr}}_W\rho$. Its entries are ${\sum }_w{c}_{z,w}\stackrel{‾}{c_{z^{\mathrm{\prime }},w}}$ by [F9], so $({\rho }_O{)}_{z,z^{\mathrm{\prime }}}=\stackrel{‾}{({\rho }_O{)}_{z^{\mathrm{\prime }},z}}$. For any output-register vector $u$, the root pairing gives $⟨{\rho }_{O}u,u{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}={\sum }_w\mathrm{\mid }{\sum }_z\overline{c_{z,w}}{u}_z{\mathrm{\mid }}^2\ge 0$; its trace is ${\sum }_{z,w}\mathrm{\mid }{c}_{z,w}{\mathrm{\mid }}^2=1$. Therefore ${\rho }_O$ is a density operator, including when $O_n$ or $W_n$ is empty.

For each output string $z$, let $P_z$ be the coordinate projection that fixes the output basis vector $e_z$ and annihilates every $e_{z^{\mathrm{\prime }}}$ with $z^{\mathrm{\prime }}\mathrm{\ne }z$. The product basis in [F3] and [F4] makes these nonnegative orthogonal projections with ${\sum }_z{P}_z=I$. They form the finite computational-basis POVM. By [F8], [F10], [F11], and [F12], its outcome weight is $\mathrm{tr}({\rho }_O{P}_z)=\mathrm{tr}(\rho (P_z\otimes I_W))={\sum }_w\mathrm{\mid }{c}_{z,w}{\mathrm{\mid }}^2=p_{C_n}(z\mid x),$ where the middle equality is the diagonal trace in the product basis and [F2] gives the last equality. Summing over the accepting outputs identifies its event probability with $p_{C_n}(x)$. If $O_n$ is empty, its output set has the single empty string and $P_z=I_{\mathbb{C}}$; if $W_n$ is empty, the sum over $w$ has its single empty-string term. The same formulas cover both cases.