Unitary normal form for finite bit-query algorithms without extra queries

The root state and all nonoracle instruments are input-independent by [F1]. Apply [F2] to those instruments only, retaining their observed outcomes and hidden dilation registers. Each dilation and each block control of a known nonoracle operation is then an input-independent unitary on finitely enlarged registers, allowed as a nonoracle operation in this query model; their gate and preparation costs are separate from oracle count. Retaining the orthogonal histories [F5] and using [F2] with the remaining registers as reference preserves the original branch output law. No oracle operation is dilated or replaced by an assumed controlled oracle.

Synchronize the finite execution tree by query number: before slot q, run each retained history's nonoracle segment until its qth query or termination, keeping terminated histories unchanged. These finite controlled segments are input-independent unitaries by step 1.1. At the slot, an active history presents its address and response to the query wires. On an inactive history, controlled swaps instead present a scratch address i_0 chosen as the first computational-basis label (the empty word for a zero-qubit address register) and a scratch target |+⟩=(|0⟩+|1⟩)/√2, preserving the algorithm registers. This address exists because the address register has positive dimension by [F4]. Apply one unconditional O_x and undo the routing swaps. Since X^{x_i}|+⟩=|+⟩ for every i, this acts identically on inactive histories and as the prescribed query on active ones, including their coherent superpositions.

Use slots q=1,…,T, then execute the final nonoracle segments and read the retained output records. Each slot contains exactly one unconditional oracle call by step 2.1, and step 1.1 adds none, so the total is exactly T, including zero when T=0. Histories with fewer queries are padded by inactive slots. Induction over the slots preserves each branch map and hence the final output law. All remaining operations and the initial state are input-independent; no controlled access to an unknown O_x or gate-efficiency bound is assumed.