Coherent normal form for finite quantum query algorithms

At an instrument node with outcome maps $({\mathcal{I}}_a{)}_{a\in \mathrm{\Omega }}$, choose a finite Kraus family $(K_{a,r}{)}_r$ for each ${\mathcal{I}}_a$ by [F3]–[F4]. The formula in [F5] shows that their union is a Kraus family for the total map $\mathrm{\Phi }={\sum }_a{\mathcal{I}}_a$. The trace identity in [F3] makes $\mathrm{\Phi }$ trace-preserving, so [F6] gives ${\sum }_{a,r}{K}_{a,r}^{†}{K}_{a,r}=I$.

Label every node of the finite execution tree by the number of oracle calls already made on its path. For each $t<T$, order the finitely many nonoracle nodes in that query-count slice by tree depth, execute each node on histories with its observed-outcome prefix, and use the identity on histories already at their next query or terminal node. This places every next query at one common slot while preserving each branch's transitions; histories that have terminated are inactive in this and every later slot. The retained outcome history identifies the branches that still make a query. On every inactive branch, conditionally swap the caller's entire $N$-level address register with a fresh register of the same dimension initialized to $\mathrm{\mid }0⟩$, and swap the caller's response qubit with a fresh qubit initialized to $\mathrm{\mid }+⟩$, prepared using $H$ from [F11]. The address-register swap is the finite basis permutation exchanging the two ordered register factors; controlling it on the retained history gives a finite input-independent unitary. After the ordinary oracle call, reverse both conditional swaps. On an inactive branch the oracle acts on $\mathrm{\mid }0⟩\mathrm{\mid }+⟩$ as either $I$ or $X$ on the response, both of which fix $\mathrm{\mid }+⟩$; the caller's address and response, including any entanglement with work, are restored. Active branches are unchanged, so this pads the slot without controlled oracle access.

Add a finite label register $L$ with orthonormal basis $\mathrm{\mid }a,r{⟩}_L$ and use the same factor order throughout, defining $V:H\to L\otimes H$ by $V\psi ={\sum }_{a,r}\mathrm{\mid }a,r{⟩}_L\otimes K_{a,r}\psi$. Orthonormality [F9], the adjoint identity [F7], and step 1.1 give $⟨V\psi ,V\varphi ⟩={\sum }_{a,r}⟨K_{a,r}\psi ,K_{a,r}\varphi ⟩=⟨\psi ,\varphi ⟩$; hence $V$ is an isometry. For any density operator $\rho$, projecting the label onto the outcome subspace spanned by $\{\mathrm{\mid }a,r{⟩}_L:r\}$ and discarding the label leaves ${\sum }_r{K}_{a,r}\rho K_{a,r}^{†}$; orthogonality removes all unequal-label cross terms. By [F5] this is exactly ${\mathcal{I}}_a(\rho )$.

In the common codomain $L\otimes H$, let $J\psi =\mathrm{\mid }0{⟩}_L\otimes \psi$ be the clean-ancilla embedding. The images under $J$ and $V$ of one orthonormal basis of $H$ are orthonormal lists of the same finite length in this same finite-dimensional space. Choose a finite spanning basis by [F10]; process it in order, subtracting its projections onto the current list and appending the normalized nonzero remainder. This finite Gram–Schmidt procedure completes each list to an orthonormal basis. Mapping the first completed basis to the second defines a unitary $U$ with $UJ=V$, so the instrument node is realized by an ordinary unitary and retained outcome/Kraus labels.

Keep each observed outcome in an orthogonal record register; hidden Kraus labels remain orthogonal environment labels and are not used by later controls. Induct over the finite execution tree, comparing the unnormalized system density for each observed history after tracing out its hidden labels. A unitary node applies the same branch unitary on every hidden-label subspace, and an instrument node has child reduced density ${\mathcal{I}}_a(\rho )$ by step 2.1, so each history's unnormalized system density agrees with the original instrument computation. At terminal histories, measuring the declared output and ignoring the orthogonal records therefore gives exactly the output law in [F2].

Insert one such ordinary call in each of the $T$ slots, using input-independent history controls for active and padded branches. Steps 1.1–4.1 preserve every output probability, and step 1.2 pads only branches with fewer than $T$ calls. Thus the resulting pure-state circuit has exactly $T$ ordinary XOR calls and the original output distribution.