相关的算法：
Deutsh-Jozsa算法：
????第一个量子算法对经典算法取得指数级加速的算法
????美中不足在于只能确定函数是平衡的还是非平衡的，无法确定函数具体的内容，即无法直接解出函数
Bernstein-Vazirani算法：
????在Deutsh-Jozsa算法基础上进一步提出，能够直接解出算法本身
????同样存在问题，即没有实现指数级的加速
Simon算法 在上述两个算法的基础上更进一步，体现在两个方面
一方面，Simon算法可以在Simon问题中，直接解出目标函数
另一方面，Simon问题的经典解法是指数级复杂度，而Simon算法相较经典算法也是取得了指数级的加速。
现有一未知数，其作用域和值域都是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
)
x_{1}+ x_{2}=s，f(x_{1})=f(x_{2})
x1?+x2?=s，f(x1?)=f(x2?)现需确定函数的属性，若属于对称函数需进一步确定 s
小贴士：
- 单射函数即作用域上每一个输入都有唯一输出的函数，常见的有实数域上所有的线性函数，例如f(x)=x、f(x)=lnx等都是单射函数
- 对称函数的性质在上面已经说明，其中s其实是x1和x2的对称轴，常见的对称函数即二次函数，例如f(x)=x^2，其对称轴s=0
需要注意的是，Simon问题中提到的值域和作用域始终都是n位二进制数，进行的加法严格意义上说是模二加法， 在模二加法中两个二进制数相加为0即表示这两个二进制数是相等的，因此可对Simon问题进行如下简化：
小贴士
- 平凡解就是显而易见的解、没有讨论的必要但是为了结果的完整性仍需要考虑的结果，比如Ax=0中的零解,即x=0，即为平凡解
- 非平凡解（nontrivial solution）是齐次方程或齐次方程组的非零解。
可以通过将作用域取值不断带入进行验证的方法进行求解，考虑到单射函数与对称函数的区别，不必将整个作用域带入，只需要带入作用域的一半+1次即可完成验证。
作用域是n位二进制数，因此需要进行验证的次数为：
2
n
?
1
+
1
2^{n-1}+1
2n?1+1
这里解释一下验证一半作用域后额外再验证一次的原因。最坏的情况下，验证一半作用域后会发现每一个输出都是唯一的，那么就需要额外再进行一次，将额外的一次结果与前面一半作用域产生的值进行比对：
因而，Simon问题经典解法的时间复杂度是 O ( 2 n ) O(2^n) O(2n)
2024.1.15 待续…