Simon算法详解

0.0 Intro

相关的算法：
Deutsh-Jozsa算法：
    第一个量子算法对经典算法取得指数级加速的算法
    美中不足在于只能确定函数是平衡的还是非平衡的，无法确定函数具体的内容，即无法直接解出函数
Bernstein-Vazirani算法：
    在Deutsh-Jozsa算法基础上进一步提出，能够直接解出算法本身
    同样存在问题，即没有实现指数级的加速

Simon算法 在上述两个算法的基础上更进一步，体现在两个方面
一方面，Simon算法可以在Simon问题中，直接解出目标函数
另一方面，Simon问题的经典解法是指数级复杂度，而Simon算法相较经典算法也是取得了指数级的加速。

1.1 Simon问题（Simon’s Problem）

现有一未知数，其作用域和值域都是n位的二进制数据： f : { 0 , 1 } n → { 0 , 1 } n f:\left \{ 0,1\right \}^{n} \to \left \{ 0,1\right \}^{n} f:{0,1}n→{0,1}n
该函数是单射或对称函数中的一种。当函数为对称时，有：$$x_1+x_2=s，f(x_1)=f(x_2)$$现需确定函数的属性，若属于对称函数需进一步确定 s

小贴士：

• 单射函数即作用域上每一个输入都有唯一输出的函数，常见的有实数域上所有的线性函数，例如f(x)=x、f(x)=lnx等都是单射函数
• 对称函数的性质在上面已经说明，其中s其实是x1和x2的对称轴，常见的对称函数即二次函数，例如f(x)=x^2，其对称轴s=0

1.2 Simon问题分析与经典解法的思路

1.2.1 Simon问题分析

需要注意的是，Simon问题中提到的值域和作用域始终都是n位二进制数，进行的加法严格意义上说是模二加法， 在模二加法中两个二进制数相加为0即表示这两个二进制数是相等的，因此可对Simon问题进行如下简化：

• 对于单射函数，显然有：在x1=x2时，$$x_1+x_2=0，f(x_1)=f(x_2)$$因此，s=0即为在单射函数情况下的解
• 对于对称函数，除了s=0这一个解之外，显然还有另一个非平凡解，即为对称函数对称轴的位置

小贴士

• 平凡解就是显而易见的解、没有讨论的必要但是为了结果的完整性仍需要考虑的结果，比如Ax=0中的零解,即x=0，即为平凡解
• 非平凡解（nontrivial solution）是齐次方程或齐次方程组的非零解。

1.2.2 Simon问题的经典解法（暴力解法）

可以通过将作用域取值不断带入进行验证的方法进行求解，考虑到单射函数与对称函数的区别，不必将整个作用域带入，只需要带入作用域的一半+1次即可完成验证。
作用域是n位二进制数，因此需要进行验证的次数为：$$2^{n-1}+1$$
这里解释一下验证一半作用域后额外再验证一次的原因。最坏的情况下，验证一半作用域后会发现每一个输出都是唯一的，那么就需要额外再进行一次，将额外的一次结果与前面一半作用域产生的值进行比对：

• 如果仍然是新的唯一输出，则表明这是一个单射函数；
• 如果能与之前某个输出值匹配，则表明这是一个对称函数，该输出对应的输入值和这额外的一次输入值就可以确定对称轴的位置。

因而，Simon问题经典解法的时间复杂度是$$O(2^n)$$

2.1 Simon算法详解

2024.1.15 待续…