Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0305050

Identity check is QMA-complete

Dominik Janzing, Paweł Wocjan, Thomas Beth

Published May 9, 2003• 32 citations
arXivHTMLPDF

Abstract

We define the problem identity check: Given a classical description of a quantum circuit, determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the corresponding unitary is close to a complex multiple of the identity matrix with respect to the operator norm. We show that this problem is QMA-complete. A generalization of this problem is equivalence check: Given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that equivalence check is also in QMA and hence QMA-complete.

DOI
10.48550/arxiv.quant-ph/0305050

Related papers

"NON-IDENTITY-CHECK" IS QMA-COMPLETE

Dominik Janzing, Paweł Wocjan, Thomas Beth

We describe a computational problem that is complete for the complexity class QMA, a quantum generalization of NP. It arises as a natural question in quantum computing and quantum physics. "Non-identity-check" is the following decision problem: Given a classical description of a quantum circuit (a sequence of elementary gates), determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the corresponding unitary is close to a complex multiple of the identity matrix with respect to the operator norm. We show that this problem is QMA-complete. A generalization of this problem is "non-equivalence check": given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that non-equivalence check is also in QMA and hence QMA-complete.

International Journal of Quantum Information•Sep 1, 2005•74 citations

Two QCMA-complete problems

Paweł Wocjan, Dominik Janzing, T. Beth

QMA and QCMA are possible quantum analogues of the complexity class NP. In QMA the proof is a quantum state and the verification is a quantum circuit. In contrast, in QCMA the proof is restricted to be a classical state. It is not known whether QMA strictly contains QCMA. Here we show that two known QMA-complete problems can be modified to QCMA-complete problems in a natural way: (1) Deciding whether a 3-local Hamiltonian has low energy states (with energy smaller than a given value) that can be prepared with at most k elementary gates is QCMA-complete, whereas it is QMA-complete when the restriction on the complexity of preparation is dropped. (2) Deciding whether a (classically described) quantum circuit does not act as the identity on all basis states is QCMA-complete. It is QMA-complete to decide whether it does not act on all states as the identity.

arXiv:quant-ph/0305090•Quantum Information and Computation•Nov 1, 2003•18 citations

EXACT NON-IDENTITY CHECK IS NQP-COMPLETE

Yu Tanaka

To understand quantum gate array complexity, we define a problem named exact non-identity check, which is a decision problem to determine whether a given classical description of a quantum circuit is strictly equivalent to the identity or not. We show that the computational complexity of this problem is non-deterministic quantum polynomial-time (NQP)-complete. As corollaries, it is derived that exact non-equivalence check of two given classical descriptions of quantum circuits is also NQP-complete and that minimizing the number of quantum gates for a given quantum circuit without changing the implemented unitary operation is NQP-hard.

arXiv:0903.0675•International Journal of Quantum Information•Aug 1, 2010•12 citations

Identity Check Problem for Shallow Quantum Circuits

Sergey B. Bravyi, Natalie Parham, Minh C. Tran

Checking whether two quantum circuits are approximately equivalent is a common task in quantum computing. We consider a closely related identity check problem: given a quantum circuit $U$, one has to estimate the diamond-norm distance between $U$ and the identity channel. We present a classical algorithm approximating the distance to the identity within a factor $α=D+1$ for shallow geometrically local $D$-dimensional circuits provided that the circuit is sufficiently close to the identity. The runtime of the algorithm scales linearly with the number of qubits for any constant circuit depth and spatial dimension. We also show that the operator-norm distance to the identity $\|U-I\|$ can be efficiently approximated within a factor $α=5$ for shallow 1D circuits and, under a certain technical condition, within a factor $α=2D+3$ for shallow $D$-dimensional circuits. A numerical implementation of the identity check algorithm is reported for 1D Trotter circuits with up to 100 qubits.

arXiv:2401.16525•Leibniz international proceedings in informatics•Jan 29, 2024•0 citations

Quantum Circuit Equivalence Checking: A Tractable Bridge From Unitary to Hybrid Circuits

Jérome Ricciardi, Sébastien Bardin, Christophe Chareton +1 more

Equivalence checking of hybrid quantum circuits is of primary importance, given that quantum circuit transformations are omnipresent along the quantum compiler chain. While some approaches exist for automating this task, most focus on the simple case of unitary circuits. At the same time, real quantum computing requires hybrid circuits equipped with measurement operators. Moreover, the few approaches targeting the hybrid case are limited to a restricted class of problems. We propose tackling the Quantum Hybrid Circuit Equivalence Checking problem through lifting unitary circuit verification using a transformation known as deferred measurement. We show that this approach alone significantly outperforms prior work, and that, with the addition of specific unitary-level techniques we call separation and projection, it can handle much larger classes of hybrid circuit equivalence problems. We have implemented and evaluated our method over standard circuit transformations such as teleportation, one-way measurement, or the IBM Qiskit compiler, demonstrating its promises. As a side finding, we have identified and reported several unexpected behaviours with the Qiskit compiler.

quant-pharXiv:2511.22523•Nov 28, 2025•1 citation

Non-Identity Check Remains QMA-Complete for Short Circuits

Zhengfeng Ji, Xiaodi Wu

The Non-Identity Check problem asks whether a given a quantum circuit is far away from the identity or not. It is well known that this problem is QMA-Complete \cite{JWB05}. In this note, it is shown that the Non-Identity Check problem remains QMA-Complete for circuits of short depth. Specifically, we prove that for constant depth quantum circuit in which each gate is given to at least $Ω(\log n)$ bits of precision, the Non-Identity Check problem is QMA-Complete. It also follows that the hardness of the problem remains for polylogarithmic depth circuit consisting of only gates from any universal gate set and for logarithmic depth circuit using some specific universal gate set.

arXiv:0906.5416•Jun 30, 2009•10 citations
We define the problem identity check: Given a classical description of a quantum circuit, determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the corresponding unitary is close to a complex multiple of the identity matrix with respect to the operator norm. We show that this problem is QMA-complete. A generalization of this problem is equivalence check: Given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that equivalence check is also in QMA and hence QMA-complete.
We describe a computational problem that is complete for the complexity class QMA, a quantum generalization of NP. It arises as a natural question in quantum computing and quantum physics. "Non-identity-check" is the following decision problem: Given a classical description of a quantum circuit (a sequence of elementary gates), determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the corresponding unitary is close to a complex multiple of the identity matrix with respect to the operator norm. We show that this problem is QMA-complete. A generalization of this problem is "non-equivalence check": given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that non-equivalence check is also in QMA and hence QMA-complete.
QMA and QCMA are possible quantum analogues of the complexity class NP. In QMA the proof is a quantum state and the verification is a quantum circuit. In contrast, in QCMA the proof is restricted to be a classical state. It is not known whether QMA strictly contains QCMA. Here we show that two known QMA-complete problems can be modified to QCMA-complete problems in a natural way: (1) Deciding whether a 3-local Hamiltonian has low energy states (with energy smaller than a given value) that can be prepared with at most k elementary gates is QCMA-complete, whereas it is QMA-complete when the restriction on the complexity of preparation is dropped. (2) Deciding whether a (classically described) quantum circuit does not act as the identity on all basis states is QCMA-complete. It is QMA-complete to decide whether it does not act on all states as the identity.
To understand quantum gate array complexity, we define a problem named exact non-identity check, which is a decision problem to determine whether a given classical description of a quantum circuit is strictly equivalent to the identity or not. We show that the computational complexity of this problem is non-deterministic quantum polynomial-time (NQP)-complete. As corollaries, it is derived that exact non-equivalence check of two given classical descriptions of quantum circuits is also NQP-complete and that minimizing the number of quantum gates for a given quantum circuit without changing the implemented unitary operation is NQP-hard.
Checking whether two quantum circuits are approximately equivalent is a common task in quantum computing. We consider a closely related identity check problem: given a quantum circuit UUU, one has to estimate the diamond-norm distance between UUU and the identity channel. We present a classical algorithm approximating the distance to the identity within a factor α=D+1α=D+1α=D+1 for shallow geometrically local DDD-dimensional circuits provided that the circuit is sufficiently close to the identity. The runtime of the algorithm scales linearly with the number of qubits for any constant circuit depth and spatial dimension. We also show that the operator-norm distance to the identity ∥U−I∥\|U-I\|∥U−I∥ can be efficiently approximated within a factor α=5α=5α=5 for shallow 1D circuits and, under a certain technical condition, within a factor α=2D+3α=2D+3α=2D+3 for shallow DDD-dimensional circuits. A numerical implementation of the identity check algorithm is reported for 1D Trotter circuits with up to 100 qubits.
Equivalence checking of hybrid quantum circuits is of primary importance, given that quantum circuit transformations are omnipresent along the quantum compiler chain. While some approaches exist for automating this task, most focus on the simple case of unitary circuits. At the same time, real quantum computing requires hybrid circuits equipped with measurement operators. Moreover, the few approaches targeting the hybrid case are limited to a restricted class of problems. We propose tackling the Quantum Hybrid Circuit Equivalence Checking problem through lifting unitary circuit verification using a transformation known as deferred measurement. We show that this approach alone significantly outperforms prior work, and that, with the addition of specific unitary-level techniques we call separation and projection, it can handle much larger classes of hybrid circuit equivalence problems. We have implemented and evaluated our method over standard circuit transformations such as teleportation, one-way measurement, or the IBM Qiskit compiler, demonstrating its promises. As a side finding, we have identified and reported several unexpected behaviours with the Qiskit compiler.
The Non-Identity Check problem asks whether a given a quantum circuit is far away from the identity or not. It is well known that this problem is QMA-Complete \cite{JWB05}. In this note, it is shown that the Non-Identity Check problem remains QMA-Complete for circuits of short depth. Specifically, we prove that for constant depth quantum circuit in which each gate is given to at least Ω(log⁡n)Ω(\log n)Ω(logn) bits of precision, the Non-Identity Check problem is QMA-Complete. It also follows that the hardness of the problem remains for polylogarithmic depth circuit consisting of only gates from any universal gate set and for logarithmic depth circuit using some specific universal gate set.