Exact Quantum Circuit Optimization is co-NQP-hard

As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical quantum advantage. Here we consider the natural problem of, given a circuit $C$, computing an equivalent circuit $C'$ that minimizes a quantum resource type, expressed as the count or depth of (i) arbitrary gates, or (ii) non-Clifford gates, or (iii) superposition gates, or (iv) entanglement gates. We show that, when $C$ is expressed over any gate set that can implement the H and TOF gates exactly, each of the above optimization problems is hard for $\text{co-NQP}$, and hence outside the Polynomial Hierarchy, unless the Polynomial Hierarchy collapses. This strengthens recent results in the literature which established an $\text{NP}$-hardness lower bound, and tightens the gap to the corresponding $\text{NP}^\text{NQP}$ upper bound known for cases (i)-(iii) over Clifford+T and (i)-(iv) over H+TOF circuits.