DeComp2: Description Complexity aware Decomposition

Quantum compilers typically optimize for execution-only metrics such as gate count, circuit depth, or fidelity. This approach treats the compiled circuit as a static artifact, often unrolling loops and erasing the hierarchical structure that allows for efficient reuse, verification, and optimization. The author argues that this conflates two distinct resources: the runtime cost on the quantum substrate and the description cost required to specify the instructions. By ignoring the latter, compilers discard valuable structural information that could reduce the overall life cycle cost of quantum programs.

To address this, the paper proposes a new objective function, C_tot = α * C_circ + β * C_Kol. Here, C_circ represents the traditional execution complexity (positional entropy), while C_Kol represents the Kolmogorov-style description complexity (kinetic entropy) of the program that emits the gate sequence. This additive framework is inspired by the second law of quantum complexity, which posits that total entropy in an auxiliary system is the sum of positional and kinetic components. By minimizing this joint cost, the compiler acts as a minimum-description-length regularizer, preferring structured, compressible decompositions over equally short but unstructured gate sequences.

The author tested this framework on the SU(2) group using exhaustive enumeration and compression-based surrogates to approximate C_Kol. The results demonstrate that C_circ and C_Kol are not tightly coupled; they correlate positively but break rank order on a significant fraction of targets. This independence confirms that there is a non-trivial set of compilation choices where the joint minimizer differs from the execution-only minimizer. By selecting these alternatives, the compiler preserves hierarchical patterns that would otherwise be discarded, providing a more robust signal for intermediate representation (IR) design in quantum compilers.