Detecting mixed-unitary quantum channels is NP-hard
Detecting mixed-unitary quantum channels is NP-hard
复制标题
检测混合酉量子通道是 NP 困难的
作者：
Colin Do;John Watrous
如果一个量子信道可以表示为幺正信道的凸组合，则称之为混合幺正信道。我们证明了，给定量子信道Φ的Choi表示，确定Φ是否是混合幺正信道对于多项式时间图灵约化是NP困难的。即使假设Φ不在混合酉通道边界的逆多项式距离内（在Φ作用的空间的维度上），该硬度结果也成立。
A quantum channel is said to be amixed-unitarychannel if it can be expressed as a convex combination of unitary channels. We prove that, given the Choi representation of a quantum channelΦ, it is NP-hard with respect to polynomial-time Turing reductions to determine whether or notΦis a mixed-unitary channel. This hardness result holds even under the assumption thatΦis not within an inverse-polynomial distance (in the dimension of the space upon whichΦacts) of the boundary of the mixed-unitary channels.