酉矩阵如何成为置换?- 量子模式匹配

How is a Unitary matrix a permutation?- Quantum pattern matching

我正在阅读有关量子模式匹配的 paper,这里它讨论了一个酉矩阵 U,它表示将状态振幅翻转为计算基础上的排列的神谕。见第3页右侧第四段下等式(7)。

谁能给我解释一下这是什么意思?

由等式(7)定义的幺正是一个置换,因为它将每个计算基础状态发送到另一个计算基础状态(与计算基础状态的某种叠加相反)。在矩阵形式中,U 的每一列都用零填充,除了一个条目等于 1(对于可逆性的行也是如此)。也就是说,它是一个permutation matrix.

具体来说,U发送计算基础状态|x0, x1, ..., x n⟩ 到计算基础状态 |y, x1, ..., xn⟩ 其中 y = f( x1, ..., xn) 如果 x0 = 0 且 y = 1- f(x1, ..., xn) 如果 x0 = 1。见等式(6).


请注意,U 不会翻转任何状态的相位。但是,如果我们在状态

上与 U 一起行动

|0, x1, ..., xn⟩ - |1, x1, ..., xn

(我们忽略归一化)那么结果是

(-1)^f(x1, ..., xn) (|0, x1, ..., xn⟩ - |1, x1, ..., xn⟩)

当且仅当 f(x1, ..., xn) = 1 时相位翻转。这是 phase kickback.

的一个例子