Identity check is QMA-complete

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.

9 pages

References in corpus (1)

• 3-Local Hamiltonian is QMA-complete

Cited by in corpus (15)

• Automated optimization of large quantum circuits with continuous parameters
• Quantum linear systems algorithms: a primer
• Merlin-Arthur Games and Stoquastic Complexity
• Exact and practical pattern matching for quantum circuit optimization
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Consistency of Local Density Matrices is QMA-complete
• Commutative version of the k-local Hamiltonian problem and common eigenspace problem
• Non-Identity Check Remains QMA-Complete for Short Circuits
• CertiQ: A Mostly-automated Verification of a Realistic Quantum Compiler
• Computational Distinguishability of Quantum Channels
• Testing quantum circuits and detecting insecure encryption
• Testing non-isometry is QMA-complete
• Two QCMA-complete problems
• On the Complexity of Quantum Languages