EXACT NON-IDENTITY CHECK IS NQP-COMPLETE
Yu Tanaka · International Journal of Quantum Information · 2010
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.