Exact Non-identity check is NQP-complete

2009/03/04 by Yu Tanaka, Tanaka, Yu · 3 citations
Computer Science · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Numerical Methods and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.0903.0675

openalex publication_date 2009/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We define a problem "exact non-identity check": Given a classical description of a quantum circuit with an ancilla system, determine whether it is strictly equivalent to the identity or not. We show that this problem is NQP-complete. In a sense of the strict equivalence condition, this problem is different from a QMA-complete problem, non-identity check defined by D. Janzing etc. As corollaries, it is derived that exact equivalence check is also NQP-complete and that it is hard to minimize quantum resources of a given quantum gate array without changing an implemented unitary operation.

Cited by

• Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits
• Exact Quantum Circuit Optimization is co-NQP-hard
• Q-Sylvan: A Parallel Decision Diagram Package for Quantum Computing

Related

• Identity check is QMA-complete
• Non-Identity Check Remains QMA-Complete for Short Circuits
• Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits
• Two QCMA-complete problems
• Towards Equivalence Checking of Classical Circuits Using Quantum Computing