Silq 关键内容预览

# 背景

假设读者知道量子计算的基本背景。具体来说，读者应该熟悉以下几个概念：

# 基本特性

# 变量赋值

以下代码片段将哈达玛(Hadamard)变换 H 应用于量子位 x ，并将结果赋值给 y 。

y := H(x);

将此代码片段编译为线路会产生以下结果：

在这里，我们将 H 中的导线命名为 x ，结果导线命名为 y 。应用 H 之前的一种可能状态是 $\ket{0}_\texttt{x}$ ，其中下标 x 表示变量 x 存储 0 。然后，线路 y := H(x) 将导致状态 $\frac{1}{\sqrt{2^n}}\left(\ket{0}_\texttt{y}+\ket{1}_\texttt{y}\right)$ 。

为了强调 H 的结果仍然引用相同的量子位 x ，我们可以这样写：

x := H(x);

此行将输出值重新赋值给原变量 x 。

# 条件语句

以下代码段执行哈达玛变换的受控应用程序。

if x {          // 由 x 控制，

    y := H(x);  // 将 H 应用于 y

}

将此代码片段编译为线路会产生以下结果：

# Silq 中的 Grover 算法

我们说明了 Silq 及其对 Grover 算法的好处，Grover 算法是一种广为人知的量子搜索算法。对于给定的函数 $f \colon\{-2^{n-1},...,2^{n-1}-1\}\to\{0,1\}$ ，从 n 位整数到布尔值，它找出 $f(w^\star)=1$ 的输入 $w^\star$ 。我们只讨论 $w^\star$ 是唯一的情况，例如。其中 $f(v)=0$ 代表所有 $v \neq w^\star$ 。

我们首先展示其实现，然后介绍其主要功能。

# 与线路的比较

对于熟悉量子线路的读者，接下来我们将展示 Grover 算法在线路方面的可能实现。虽然它不遵循 Grover 算法的标准表示，但它实现了相同的行为。为避免符号混乱，线路的导线未命名。

# 泛型参数和经典类型

grover 函数的第一个参数是泛型参数 n ，用于将 f 的输入长度参数化。它的类型为 !ℕ ，表示任意大小的经典自然数。这里，注解 ! 表示 n 是经典已知的，即它处于基态（而非叠加态），我们可以经典地操纵它。

Silq 要求泛型参数是经典的，允许在参数化类型中使用它们。虽然 Silq 支持固定大小的量子整型 int[n] （包含 n 位整数）和 uint[n] （包含 n 位无符号整型）的量子值，但它不允许类型 ℤ （包含所有整数）或 ℕ （包含所有自然数）的量子值，因为后者需要动态长度表示。

注意，函数体也要求 n 是经典的。否则，我们无法在不测量迭代次数的情况下确定循环迭代次数，这将导致状态崩溃。此外，参数 f 也被注释为经典的。这使我们能够自由地使用 f ，即，就像经典计算机上的普通变量一样。具体地说，我们可以多次调用 f ，并将其从 Grover 末尾的上下文中悄悄删除。

# Qfree 函数

f 的类型被注释为 qfree ，这表明 f 既不引入也不破坏叠加态。具体地说，如果 f 将基态作为输入，则它将返回基态。 qfree 函数的一个很好的例子是位翻转(bit-flip)门(gate)X ，它将 $\displaystyle\sum_{v=0}^1\gamma_v\ket{v}$ 映射到 $\displaystyle\sum_{v=0}^1\gamma_v\ket{1-v}$。

# Qfree 函数的常量参数

请注意，虽然 X 的类型是 qfree ，但它不保留它的参数，即它消耗它的输入。相反， f 的参数被注释为 const ，这表明 f 保留它。

具体地说，考虑态 $\displaystyle\sum_v\gamma_v\varphi_v\ket{v}_\texttt{x}$，其中 $\varphi_v$ 捕获态的其余部分（可能是纠缠的）。然后，在该态下运行 y := f(x) ，其中 f 是 qfree 的，得到 $\displaystyle\sum_v\gamma_v\varphi_v\otimes\ket{v}_\texttt{x}\otimes\ket{f(v)}_\texttt{y}$。生成态保留原始的求和表达式，并使用附加值 $\ket{f(v)}_\texttt{y}$ 对其进行扩充。

未注释为 const 的函数参数在调用函数后不可访问，也就是说，函数会使用它们。例如， groverDiff 使用其参数 (请参见上面代码中右上角的框)。因此，第 8 行中的调用使用 cand ，对其进行转换，并将结果写入同名的 cand 新变量。类似地，第 10 行中的 measure 通过测量消耗 cand 。

# 输入态

第 1 行之后的系统状态为 $\psi_1$，其中 $f$ 和 $n$ 表示变量的值。接下来，第 2 行初始化变量 nIterations ，产生状态 $\psi_2$。

# 叠加态

第 3-4 行导致状态 $\psi_4$，其中 cand 保持 $\{-2^{n-1},\dots,2^{n-1}-1\}$ 中所有 n 位整数的相同叠加态。为此，第 4 行通过对 cand 的第 i 位应用哈达玛变换 H 来更新它。

# 循环

第 6 行中的循环执行 nIterations 次，这是可能的，因为后者是经典的。每次循环迭代都会增加 $\ket{w^\star}$ 系数，从而增加最终测量 $w^\star$ 的概率（第 10 行）。我们现在讨论第一次循环迭代（$k=0$）。它从引入变量 k 的状态 $\psi_{6,0}$ 开始。为方便起见，它还将叠加拆分为 $w^\star$ 和所有其他值。

# 条件语句

如果第 7 行的 f(cand) 返回真，执行 phase(π) 。当 phase(π) 翻转系数的符号时，第 7 行 $\ket{w^\star}$ 将系数从 $\frac{1}{\sqrt{2^n}}$ 更改为 $-\frac{1}{\sqrt{2^n}}$。

在前面显示的电路中，我们通过（i）使用 $U_f$ 计算 f(cand) 来物理地实现这一点，（ii）使用 $Z$ 门 phase(π) ，以及（iii）使用 $U_f^\dagger$ 取消计算 f(cand) 。取消计算 f(cand) 非常关键，我们稍后将简短讨论。

# Grover 扩散算符

第 8 行完成了对我们示例的解释，将 Grover 的扩散算符应用于 cand 。 GroverDiff 增加解 $w^\star$ 的系数，得到 \norm{\gamma_{w^\star}}^+}>\norm{\frac{1}{\sqrt{2^n}}}，降低非解 $v\neq w^\star$ 的系数，得到 $\norm{\gamma_v^-}\lt\norm{\frac{1}{\sqrt{2^n}}}$。在一次循环迭代之后，这将导致状态 $\psi_{8,0}$。循环的重复，第 6-9 行，进一步增加 $w^\star$ 的系数，直到它大约为 $1$。因此，在第 10 行测量 cand 返回 $w^\star$ 的概率很高。

# 非计算

$$\psi'_{7,0} = \psi_2 \otimes \Big( \sum_{v \neq w^\star} \facs \ket{v}_\texttt{cand}\ket{0}_{\underline{\texttt{f(cand)}}} - \facs \ket{w^\star}_\texttt{cand}\ket{1}_{\underline{\texttt{f(cand)}}} \Big) \otimes \ket{0}_\texttt{k}.$$

$$\psi'_{7,0,0} = \psi_2 \otimes \sum_{v \neq w^\star} \facs \ket{v}_\texttt{cand} \otimes \ket{0}_\texttt{k} \quad \text{or} \quad \psi'_{7,0,1} = \psi_2 \otimes \facs \ket{w^\star}_\texttt{cand} \otimes \ket{0}_\texttt{k}.$$

# 非计算的陷阱

# 自动非计算

# 防止错误

# 无效测量

1. 隐含测量

2. 条件性测量

3. 反向测量

# 使用消耗的变量

# 不可能发生的非计算

1. 不是常量

2. 不是 Qfree

# 参考资料 ^[1]