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

• URL: http://arxiv.org/abs/2511.17856v1
• Date: Sat, 22 Nov 2025 00:51:30 GMT
• Title: Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits
• Authors: Joshua Nevin,
• Abstract summary: Gate-teleportation-based protocol for computational indistinguishability obfuscation of quantum circuits developed in 2021.<n>In particular, we show that, for Clifford+T circuits of T-depth $O(log(n))$, deciding ENIC is NP-hard.<n>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.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• 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 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.

Related papers

• Exact Quantum Circuit Optimization is co-NQP-hard [4.554892610576937]
  We consider the natural problem of, given a circuit $C$, computing an equivalent circuit $C'$ that minimizes a quantum resource type.<n>We show that, when $C$ is expressed over any gate set that can implement the H and TOF gates exactly, each of the above optimization problems is hard for $textco-NQP$.
  arXiv  Detail & Related papers  (2025-10-18T09:31:23Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
  We use global interactions, such as the Global Molmer-Sorensen gate present in ion trap hardware, to optimize and synthesize quantum circuits.<n>The algorithm is based on the ZX-calculus and uses a specialized circuit extraction routine that groups entangling gates into Global MolmerSorensen gates.<n>We benchmark the algorithm in a variety of circuits, and show how it improves their performance under state-of-the-art hardware considerations.
  arXiv  Detail & Related papers  (2025-07-28T10:25:31Z)
• Implementation and readout of maximally entangled two-qubit gates quantum circuits in a superconducting quantum processor [32.40607221598716]
  In a transmon-based 5-qubit superconducting quantum processor, we compared the performance of quantum circuits involving an increasing level of complexity.<n>Here we report the results obtained from the analysis of the outputs of quantum circuits using two readout paradigms.<n>The first method is suitable for single-qubit circuits, while the second is essential for accurately interpreting the outputs of circuits involving two-qubit gates.
  arXiv  Detail & Related papers  (2025-03-31T16:20:56Z)
• Optimising quantum circuits is generally hard [0.0]
  We find that many gate optimisation problems for approximately universal quantum circuits are NP-hard. We show that for any non-Clifford gate $G$ it is NP-hard to optimise the $G$-count over the Clifford+$G$ gate set.
  arXiv  Detail & Related papers  (2023-09-12T09:35:23Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• Single-shot error mitigation by coherent Pauli checks [6.992823294269743]
  We show how to generate samples from the output distribution of a quantum circuit without full-blown error correction. Our approach is based on Coherent Pauli Checks that detect errors in a Clifford circuit.
  arXiv  Detail & Related papers  (2022-12-07T20:03:07Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$ [1.14219428942199]
  We show that proper learning of Clifford circuits is hard for classical learners unless $textsfRP = textsfNP$. We also show that an efficient proper quantum learner exists if and only if $textsfNP subseteq textsfRQP$.
  arXiv  Detail & Related papers  (2022-04-13T21:07:53Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Efficient quantum programming using EASE gates on a trapped-ion quantum computer [1.9610635155358869]
  We focus on the recently invented efficient, arbitrary, simultaneously entangling (EASE) gates, available on a trapped-ion quantum computer. We show an $n$-qubit Clifford circuit can be implemented using $6log(n)$ EASE gates, an $n$-qubit multiply-controlled NOT gate can be implemented using $3n/2$ EASE gates, and an $n$-qubit permutation can be implemented using six EASE gates.
  arXiv  Detail & Related papers  (2021-07-15T20:03:23Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.