BQTISP to Derived-Basis PrTISP Simulation

Detect source work-head collisions before decomposing a transition. The following classical marker construction stores positions without retaining their potentially long binary addresses. Fix a power-of-two stride $K$, independent of $t,s$, large enough for distinct tracks for source classical data, a marker for every source work head, an origin marker, compiler scratch, and a distinct parking track for every physical classical head. Logical cell $a$ on track $b$ is physical cell $Ka+b$. For every source work head $j$, keep one classical probe parked at $K{a}_j+b_j$ and a single $1$ on marker track $j$ at logical position $a_j$; all other bits of that track are zero. Park the initially coincident physical heads at their distinct tracks using identity operations, then set the initial markers at logical zero. The origin track has its sole $1$ at zero and is never changed. To test $a_i=a_j$, move probe $i$ within its current stride block to marker track $j$, read its bit, and return to its parking track. Only that probe leaves its parking track during this test, so at the read no other classical head coincides with it. Transient collisions during movement perform identity operations only. Test all relevant pairs; there are only constantly many. Before a source movement clear each head's old marker using its own probe; then move the probes with their source heads and set their new markers before any further test. A local source move takes $K$ physical moves; probe the origin track to clamp a left move at logical zero. Duplicate each freshly emitted jump-address bit onto the probe's own erased index tape and append its fixed parking-label bits before use, obtaining $K{a}_j+b_j$ without storing or rereading the address. Each source bit is duplicated only constantly many times. This maintains all markers exactly, costs constant time per source transition beyond charged index emission, uses fixed heads and alphabet, and has extent $O(s+1)$. Classical source symbols can likewise be read one probe at a time on the shared data track, saved in finite control, and written sequentially after evaluating the source's fixed classical function; the equality partition determines precisely whether that source operation is omitted. Auxiliary heads remain on distinct tracks, so source collisions do not suppress compiler or marker work. Apply the quantum source's collision-omission rule to the same equality partition: an omitted unitary is replaced by the empty word, not by its elementary factors. Otherwise its operands are distinct and are held fixed throughout its compiled block. The original quantum tape and its query blocks are not interleaved.

Each fixed one-qubit factor $U$ from [A1] has a polynomial-time Cauchy normalization into $SU(2)$. Put $z=\det U$, so $\mathrm{\mid }z\mathrm{\mid }=1$, and hardcode $a\in \{1,-1,i,-i\}$ with $\mathrm{Re}(az)>1\mathrm{/}2$; one exists since the larger absolute coordinate of $z$ is at least $1\mathrm{/}\sqrt{2}$. Set $r=\sqrt{(1+\mathrm{Re}(az))\mathrm{/}2}$ and $v=r+i\mathrm{Im}(az)\mathrm{/}(2r)$. Then $r>\sqrt{3}\mathrm{/}2$, $\mathrm{\mid }v\mathrm{\mid }=1$ and $v^2=az$. Fix an algebraic square root $b$ of $a$ and put $\lambda =b\mathrm{/}v$. Thus $\mathrm{\mid }\lambda \mathrm{\mid }=1$, ${\lambda }^{2}z=1$ and $V=\lambda U\in SU(2)$. The formulas use only [A3] with fixed positive denominator bounds, so every coordinate of $V$ has a polynomial-time Cauchy procedure. There are finitely many factors; their branch constants and one common polynomial query bound may be hardcoded. No exact coordinate digits or run-time equality tests are needed.

For a fixed machine, only finitely many local transition unitaries occur, each on a fixed number of qubits. For every nonomitted unitary in step 1.1, decompose it into a constant number of one-qubit gates and CNOTs using [A1], with polynomial-time Cauchy names for the resulting fixed one-qubit factors. Choose fixed integers $c_T,c_M\ge 1$ so that $T\le c_{T}t$ is the transition clock and $c_M$ bounds the one-qubit factors per transition. Fix ${\eta }_0=1\mathrm{/}8192$ and its base-net certificate from [A2]. Apply the bit-complexity theorem in [A2] to each normalized target $V$ of step 1.2 with rational tolerance $\min (1\mathrm{/}(20c_M{c}_{T}t),{\eta }_0\mathrm{/}2)$. Its target-name, algebraic gate-package, inverse-closure and base-net hypotheses are satisfied. Erase the lifted word's scalar letter phases using [A2]; since $V=\lambda U$, this compiles each factor $U$ to projective error at most $1\mathrm{/}(20c_M{c}_{T}t)$ over $F=\mathrm{diag}(1,(3+4i)\mathrm{/}5)$, its adjoint, and $H$. CNOT and query gates remain exact. Direct multiplication gives $F^{\ast }F=I$ because $(3-4i)(3+4i)=25$; [F3] gives unitary $H$ and CNOT, and [F1] gives the query basis permutation. The finite-bit compiler has word length and bit time polynomial in $\log t$, since the normalized Cauchy procedures have a fixed polynomial query bound and the tolerance has $O(\log t)$ encoding length; workspace is at most bit time. Execute its deterministic work sequentially while holding the original quantum operand heads stationary. Preserve the source's classical transition, fresh index-bit emissions and scheduled jumps/queries once; extra compiler cycles neither duplicate nor consume its pending index words. Use the interleaved classical data, probes and scratch tracks of step 1.1, keeping a snapshot of the source input/classical scanned symbols from the beginning of its transition. Fixed extra classical heads access the compiler scratch track sequentially, whose used length is $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(t)$; the resulting classical extent is $O(s+\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}t)$. The original quantum work tape, operand positions and quantum-query endpoint indices are unchanged, so every native quantum-query block remains contiguous as in [F1]. The constructible bounds [F4] clock these loops, giving compiled time $t^{\mathrm{\prime }}=O(t\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}t)$ and work extent $O(s+\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}t)$.

For a computational-basis measurement [F1], put $P_j=\mathrm{\mid }j⟩⟨j\mathrm{\mid }$ for $j=0,1$; direct calculation gives $P_j^{\ast }=P_j$, $P_j^2=P_j$, $P_0{P}_1=0$, and $P_0+P_1=I$. Postpone it in a proof-only deferred-measurement dilation by reserving a fresh two-qubit record slot, initialized to $\mathrm{\mid }00⟩$, at each of the $T$ transition times and using the isometry $\psi \otimes \mathrm{\mid }00⟩\mapsto P_0\psi \otimes \mathrm{\mid }10⟩+P_1\psi \otimes \mathrm{\mid }11⟩$. The output branches are orthogonal by [F8]–[F9], and their squared norms sum to $\mathrm{\parallel }\psi {\mathrm{\parallel }}^2$ by the projector identities just checked. A transition with no measurement leaves that slot at $\mathrm{\mid }00⟩$. Thus every complete history has a fixed-length record string over the $T$ slots; distinct histories differ in some slot, so [F8]–[F9] make their record subspaces orthogonal, and subsequent classically controlled operations preserve orthogonality by [F1]. These record slots are not allocated by the simulator. A collision-omitted unitary has no compiled factors and zero approximation error. Projective compilation may multiply a one-qubit gate by a phase. Within each fixed history $h$ and transition time $r$, all one-qubit factors act on the same quantum state, so their phases multiply to one scalar ${\lambda }_{h,r}$ on that whole transition block. Rephase each compiled block by this scalar; telescoping its at most $c_M$ one-qubit replacements gives operator error at most $c_M\mathrm{/}(20c_M{c}_{T}t)=1\mathrm{/}(20c_{T}t)$, since surrounding gates and exact measurement dilations have norm one. The direct sum over orthogonal history blocks has this same bound: for $v={⨁}_h{v}_h$ and block errors $E_h$, $\mathrm{\parallel }({⨁}_h{E}_h)v{\mathrm{\parallel }}^2={\sum }_h\mathrm{\parallel }{E}_h{v}_h{\mathrm{\parallel }}^2\le (1\mathrm{/}(20c_{T}t){)}^2{\sum }_h\mathrm{\parallel }{v}_h{\mathrm{\parallel }}^2$. Across the full computation, the actual and rephased compiled final vectors differ by $D={⨁}_h{\mathrm{\Lambda }}_h{I}_h$, where ${\mathrm{\Lambda }}_h$ is the product of the phase factors along history $h$ and $\mathrm{\mid }{\mathrm{\Lambda }}_h\mathrm{\mid }=1$. The accepting projection is block diagonal, $P={⨁}_h{P}_h$, so $⟨Dv,PDv⟩={\sum }_h\mathrm{\mid }{\mathrm{\Lambda }}_h{\mathrm{\mid }}^2⟨v_h,P_h{v}_h⟩=⟨v,Pv⟩$. Thus the rephasing does not change acceptance probability. Telescope the $T$ phase-aligned transition products. Their exact and compiled prefixes and suffixes are norm one, so [F6]–[F7] give state-vector error at most $T\mathrm{/}(20c_{T}t)\le 1\mathrm{/}20$. For unit vectors $u,v$ and accepting projection $P$, $⟨u,Pu⟩-⟨v,Pv⟩=⟨u-v,Pu⟩+⟨v,P(u-v)⟩$. Cauchy–Schwarz [F10] and $\mathrm{\parallel }Pz\mathrm{\parallel }\le \mathrm{\parallel }z\mathrm{\parallel }$ bound the absolute difference by $2\mathrm{\parallel }u-v\mathrm{\parallel }\le 1\mathrm{/}10$. The compiled machine therefore accepts YES inputs with probability at least $17\mathrm{/}30>1\mathrm{/}2$ and NO inputs with probability at most $13\mathrm{/}30<1\mathrm{/}2$.

Fix one input and the compiled computation. For a complete measurement history $\mu$, let $f_{\mu }$ and $h_{\mu }$ count its $F\mathrm{/}{F}^{†}$ and $H$ gates. Let ${\mathrm{\Sigma }}_{\mathrm{a}\mathrm{c}\mathrm{c}}(\mu )$ be the final basis configurations accepted by the fixed machine after history $\mu$, as determined by its finite transition table and terminal acceptance rule. Use the exact matrices from [F3] and the stated $F$ matrix in step 2.1. Expand every $F$ entry with numerator $1$ as five unit terms over denominator $5$, and every numerator $3+4i$ (respectively $3-4i$) as three terms of phase $1$ and four terms of phase $i$ (respectively $-i$). Each Hadamard transition contributes phase $1$ or $-1$ over denominator $\sqrt{2}$; CNOT, query, and computational-basis measurement transitions contribute $0$ or $1$. Thus each path term has phase $\alpha \in \{1,-1,i,-i\}$ and denominator $5^{f_{\mu }}{2}^{h_{\mu }\mathrm{/}2}$. For a final basis state $\sigma$, let $A_{\alpha }(\mu ,\sigma )$ count path terms of phase $\alpha$. Its amplitude is ${\sum }_{\alpha }\alpha A_{\alpha }\mathrm{/}(5^{f_{\mu }}{2}^{h_{\mu }\mathrm{/}2})$. Summing squared magnitudes over the accepting configurations gives the joint probability of history $\mu$ and acceptance: $p_{\mu }^{\mathrm{a}\mathrm{c}\mathrm{c}}=\frac{{\sum }_{\sigma \in {\mathrm{\Sigma }}_{\mathrm{a}\mathrm{c}\mathrm{c}}(\mu )}(A_1^2+A_{-1}^2+A_i^2+A_{-i}^2-2A_1{A}_{-1}-2A_i{A}_{-i})}{{25}^{f_{\mu }}{2}^{h_{\mu }}}\mathrm{.}$ The identity follows by expanding the squared real and imaginary parts, and summing $p_{\mu }^{\mathrm{a}\mathrm{c}\mathrm{c}}$ over histories gives the compiled acceptance probability.

Pad every branch to exactly $t^{\mathrm{\prime }}$ quantum gate slots with identities, and set $F_{\ast }=H_{\ast }=t^{\mathrm{\prime }}$ and $D={25}^{F_{\ast }}{2}^{H_{\ast }}$. Multiply each joint accepting-history numerator in step 3.2 by ${25}^{F_{\ast }-f_{\mu }}{2}^{H_{\ast }-h_{\mu }}$. A bounded nondeterministic machine simulates two path terms in lockstep, requires the same measurement history and final basis row, tests shared classical acceptance, and counts pairs with equal phases positively and opposite phases negatively. The scale factor is exactly realized by $H_{\ast }-h_{\mu }$ extra binary choices and two five-way choices per missing $F$ slot, rejecting invalid encodings. All phase and scale choices use $O(t^{\mathrm{\prime }})$ binary choices. At a measurement, guess one bit, require both basis rows to have it at the measured cell, feed it to their shared classical controller, then discard it. This sums histories without storing a transcript.

Store the two quantum basis rows on two separate binary work tapes and the shared classical configuration on separate fixed tapes, as permitted by [F2]. Corresponding heads on both rows make the same source local moves or fresh jumps; duplicate each newly emitted source index bit to the fixed number of required index tapes, so total address writing is multiplied only by a constant. Separate rows preserve contiguity of each query address block. For $Q_x$ on source cells $[l,r]$, apply native $Q_x$ to each row using copies of its freshly written endpoint indices. Its address bits are unchanged and only its answer cell $r$ is updated. Duplicate the right-endpoint stream also to auxiliary heads on both rows; at query time place these at $r$ to read the old and new answer bits. These heads remain within charged operand extent $s$. There is no copying or scanning of the possibly long address block, and no assertion that $\log n=O(\log t)$. Each row can read a different input bit, exactly as required by its distinct basis path. Maintain a counter $\mathrm{\Delta }$ of positions where the two rows disagree. It starts zero; every local gate or query changes only a fixed number of bits, so mirrored operand heads supply the before/after disagreement indicators and update $\mathrm{\Delta }$. Since at most $O(t^{\mathrm{\prime }})$ bit changes occur, $\mathrm{\Delta }$ uses $O(\log t^{\mathrm{\prime }})$ bits; its final value is zero exactly when the rows agree, avoiding an $O(s)$ terminal scan. Each counter operation costs $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(t^{\mathrm{\prime }})$ bit time. Thus the two bounded path-count machines have time $O(t^{\mathrm{\prime }}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}{t}^{\mathrm{\prime }})$ and extent $O(s+\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}t)$, with accepting counts $N_{+},N_{-}$ satisfying $\mathrm{Pr}[\text{compiled acceptance}]=(N_{+}-N_{-})\mathrm{/}D$.

The sign of $2(N_{+}-N_{-})-D$ decides whether the compiled acceptance probability is above or below $1\mathrm{/}2$. The denominator $D$ is itself a bounded path count: guess $H_{\ast }$ bits and, for each of $F_{\ast }$ factors, two three-bit numbers, accepting only values below $5$. Thus $D$ has exactly $2^{H_{\ast }}{25}^{F_{\ast }}$ accepting branches and is generated in $O(t^{\mathrm{\prime }})$ time and $O(\log t^{\mathrm{\prime }})$ work space. Build bounded nondeterministic machines with path counts $A=2N_{+}$ and $B=2N_{-}+D$ by disjointly tagging the component computations and rejecting noncanonical padding. Pad both to the same total number $2^q$ of paths for an explicitly bounded $q=O(t^{\mathrm{\prime }})$, using zero-only suffix padding to preserve each accepting-path count. A fair leading bit chooses the $A$ machine on branch 0 and the complement of the $B$ machine on branch 1. The resulting machine has $2^{q+1}$ equiprobable paths and $2^q+(A-B)$ accepting paths, so it accepts with probability strictly greater than $1\mathrm{/}2$ exactly when $2(N_{+}-N_{-})-D>0$. The constructible bounds in [F4] let the simulator choose and exhaust these fixed choice lengths. All choice counters can be maintained in $O(\log t^{\mathrm{\prime }})$ bits and $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(t^{\mathrm{\prime }})$ time per choice. The total time is $O(t^{\mathrm{\prime }}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}{t}^{\mathrm{\prime }})=O(t\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}t)$ and work extent is $O(s+\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}t)$ in the derived basis profile.

Step 3.1 places compiled YES acceptance strictly above $1\mathrm{/}2$ and NO acceptance strictly below $1\mathrm{/}2$. Step 6.1 preserves that sign, giving the stated bounded-error quantum to unbounded-error classical inclusion with its full claimed resources in ${\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{S}\mathrm{P}}_{\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}}$. The classical operand-space convention is explicit in [F1]–[F2]; literal head-only accounting with uncharged distant query operands is not claimed. No general simulation into the index-only erased-address or sequential profile has been proved here.