跳到主要内容

Simon 算法

阐述

Simon 问题

给定一个 f:ΣnΣnf:\Sigma^n\to\Sigma^n,它是二对一的且存在一个 cΣnc\in\Sigma^n,使得 f(x)=f(xc)f(x)=f(x\oplus c)。找出 cc

Simon 算法

构造一个黑箱 OfO_f 使得

Ofxz=xzf(x)O_{f}|x\rangle|z\rangle=|x\rangle|z \oplus f(x)\rangle

准备两组长度为 nn 的寄存器,依次作用 HnH^{\otimes n}OfO_fHnH^{\otimes n},然后测量第一组寄存器。此时系统状态为

k=02n1(12nj=02n1(1)jkf(j))k\sum_{k=0}^{2^{n}-1}\left(\frac{1}{2^{n}}\sum_{j=0}^{2^{n}-1}(-1)^{j \cdot k}|f(j)\rangle\right)|k\rangle

括号内的振幅不为 0 当且仅当 ck=0c\cdot k=0,因此测量得到的结果满足这一条件。由于共有 2n12^{n-1} 个正交向量,进行 n1n-1 次测量中,第 ii 次取得的向量与此前的线性相关的概率是 2in2^{i-n},所以每次找到合适的向量的期望次数小于 2。总体运算时间 O(n2)O(n^2)

Simon 算法是一个量子反作用的例子。

实例

性质

相关内容

参考文献