Simon 问题
给定一个 f:Σn→Σn,它是二对一的且存在一个 c∈Σn,使得 f(x)=f(x⊕c)。找出 c。
Simon 算法
构造一个黑箱 Of 使得
Of∣x⟩∣z⟩=∣x⟩∣z⊕f(x)⟩
准备两组长度为 n 的寄存器,依次作用 H⊗n、Of 和 H⊗n,然后测量第一组寄存器。此时系统状态为
k=0∑2n−1(2n1j=0∑2n−1(−1)j⋅k∣f(j)⟩)∣k⟩
括号内的振幅不为 0 当且仅当 c⋅k=0,因此测量得到的结果满足这一条件。由于共有 2n−1 个正交向量,进行 n−1 次测量中,第 i 次取得的向量与此前的线性相关的概率是 2i−n,所以每次找到合适的向量的期望次数小于 2。总体运算时间 O(n2)。
Simon 算法是一个量子反作用的例子。
相关内容
参考文献