"Identity check" is QMA-complete
"Identity check" is QMA-complete
复制标题
“身份检查”已完成 QMA
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
T. Beth
中科院分区：
文献类型：
--
作者：
D. Janzing;P. Wocjan;T. Beth
我们定义了“身份验证”问题：给定一个量子电路的经典描述，确定它是否几乎等同于该身份。明确地说，任务是确定相应的酉性是否接近单位矩阵关于算子范数的复数倍。我们证明了这个问题是QMA-完全的。这个问题的一个推广是“等价检验”：给出两个量子电路的描述和一个公共不变子空间的描述，判断电路对该子空间的限制是否几乎重合。我们证明了QMA中的等价性检验也是QMA-完全的。
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.