⚛️ quantum physics

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

This paper proves that deciding Exact Non-Identity Check (ENIC) remains NP-hard for Clifford+T circuits with logarithmic T-depth, thereby ruling out the possibility of efficient gate-teleportation-based indistinguishability obfuscation for such circuits unless P=NP.

Original authors: Joshua Nevin

Published 2026-09-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joshua Nevin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the emerging field of quantum computing, scientists are trying to build machines that can solve problems far beyond the reach of today's supercomputers. To do this, they use tiny particles of light or matter that can exist in multiple states at once, allowing them to process information in ways that classical bits cannot. However, these quantum machines are incredibly fragile. To protect the information they hold, researchers often hide the details of how a calculation is performed, a process known as obfuscation. The goal is to let a computer run a specific task without revealing the inner workings of the program, much like handing someone a locked box that performs a calculation when you put something inside, without ever showing them the gears or levers inside. For years, there was hope that a specific type of quantum circuit, one that uses a limited set of basic building blocks, could be obfuscated efficiently. This would have been a major breakthrough for quantum cryptography, allowing for secure communication and private computation on a massive scale.

A recent study by Joshua Nevin challenges this optimism by examining the limits of these quantum circuits. The research focuses on a specific class of circuits built from a standard set of gates, including a special operation called the T-gate, which is essential for making quantum computers powerful but also difficult to manage. The study investigates whether it is possible to efficiently determine if two different quantum circuits are actually doing the exact same thing, a task known as the Exact Non-Identity Check. If this check were easy to perform, it would be a key step toward creating the secure, hidden programs mentioned earlier. Nevin's work proves that for circuits with a very low "depth" of these difficult T-gates—meaning the operations happen in very few sequential steps—this check is not just hard, but mathematically intractable to solve efficiently with current methods, assuming P does not equal NP. The paper demonstrates that the difficulty of checking these circuits is tied to a classic, unsolved problem in mathematics involving the weights of codes, a problem known to be computationally intractable.

The core of the discovery lies in how the researchers connected two seemingly unrelated worlds: the behavior of quantum gates and the properties of binary codes used in error correction. The team showed that when you try to hide a quantum circuit using a method based on teleporting information through a network, the effort required to verify the circuit's behavior grows explosively as the circuit gets slightly more complex. Specifically, they found that even if a circuit only has a logarithmic number of steps involving the difficult T-gates, determining whether it is truly identical to a simple, empty operation is as hard as solving the most difficult problems in a class of computational challenges known as NP-hard. This means that unless a fundamental breakthrough occurs in computer science that allows us to solve these hard problems quickly (specifically, unless P = NP), there is no efficient way to obfuscate these specific types of quantum circuits.

The researchers arrived at this conclusion by translating the quantum problem into a language of binary strings and linear combinations. They constructed a scenario where the coefficients of a quantum operation, which describe how the circuit transforms information, could be made to represent the weight distribution of a binary code. In this context, the "weight" refers to the number of non-zero elements in a string of data. The study proved that calculating these coefficients for low-depth circuits is equivalent to counting the number of specific patterns in a code, a task that is known to be extremely difficult. By showing that the quantum problem maps directly onto this difficult counting problem, the author effectively ruled out the possibility of an efficient solution. They demonstrated that the protocol proposed in 2021 for hiding quantum circuits, which worked well for circuits with very few T-gates, cannot be extended to circuits with slightly more complex structures without hitting a wall of computational difficulty.

This finding has significant implications for the future of quantum cryptography. It suggests that the dream of creating a universal, efficient method to hide quantum programs from prying eyes may be out of reach for a broad and important class of circuits. The study does not say that obfuscation is impossible in all cases, but it draws a sharp line in the sand. It shows that as soon as the circuits move beyond the simplest configurations, the mathematical complexity becomes a barrier that cannot be bypassed with current algorithms. The work also provides a new, independent proof of the hardness of these problems, reinforcing the idea that the difficulty is inherent to the structure of the circuits themselves, rather than just a limitation of our current technology.

The paper also leaves the door open for further inquiry, particularly regarding whether these hard problems remain difficult even when the circuits are restricted to a constant, very small number of steps. The author suspects that the difficulty persists even in these simpler cases, potentially linking the problem to the even more complex task of determining if two different codes are structurally identical. While this remains unproven, the current results are definitive for the logarithmic depth case. The research stands as a rigorous demonstration that nature imposes strict limits on how much we can hide within quantum mechanics, ensuring that some secrets remain computationally locked away, not because of a lack of ingenuity, but because of the fundamental mathematical landscape of the universe.

Technical Summary: Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation Are NP-Hard for Low-T-Depth Quantum Circuits

Problem Statement
This paper investigates the computational complexity of two interrelated problems in the context of quantum circuits composed of Clifford and $T$ gates (Clifford+ $T$ circuits). The first problem is Exact Non-Identity Check (ENIC), which asks whether a given $n$ -qubit quantum circuit $C$ is exactly equivalent to the identity operator up to a global phase (i.e., $C = e^{i\theta}I^{\otimes n}$ ). The second problem concerns the feasibility of Gate-Teleportation-Based Indistinguishability Obfuscation (qiO).

In 2021, Broadbent and Kazmi proposed a protocol for computational indistinguishability obfuscation of quantum circuits. The efficiency of this protocol relies on the ability to classically compute a description of the unitary $C P_x C^\dagger$ (where $P_x$ is a Pauli operator corresponding to a Bell-measurement outcome) efficiently. This task is at least as hard as determining whether two circuits are perfectly equivalent. While Broadbent and Kazmi showed their protocol is efficient for Clifford+ $T$ circuits with logarithmically many T-gates (logarithmic T-count), the complexity for circuits with logarithmic T-depth (number of time steps containing at least one $T$ gate) remained open. The paper addresses whether ENIC and the associated conjugate-encoding tasks remain tractable when restricted to circuits of low $T$ -depth, specifically $O(\log n)$ .

Methodology
The author employs a reductionist approach, linking the complexity of quantum circuit problems to the hardness of problems in coding theory, specifically regarding codeword weights in binary linear codes.

Conjugate-Encoding and Pauli Expansions: The paper analyzes the Pauli expansion of unitaries of the form $C P_x C^\dagger$ . It introduces the concept of a "conjugate-encoding," a classical description of these unitaries that depends only on their functionality. The efficiency of such an encoding is tied to the ability to compute Pauli coefficients.
Reductions to Coding Theory: The core technical strategy involves constructing specific Clifford+ $T$ $T$ circuits (specifically "PC-circuits") whose Pauli coefficients encode the weight enumerator polynomials of binary linear codes evaluated at specific points (e.g., $1/\sqrt{2}$ $1/ 2$ ).
- The paper defines depth- $d$ presentations, a data structure representing the sequence of Clifford and $T$ layers applied to a Pauli.
- It establishes a recursive formula (Proposition 12) showing how the Pauli coefficients of a depth- $d$ presentation relate to those of depth- $(d-1)$ presentations.
- By carefully constructing circuits with specific $T$ -depths, the author demonstrates that the coefficients of the resulting unitary expansion correspond to sums of powers of $1/\sqrt{2}$ indexed by the codewords of a binary linear code.
Hardness Assumptions: The paper relies on known hardness results for binary codes:
- Determining if a binary code contains a codeword of a specific weight is NP-complete (Theorem 8).
- Computing the weight distribution (and thus the weight enumerator polynomial) is #P-hard (Theorem 9).
- The author introduces a specific family of "1-remainder matrices" to embed these coding problems into the quantum circuit setting while maintaining control over the phases in the Pauli expansion.

Key Contributions and Results
The paper establishes the following main results (Theorem 6):

NP-Hardness of ENIC at Low T-Depth: While ENIC is solvable in polynomial time for circuits with $T$ -depth 2 ( $T^2$ ), the decision problem becomes NP-hard for circuits with $T$ -depth $O(\log n)$ . Specifically, there exists a constant $K$ such that ENIC is NP-hard over the domain $T^{K \log n}$ .
Hardness of Related Problems: The problems SUPPORT (determining if a specific Pauli appears with a non-zero coefficient in the expansion of $C P_x C^\dagger$ ) and COMMUTE (determining if $C P_x C^\dagger = P_x$ ) are also shown to be NP-hard over the domain $T^{K \log n}$ .
#P-Hardness of Coefficient Computation: The functional problem of computing the exact value of a Pauli coefficient (CONJUGATE) is shown to be #P-hard over the domain $T^3$ .
Implications for Obfuscation: The results imply that, unless $P = NP$ , the gate-teleportation-based protocol for indistinguishability obfuscation (Broadbent and Kazmi, 2021) cannot be extended to an efficient protocol for Clifford+ $T$ circuits of logarithmic $T$ -depth. The bottleneck is the classical difficulty of producing the required conjugate-encoding (description of $C P_x C^\dagger$ ).

Significance and Claims
The paper claims to provide a new, independent proof of the hardness of ENIC, extending the known complexity landscape from general circuits to those with low $T$ -depth. The significance lies in:

Limiting Obfuscation Protocols: It effectively rules out the possibility of efficient gate-teleportation-based computational indistinguishability obfuscation for the class of logarithmic $T$ -depth Clifford+ $T$ circuits, assuming $P \neq NP$ . This is significant because this protocol was the primary candidate for constructing quantum obfuscation from classical obfuscation.
Connecting Quantum and Classical Complexity: The work bridges quantum circuit analysis and classical coding theory, demonstrating that the algebraic structure of Pauli coefficients in low-depth quantum circuits encodes hard coding-theoretic problems.
Refining Complexity Bounds: The paper narrows the gap between tractable and intractable regimes. It shows that while $T$ -depth 2 is easy, the hardness emerges within the logarithmic depth regime, which is relevant for fault-tolerant quantum computing where $T$ -gates are expensive.

Open Questions
The paper concludes by noting that the exact boundary of hardness remains unclear. It poses whether ENIC remains NP-hard for constant $T$ -depth ( $T^{O(1)}$ ) or if it becomes polynomial-time for $T$ -depth 3. It also suggests that the hardness of the SUPPORT problem might be linked to the "formal code equivalence" problem (deciding if two codes have the same weight enumerator), which is a variant of the code equivalence problem known to be related to Graph Isomorphism.

More like this