Computational circuit analysis determines exact depth-width tradeoffs for four-target reversible selectors, demonstrating the overhead of clean ancilla restoration in logic circuits.
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.
No takes yet. Share an insight, caveat, or question.
Daniel Martín (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: