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

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 in general. Motivated by this, we consider in this work what happens when we pass from low T-count to low T-depth. In particular, we show that, for Clifford+T circuits of T-depth O\(log(n\)), deciding ENIC is NP-hard. 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.