Silq 关键内容预览

AI 正在绞尽脑汁想思路 ING···

AI 摘要

DeepSeek & Kimi

§ 背景

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

概念	简介
量子位(qubit)的状态	$\varphi=\gamma_0\ket{0}+\gamma_1\ket{1}\quad\gamma_0,\gamma_1\in\mathbb{C}\,$
基(basis)态(states)	非叠加态，像是 $\ket{0},\;\ket{1}\,$
张量(Tensor)积(product)	用于表示由多个量子位组成的状态，例如 $\ket{0} \otimes \ket{0} = \ket{0}\ket{0}\,$
纠缠(Entangled)态(states)	不能写成两个状态的张量积的态，例如 $\frac{1}{\sqrt{2}}\ket{0}\ket{0}+\frac{1}{\sqrt{2}}\ket{1}\ket{1}\,$
测量(Measurement)	测量态 $\varphi=\displaystyle\sum_{b=0}^1\gamma_b\ket{b}$ 会产生几率为 $\norm{\gamma_b}^2$ 的 $\gamma_b\ket{b}$ （我们不会将结果归一化(normalization)）。
将经典计算提升为量子输入	通过将（么正）算符 $U_f\ket{a}\ket{b}\mapsto\ket{a}\ket{b\oplus f(a)}$ 作用于输入态 $\ket{a}\ket{0}$ ，可以使任意函数 $f\colon A\to B$ 可逆（从而在量子计算机上实现）。
不可克隆(No-cloning)定理(theorem)	我们不能在物理上实现形式 $\varphi\mapsto\varphi\otimes\varphi$ 的操作

§ 基本特性

§ 变量赋值

以下代码片段将哈达玛(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}.$

§ 背景