Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits
本文证明了对于具有对数级 T 深度(logarithmic T-depth)的 Clifford+T 电路,判定精确非恒等检查(Exact Non-Identity Check, ENIC)仍然是 NP-hard 的,从而排除了针对此类电路通过基于门隐形传输(gate-teleportation)的不可区分混淆(indistinguishability obfuscation)实现高效性的可能性,除非 P=NP。