THE QUANTUM INTELLIGENCER

The established method of building a reversible circuit from a Boolean specification is to minimise the expression and map the result. The assumption underneath it, that the minimised form is the best form, has held long enough to pass for a rule. A paper deposited with the preprint service reports that the assumption was never complete. Minimised expressions retain algebraic structure that minimisation cannot reach, arising from containment and complementary-polarity relationships among their terms. The structure was present in every minimised expression the method has produced; the minimising step cannot reach it. Extracting it yields circuits cheaper to execute despite containing more operations. The decisive quantity, the authors argue, is not the operation count but the control count of the widest operation, which carries a superlinear cost; shared-factor extraction trades a few wide operations for many narrow ones and reduces the qubit count. Across benchmarks and oracles drawn from quantum search and factoring algorithms, the transformation never increases either cost measure at the representation level, a guarantee the authors derive from its construction. Translation to an executable circuit returns part of the advantage, as auxiliary lines must be uncomputed. The factorised circuit still left a leading circuit-level optimizer reaching lower final counts, and faster, than when it worked unaided. The representation of a computation, the paper concludes, is itself a resource: optimisable before compilation, and distinct from both logic minimisation and circuit-level optimisation. Whether the established toolchains will adopt the step, the paper does not say; the saving exists regardless. —Inspector Grey Dispatch from The Prepared E0