Tight computational-complexity classification of exact T-count circuit optimization

The decision problem T-COUNT (given an integer $k$ and a Clifford+T circuit implementing a unitary $U$ , decide whether some Clifford+T circuit implements $U$ with at most $k$ T gates, with equivalence over the full state space) is known to be NP-hard under polynomial-time Turing reductions and contained in $NP^{NQP}$ ; its classical-reversible analogue TOF-COUNT, whose NOT/CNOT/Toffoli gate set cannot implement the Hadamard gate, has the same known bounds. A 2025 result (Kjelstrøm–Pavlogiannis–van de Pol) improved the lower bound to co-NQP-hardness — hence outside the Polynomial Hierarchy unless it collapses — but for a generalized problem in which the optimized circuit need only behave equivalently on a desired subspace; as their abstract states, this complements the earlier NP-hardness lower bound established for equivalence over the full state space, so the best known lower bound for T-COUNT as defined here remains NP-hardness. The open problem posed by the source is the exact classification of T-COUNT: is it complete for $NP^{NQP}$ under a suitable reduction, or does it admit a strictly smaller upper bound? The gap between the NP-hardness lower bound and the $NP^{NQP}$ upper bound remains open, with a documented obstacle: NQP-style reasoning requires exact circuit equality while Clifford+T is only approximately universal.

Background

In fault-tolerant quantum computation under stabilizer error-correcting codes (the standard family of quantum error-correcting codes built from Pauli operators), gates from the Clifford group — the normalizer of the Pauli group, generated for example by CNOT, Hadamard, and $S$ gates — can be implemented cheaply, while the non-Clifford $T$ gate $\mathrm{diag}(1,e^{i\pi/4})$ is comparatively expensive. The Clifford+T gate set (Clifford gates plus $T$ ) is approximately universal for quantum computation, and the number of T gates in a circuit, the T-count, is a standard proxy for the cost of fault-tolerant execution. This motivates the exact optimization problem T-COUNT, defined by van de Wetering and Amy as follows: given an integer $k$ and a Clifford+T circuit implementing a unitary $U$ , decide whether there exists a Clifford+T circuit implementing $U$ using at most $k$ T gates. The optimization version reduces to this decision version by binary search. A classical analogue, TOF-COUNT, asks the same for the number of Toffoli gates ( $|x,y,z\rangle \mapsto |x,y,z\oplus xy\rangle$ ) in reversible classical circuits built from Toffoli, CNOT, and NOT gates; Toffoli gates dominate the T-count of circuits synthesizing classical functions such as the modular exponentiation in Shor's algorithm.

Before 2023, no concrete hardness result was known for exact T-count optimization of general Clifford+T circuits, although heuristics existed and related subproblems (Reed–Muller decoding, symmetric tensor factorization) were believed hard. Van de Wetering and Amy (arXiv:2310.05958, v3 2024, retitled from 'Optimising T-count is NP-hard' to 'Optimising quantum circuits is generally hard') proved that T-COUNT and TOF-COUNT are NP-hard under polynomial-time Turing reductions by encoding Boolean satisfiability, and established an upper bound: both problems are contained in $NP^{NQP}$ , the class of problems decidable by a nondeterministic polynomial-time machine with access to an oracle for NQP. Here NQP (non-deterministic quantum polynomial time) is the quantum analogue of NP in which a nondeterministic quantum computation accepts with nonzero probability; by work of Tanaka (2010), deciding whether a polynomial-size quantum circuit is exactly the identity up to global phase — the exact non-identity check, ENIC — is NQP-complete, so deciding exact equality of two quantum circuits is coNQP-complete. The containment argument nondeterministically guesses a candidate circuit of at most $k$ T gates (any such circuit can be normalized to polynomial size using Clifford normal forms) and uses an NQP oracle to verify exact equality with the target. Note that a QMA oracle — QMA being the quantum analogue of NP with classical verification of a quantum witness, whose complete problems concern approximate equality — does not suffice, because exact equality is required. This contrasts with the purely classical situation, where Boolean circuit minimization is complete for $\Sigma^P_2 = NP^{NP}$ : the only difference in the quantum bound is that the coNP exact-equality check for Boolean circuits is replaced by a coNQP one for quantum circuits. Subsequently (arXiv:2510.16420, 2025) Kjelstrøm, Pavlogiannis, and van de Pol strengthened the lower bound for a generalized problem: given a circuit $C$ over a gate set that implements H and Toffoli exactly — which includes Clifford+T — a bit-string $x$ , and an integer $k$ , find a circuit minimizing count or depth with respect to total gates, non-Clifford gates, superposition gates (gates that can map a computational basis state to a superposition, such as H), or entanglement gates (gates that can entangle qubits, such as CNOT) that behaves equivalently to $C$ on the subspace of inputs $|x\rangle|\psi\rangle$ for all $|\psi\rangle$ ; each of these subspace-equivalence optimization problems is co-NQP-hard, and hence outside the Polynomial Hierarchy unless it collapses. In particular, minimizing T-count over Clifford+T with respect to equivalence on a subspace is co-NQP-hard. Their abstract explicitly contrasts this with the full-state-space setting, stating that the result 'complements recent results in the literature which established an NP-hardness lower bound when equivalence is over the full state space'; the co-NQP bound therefore does not transfer to T-COUNT as defined above, which requires implementing $U$ on the full state space, and the known lower bound for T-COUNT — as for TOF-COUNT — remains NP-hardness. The remaining gap between NP-hardness and the $NP^{NQP}$ upper bound for T-COUNT (and, analogously, for TOF-COUNT) is the subject of this problem. Writing $D[\omega]$ for the ring $\mathbb{Z}[1/\sqrt{2},i]$ of dyadic cyclotomic numbers — the 'Clifford+T domain' over which Clifford+T is exactly universal — the source paper notes the documented obstacle to completeness: the Boolean-circuit completeness proof does not extend trivially even when NQP is restricted to unitaries with entries over $D[\omega]$ .

Problem Statement

Determine the exact computational complexity of the decision problem T-COUNT, answering the source's open question 'What is the exact hardness of T-COUNT?'. T-COUNT: given an integer $k$ and a Clifford+T circuit implementing a unitary $U$ , decide whether there exists a Clifford+T circuit implementing $U$ exactly, over the full state space, using at most $k$ T gates. Known bounds: T-COUNT is NP-hard under polynomial-time Turing reductions (van de Wetering–Amy 2023/2024) and is contained in $NP^{NQP}$ (van de Wetering–Amy, Theorem 4). The co-NQP-hardness result of Kjelstrøm–Pavlogiannis–van de Pol (2025) applies to the generalization in which equivalence is required only on a specified subspace, not to full-state-space T-COUNT. The classical-reversible analogue TOF-COUNT (the same question for the number of Toffoli gates in a reversible classical circuit over Toffoli, CNOT, and NOT gates) has the same known bounds — NP-hardness and containment in $NP^{NQP}$ — and its exact classification is an analogous open question; the target posed by the source, and the target here, is T-COUNT. The problem is to determine the exact complexity class of T-COUNT by matching the strongest known lower bound with a tightest upper bound, thereby closing the remaining gap between the NP-hardness lower bound and the $NP^{NQP}$ upper bound (up to the tightest pair of bounds that can be proved). The outcome the source suggests 'would make sense' is (a) proving completeness for $NP^{NQP}$ under a stated reduction (containment plus a matching hardness result for $NP^{NQP}$ ), while noting the obstacles that NQP requires exact circuit equality whereas Clifford+T is only approximately universal, and that the Boolean-circuit completeness proof does not extend trivially even under the restriction to unitaries over the exactly-universal Clifford+T domain $D[\omega]$ . A classification of T-COUNT at any other class below $NP^{NQP}$ — for instance $NP$ — is an equally acceptable resolution (b) when its upper bound is proved and matched by the known lower bound; a strictly stronger upper bound alone (e.g. containment of T-COUNT in $NP$ or in another class below $NP^{NQP}$ ) is a meaningful partial resolution, and no complexity-class separation is required to be proved. An answer must state the reduction notion used and apply to the exact (non-approximate) optimization problem as defined above.

References

John van de Wetering, Matt Amy. Optimising quantum circuits is generally hard (v1/v2 titled 'Optimising T-count is NP-hard'). arXiv:2310.05958 (2023; v3 2024). DOI: 10.48550/arXiv.2310.05958. https://arxiv.org/abs/2310.05958
Adam Husted Kjelstrøm, Andreas Pavlogiannis, Jaco van de Pol. Exact Quantum Circuit Optimization is co-NQP-hard. arXiv:2510.16420 (2025). DOI: 10.48550/arXiv.2510.16420. https://arxiv.org/abs/2510.16420
Yu Tanaka. Exact non-identity check is NQP-complete. International Journal of Quantum Information 8(5):807–819 (2010). DOI: 10.1142/S0219749910006599. https://doi.org/10.1142/S0219749910006599
Joshua Nevin. Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits. arXiv:2511.17856 (2025). DOI: 10.48550/arXiv.2511.17856. https://arxiv.org/abs/2511.17856
Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva. CNOT-Distance is NP-complete under all-to-all connectivity. arXiv:2608.03825 (2026). DOI: 10.48550/arXiv.2608.03825. https://arxiv.org/abs/2608.03825