Exact all-width depth of four-target coherent selection and a dirty-target fan-out obstruction

Abstract

We determine the complete fixed-width depth curve of the four-target one-hot selector SELECT_X in a fully declared classical-reversible model: gate set {X, CNOT, Toffoli}, pairwise-disjoint-support layers, all-to-all connectivity, dirty data targets, and clean ancillae restored to zero. The curve is D*(4,Q) = infinity for Q < 6; 5 at Q = 6; and 4 for every Q >= 7. The two finite values are exact by exhaustive meet-in-the-middle; the all-width statement rests on a lossless normal-form reduction of any depth-3 clean-ancilla circuit to at most eight wires, whose finite core is certified by two independent machine pipelines: a direct exhaustion of the normal form and a calibrated SAT encoding run under two solvers. A causal lower bound D*(2^k, Q) >= k+1 for every k and every width follows from counting the light cone of one address bit together with the preserved address line; the curve shows it is not tight with clean workspace. If the workspace may instead be left dirty (garbage output), depth 3 is attainable at width 12, and the clean-output constraint raises the optimum by exactly one layer for every width budget Q >= 12, while at widths 7 to 9 garbage does not help. For ancilla-free dirty-target fan-out we compute the exact minimum depths through seven targets and prove that 2^d - 1 targets require depth at least d+1, one above the causal floor. Exact minimum-width depths for the threshold selector (3, 4, 4 at m = 2, 3, 4) and provisional minimum-width floors for a nonlinear arithmetic payload (pending exact-signature revalidation) complete the picture. All exact values are backed by reproducible code, logs and hashes. No priority claim is made: a systematic novelty search is not complete, and no result is asserted as first or novel. AI-based tools were used to assist with the drafting and revision of the text; the author reviewed and validated all content and is solely responsible for the results.