Abstract
The Non-Identity Check problem asks whether a given quantum circuit is far away from the identity or not. It is well known that this problem is QMA-Complete. 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 $\Omega(\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.
Introduction
In computational complexity, the "Non-Identity Check" (NIC) problem is a fundamental task: given a quantum circuit $C$, determine if it is close to the identity operator $I$ or significantly far from it. While the classical equivalent—circuit identity testing—is efficiently solvable (in BPP), the quantum version is QMA-complete, placing it among the hardest problems verifiable by a quantum computer.
This research investigates whether this complexity persists when the circuit's depth is severely restricted. Shallow circuits are of particular interest in the current Noisy Intermediate-Scale Quantum (NISQ) era, as they are less susceptible to decoherence. The authors demonstrate that even with minimal depth, the NIC problem retains its full computational hardness.
Methodology
The authors establish their results through a reduction from the 1-D Local Hamiltonian problem, which is known to be QMA-complete. The reduction involves several key steps:
1. Hamiltonian Mapping and Parallelization
A 1-D Hamiltonian $H = \sum H_i$ is mapped to a unitary operation $U = e^{iHt}$. To minimize circuit depth, the authors exploit the 1-D spatial structure of the Hamiltonian. By partitioning the terms into "odd" and "even" groups, they ensure that terms within each group act on disjoint sets of particles and thus commute.
This decomposition allows all odd terms to be executed in a single parallel layer, followed by a second layer for all even terms.
2. Trotterization and Precision Analysis
Using a first-order Trotter expansion, the evolution is approximated as $U \approx e^{iH_{even}t} e^{iH_{odd}t}$. This approximation results in a constant-depth circuit. However, the validity of the reduction depends on the precision of the gates. The authors analyze how the eigenvalues of the Hamiltonian map to phases on the complex unit circle to ensure that the "far from identity" condition is preserved.
For implementations using discrete, universal gate sets (like Hadamard and T-gates), the Solovay-Kitaev theorem is employed. This analysis shows that while constant depth is achievable with high-precision gates ($\Omega(\log n)$ bits), polylogarithmic depth is required to maintain QMA-completeness when using standard finite gate sets.
Key Results
- Theorem 1: The Non-Identity Check for constant depth quantum circuits is QMA-complete, provided each gate is described with at least $\Omega(\log n)$ bits of precision.
- Corollary 1: For any arbitrary universal gate set, the problem remains QMA-complete for circuits of polylogarithmic depth.
- Corollary 2: There exists a specific universal gate set for which the problem is QMA-complete at only logarithmic depth.
Discussion and Future Work
The study confirms that circuit depth is not the primary driver of complexity in the NIC problem; a few layers of gates can encode problems as difficult as any in QMA.
One remaining open question is whether the problem remains QMA-complete for constant-depth circuits using only a fixed, finite universal gate set without the high-precision assumption. Additionally, while this work focuses on unitary circuits, the authors suggest that distinguishing between mixed-state computations—which are more representative of noisy hardware—is likely even harder, potentially reaching QIP-completeness.
Summary updated