Coherent variable-time algorithm model

A finite coherent variable-time algorithm has a finite family of stopping times $0<t_1<\cdots <t_m=T_{\max }$, a designated output space, and a finite clock/step register. A run is unfinished at stage $j$ if it has not entered a stopping subspace by $t_j$; otherwise it is stopped. The stopping subspaces are pairwise orthogonal, and the output register labels each stopped branch as good or bad. Every later stage is controlled on the unfinished projector, so a stopped branch is not advanced. Admissibility requires the first-stop subspaces to exhaust the reachable state at $T_{\max }$ for every allowed input; no branch remains unfinished after the final stage. The input specifies each stage unitary, its inverse and every controlled form used, and the gate/query cost for each.

For a normalized input state, let $p_i$ be the Born probability mass in the subspace that first stops at $t_i$. These are nonnegative masses of orthogonal subspaces whose sum is the reachable state at the final time, so $p_i\ge 0$ and ${\sum }_{i=1}^m{p}_i=1$. Define the root-mean-square stopping time $T_{\mathrm{a}\mathrm{v}}:={\left({\sum }_{i=1}^m{p}_i{t}_i^2\right)}^{1\mathrm{/}2}\mathrm{.}$ Let $p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}$ be the total Born probability of the good-output subspace. When $p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}>0$, the good output means the normalized conditional state of the declared good projector; it is defined only on that positive-probability branch. The mean stopping time ${\sum }_i{p}_i{t}_i$ is a different quantity and is not substituted for $T_{\mathrm{a}\mathrm{v}}$.

A measured adaptive procedure qualifies only if it has a finite coherent implementation with the same stopped/unfinished branch semantics and the required inverse/coherent access. Measurement records used to choose a circuit may be classical construction data; no intermediate measurement is inserted into a branch whose later inverse must erase that record. All stopping times, branch probabilities, reflections, inverses, controlled calls, and state preparation remain explicit resource inputs. Complexity statements use an actual normalized primitive-operation coordinate: positive counts are at least one, and the declared interval budgets include the preparation, controlled/inverse and input/selected-reflection operations used in the construction. Other weighted time coordinates may be recorded, but arbitrary uncharged subunit weights do not inherit logarithmic operation-count bounds.

A supplied-probability production regime must specify finite probability/schedule certificates rather than infer them from black-box unitary access. For $h+1\le n$ dyadic intervals indexed $j=0,\dots ,h$, initialize $s_{-1}=r_{-1}=1$ and require $p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}>0$. The original good-or-unfinished masses satisfy $1\ge s_{j-1}\ge s_j\ge p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}>0$ and $s_h=p_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}$, so $q_j=r_{j-1}{s}_j\mathrm{/}{s}_{j-1}$ is defined. Supply odd multipliers $d_j=2k_j+1$ and certificates for the actual amplified selected masses satisfying $r_j\ge 1\mathrm{/}(16n)$ and $r_j\ge (1-2\mathrm{/}(5n))d_j^2{q}_j$; an unamplified interval has $d_j=1$ and $r_j=q_j$. Supply also a rational $\mathrm{\ell }$ with $r_h\mathrm{/}2\le \mathrm{\ell }\le r_h$. These are the finite schedule inequalities for the supplied-data production regime. Data may use exact rational/algebraic representations, certified rational enclosures with the stated valid inequalities, or a separately declared exact-real representation/comparison resource. The finite construction and verification cost $C_{\mathrm{b}\mathrm{u}\mathrm{i}\mathrm{l}\mathrm{d}}$ includes every oracle call used to acquire or certify probability information, as well as classical arithmetic, list generation and output costs. No zero-query method obtaining these data is assumed. A uniform regime without those certificates must instead state its supplied probability floor, confidence and complete estimation/production costs. Branch probabilities defined above remain valid analysis quantities even when they are unknown to the implementation.