15、量子算法：从 Deutsch - Jozsa 到 Simon 算法的探索

量子算法：从 Deutsch - Jozsa 到 Simon 算法的探索

1. 克罗内克积与哈达玛矩阵

在量子算法中，矩阵的克罗内克积起着重要作用。当我们考虑哈达玛矩阵 (H) 的多次张量积 (H^{\otimes n}) 时，随着 (n) 的增加，矩阵规模会迅速增大。不过，存在一个递归公式：
[H^{\otimes n} \otimes H^{\otimes n} \otimes H^{\otimes n} \otimes H^{\otimes n} \otimes H^{\otimes n} =
\begin{bmatrix}
-1 & 1 & 1 & 1 \
1 & -1 & 1 & 1 \
1 & 1 & -1 & 1 \
1 & 1 & 1 & -1
\end{bmatrix}]
这使得我们能够快速计算这些矩阵。这些描述张量积作用方式的矩阵乘积被称为克罗内克积。对于 Simon 算法，我们需要详细研究这些矩阵；而对于下一个算法，关键的一点是这些矩阵的第一行元素都相等，对于 (H^{\otimes n})，它们都等于 (\frac{1}{2^n})。

2. Deutsch - Jozsa 算法

2.1 问题描述

Deutsch 算法研究的是单变量函数，需要判断给定的函数是常量函数还是平衡函数。Deutsch - Jozsa 问题是这一问题的推广，现在我们面对的是 (n) 变量函数，每个变量的输入可以是 0 或 1，输出也为 0 或 1。函数要么是常量函数（所有输入都映射到