9.8 Bounded and weighted catalytic resources
On this page · Permalink · Source line 2211
The connected snapshot family uses a single matched excursion: one upper-directed gate opens the dirty carrier and one upper-directed gate closes it. This permits a sharper statement than the unrestricted inequality \({\ell_{*}}<{\ell_{\downarrow}}\).
9.8.1 A bounded number of upper-directed gates
On this page · Permalink · Source line 2215
For a circuit word \(w\), let \(u(w)\) denote its number of upper-directed gates.
Definition 9.38: Upper-gate budget
For \(q\ge0\) and \(A\in{\operatorname{U}}_n({\mathbb F})\), define
Thus
Proposition 9.39: Two upper gates give a linear advantage
For every snapshot target \(A=A(u;s_1,\ldots,s_v)\),
Consequently,
For the optimized connected target \(A_n\) of Corollary 9.6,
Proof
The exact restricted value is Theorem 9.5. Its ambient construction has precisely two upper-directed gates, namely the opening and closing operations on the carrier row; all \(u\) updates and all \(v\) reads are lower directed. The optimized choice has \(v=\lfloor(n-1)/2\rfloor\).
Corollary 9.40: No budget-only additive simulation bound
There is no finite constant \(K\) such that
for all dimensions, fields, and lower-unitriangular targets \(A\).
Proof
The left-minus-right difference in Proposition 9.39 tends to infinity with \(n\).
Thus the power of the excursion is not controlled by the number of forbidden gates. It is controlled by how many useful carrier states are exported between opening and closing.
9.8.2 Rank-one, bandwidth-one flag escape
On this page · Permalink · Source line 2273
The number of upper gates does not measure how far a circuit travels from the lower subgroup. We now control every intermediate state.
For \(X\in{\operatorname{SL}}_n({\mathbb F})\), let \(X^+\) be the matrix obtained by retaining only the strict upper entries of \(X\). Define
and
with \(b^+(X)=0\) when \(X^+=0\). Let \({\ell^{(r,b)}}(A)\) be the minimum length of a transvection circuit from \(I\) to \(A\) such that every prefix matrix \(X\) satisfies
Lemma 9.41
For \(A\in{\operatorname{U}}_n({\mathbb F})\),
Proof
A lower-directed gate preserves lower triangularity. Conversely, if \(X\) is lower unitriangular and an upper-directed gate \(R_t\leftarrow R_t+aR_s\) with \(t<s\) is applied, then the new \((t,s)\) entry equals
The next state is therefore not lower triangular. A circuit whose every prefix has zero strict upper part uses only lower-directed gates.
Theorem 9.42: Microscopic escape, macroscopic saving
For every field \({\mathbb F}\) and every \(n\ge7\), there is a connected target \(A_n\in{\operatorname{U}}_n({\mathbb F})\) such that
The length-\(n\) circuit witnessing the second term uses exactly two upper-directed gates.
Proof
Use the connected family from Corollary 9.6, with the carrier coordinates \(p<q\) adjacent. Between the opening and closing gates, the only strict upper entry is the coefficient at position \((p,q)\). Hence every prefix has upper rank at most one and upper bandwidth at most one. The displayed ambient circuit has length \(n\), whereas
Subtracting proves the claim.
9.8.3 A weighted upper-gate metric
On this page · Permalink · Source line 2333
A hardware or fault model may penalize an upper-directed interaction more heavily than a lower-directed one. Fix \(\lambda>0\). If \(w\) has \(d(w)\) lower-directed gates and \(u(w)\) upper-directed gates, put
and define
At \(\lambda=1\) this is the ordinary ambient length, while large \(\lambda\) increasingly penalizes flag excursions.
Proposition 9.43: Fixed penalties do not suppress catalysis
For every snapshot target \(A=A(u;s_1,\ldots,s_v)\) and every \(\lambda>0\),
Consequently,
For the optimized connected family,
In particular, for every fixed finite \(\lambda\), the weighted advantage grows linearly with \(n\).
Proof
The displayed catalytic word contains \(u+v\) lower-directed gates and two upper-directed gates, so its weighted cost is \(u+v+2\lambda\). Subtract this from the exact restricted value \(u+2v\). The optimized family again has \(v=\lfloor(n-1)/2\rfloor\).
Remark 9.44: Penalty threshold
For the displayed realization of a snapshot target, catalysis beats the optimal lower-only cost whenever
The critical penalty therefore scales with the number of consumers, not with the dimension of the dirty workspace.
Proof of Theorem 9.7
Combine Proposition 9.39 and Proposition 9.43.