Manuscript Oai280-C@1 · Oai280-C.tex · proposition · 7d44b8c0
Proposition: Balanced recursive modules
Resource-restricted programmes › A decomposition-specific tree comparison · lines 1168–1194 · proof included or linked
Oai280-C@1#prop:tree
Concatenate the five-qubit encoder to depth and retain three designated children at every node. Within the module class in which each child is fully decoded before being consumed by its parent, the depth-first measurement-assisted schedule has peak , for . This is optimal in that module class.
The explicitly non-adaptive schedule that receives and holds all selected leaves before any decoding has peak .
Proof. At height one, Theorem thm:stream gives peak two. At a parent, decode the first child and retain its one-qubit output. Decode the second child while holding that output, measure the two outputs using the parent two-qubit measurement, and discard them. Decode the third child and apply the parent feedforward. If the child peak is , the parent peak is . Thus .
In the declared module class, two completed child outputs are needed for the parent measurement. One must be held while a second child is decoded. This gives the same recurrence as a lower bound. The non-adaptive peak follows from its stipulated initial holding of all selected leaves; later decoding need not exceed that count.