# 背景

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

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

# 基本特性

# 变量赋值

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

y := H(x);

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

在这里,我们将 H 中的导线命名为 x ,结果导线命名为 y 。应用 H 之前的一种可能状态是 0x\ket{0}_\texttt{x} ,其中下标 x 表示变量 x 存储 0 。然后,线路 y := H(x) 将导致状态 12n(0y+1y)\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:{2n1,...,2n11}{0,1}f \colon\{-2^{n-1},...,2^{n-1}-1\}\to\{0,1\} ,从 n 位整数到布尔值,它找出 f(w)=1f(w^\star)=1 的输入 ww^\star 。我们只讨论 ww^\star 是唯一的情况,例如。其中 f(v)=0f(v)=0 代表所有 vwv \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 ,它将 v=01γvv\displaystyle\sum_{v=0}^1\gamma_v\ket{v} 映射到 v=01γv1v\displaystyle\sum_{v=0}^1\gamma_v\ket{1-v}

# Qfree 函数的常量参数

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

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

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

# 输入态

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

# 叠加态

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

# 循环

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

# 条件语句

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

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

# Grover 扩散算符

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

# 非计算

ψ7,0=ψ2(vw12nvcand0f(cand)12nwcand1f(cand))0k.\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}.

ψ7,0,0=ψ2vw12nvcand0korψ7,0,1=ψ212nwcand0k.\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]


  1. Silq - Overview of Key Concepts ↩︎