Circuit Optimization Task

A circuit-optimization instance consists of (i) a finite circuit in the ordered syntax of Finite circuit syntax and ordered wire labels, with denotation given by Denotational semantics of a finite layered circuit, over one fixed finite exact gate alphabet, (ii) a declared equivalence relation—exact equality of those denoted matrices, or the whole-circuit phase relation $U{\sim }_{\mathrm{p}\mathrm{h}\mathrm{a}\mathrm{s}\mathrm{e}}V$ from Global Phase Equivalence, and (iii) an ancilla policy and one applicable cost coordinate. The ancilla policy specifies the allowed initial ancilla states and exact return obligations under Clean and dirty ancillas. The cost coordinate is chosen from gate-occurrence count (size), minimum-layer depth, T-count, or width, using the precise meanings of Finite circuit resource accounting and Circuit-family and computation cost model. Here minimum-layer depth is $d(C)$ from Circuit-family and computation cost model; T-count is the number of occurrences labeled $T$ or $T^{†}$ from Clifford+T gate library and exact matrices, so that coordinate is applicable only when the instance's alphabet contains those gates. The selected coordinate is part of the instance and remains fixed when comparing outputs.

Phase equivalence is applied only to the denotation of the whole standalone circuit. A phase on a unitary generally becomes a relative phase when that unitary is placed under control, so an optimizer may not silently replace a controlled subcircuit by a phase-equivalent one. The instance must specify controlled access explicitly when controls are present.

A feasible output is a circuit over the same gate alphabet and wire policy, with the same denotation under the chosen equivalence and no greater value of the selected cost coordinate. A globally optimal output has minimum selected cost among all feasible circuits in that declared model. This defines an optimization task; it supplies no algorithm or general optimality guarantee.