Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits

Abstract:In 2021, Broadbent and Kazmi developed a gate-teleportation-based protocol for computational indistinguishability obfuscation of quantum circuits. This protocol is efficient for Clifford+T circuits with logarithmically many T-gates, where the limiting factor in the efficiency of the protocol is the difficulty, on input a quantum circuit $C$, of the classical task of producing a description of the unitary obtained by conjugating a Pauli $P$ (corresponding to a Bell-measurement outcome) by $C$, where this description only depends on the input-output functionality of $CPC^{\dagger}$. The task above, in turn, is at least as hard as the problem of determining whether two $n$-qubit quantum circuits are perfectly equivalent up to global phase. In 2009, Tanaka defined the corresponding decision problem Exact Non-Identity Check (ENIC) and showed that ENIC is NQP-complete and thus NP-hard as well. Motivated by the 2021 protocol, we consider in this work what happens when we pass from low T-count to low T-depth. We show that, for Clifford+T-circuits of T-depth $O(\log(n))$, deciding ENIC remains NP-hard. In particular, we show this by relating certain decision problems on Pauli coefficients of Clifford+T unitaries to well-known hardness results for codeword weights in binary linear codes. This effectively rules out the possibility, for Clifford+T-circuits of logarithmic T-depth, of either efficient ENIC or efficient gate-teleportation based computational indistinguishability obfuscation, unless P=NP. It also provides a new, independent proof of the hardness of ENIC, even at low T-depth. Along the way, we prove the NP-hardness of some related circuit problems.

arXiv:2511.17856 [quant-ph]

(or arXiv:2511.17856v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2511.17856 Focus to learn more arXiv-issued DOI via DataCite

IEEE Trans. Inf. Theory 72(10) (2026) pp. 7650-7668

https://doi.org/10.1109/TIT.2026.3723681 Focus to learn more DOI(s) linking to related resources

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.