# 背景
假设读者知道量子计算的基本背景。具体来说,读者应该熟悉以下几个概念:
概念 | 简介 |
---|---|
量子位的状态 | |
基 态 | 非叠加态,像是 |
张量积 | 用于表示由多个量子位组成的状态,例如 |
纠缠态 | 不能写成两个状态的张量积的态,例如 |
测量 | 测量态 会产生几率为 的 (我们不会将结果归一化)。 |
将经典计算提升为量子输入 | 通过将(么正)算符 作用于输入态 ,可以使任意函数 可逆(从而在量子计算机上实现)。 |
不可克隆定理 | 我们不能在物理上实现形式 的操作 |
# 基本特性
# 变量赋值
以下代码片段将哈达玛变换 H
应用于量子位 x
,并将结果赋值给 y
。
y := H(x); |
将此代码片段编译为线路会产生以下结果:
在这里,我们将 H
中的导线命名为 x
,结果导线命名为 y
。应用 H
之前的一种可能状态是 ,其中下标 x
表示变量 x
存储 0
。然后,线路 y := H(x)
将导致状态 。
为了强调 H
的结果仍然引用相同的量子位 x
,我们可以这样写:
x := H(x); |
此行将输出值重新赋值给原变量 x
。
# 条件语句
以下代码段执行哈达玛变换的受控应用程序。
if x { // 由 x 控制, | |
y := H(x); // 将 H 应用于 y | |
} |
将此代码片段编译为线路会产生以下结果:
# Silq 中的 Grover 算法
我们说明了 Silq 及其对 Grover 算法的好处,Grover 算法是一种广为人知的量子搜索算法。对于给定的函数 ,从 n 位整数到布尔值,它找出 的输入 。我们只讨论 是唯一的情况,例如。其中 代表所有 。
我们首先展示其实现,然后介绍其主要功能。
# 与线路的比较
对于熟悉量子线路的读者,接下来我们将展示 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
函数的一个很好的例子是位翻转门X
,它将 映射到 。
# Qfree 函数的常量参数
请注意,虽然 X
的类型是 qfree
,但它不保留它的参数,即它消耗它的输入。相反, f
的参数被注释为 const
,这表明 f
保留它。
具体地说,考虑态 ,其中 捕获态的其余部分(可能是纠缠的)。然后,在该态下运行 y := f(x)
,其中 f
是 qfree
的,得到 。生成态保留原始的求和表达式,并使用附加值 对其进行扩充。
未注释为 const
的函数参数在调用函数后不可访问,也就是说,函数会使用它们。例如, groverDiff
使用其参数 (请参见上面代码中右上角的框)。因此,第 8 行中的调用使用 cand
,对其进行转换,并将结果写入同名的 cand
新变量。类似地,第 10 行中的 measure
通过测量消耗 cand
。
# 输入态
第 1 行之后的系统状态为 ,其中 和 表示变量的值。接下来,第 2 行初始化变量 nIterations
,产生状态 。
# 叠加态
第 3-4 行导致状态 ,其中 cand
保持 中所有 n 位整数的相同叠加态。为此,第 4 行通过对 cand
的第 i 位应用哈达玛变换 H
来更新它。
# 循环
第 6 行中的循环执行 nIterations
次,这是可能的,因为后者是经典的。每次循环迭代都会增加 系数,从而增加最终测量 的概率(第 10 行)。我们现在讨论第一次循环迭代()。它从引入变量 k
的状态 开始。为方便起见,它还将叠加拆分为 和所有其他值。
# 条件语句
如果第 7 行的 f(cand)
返回真,执行 phase(π)
。当 phase(π)
翻转系数的符号时,第 7 行 将系数从 更改为 。
在前面显示的电路中,我们通过(i)使用 计算 f(cand)
来物理地实现这一点,(ii)使用 门 phase(π)
,以及(iii)使用 取消计算 f(cand)
。取消计算 f(cand)
非常关键,我们稍后将简短讨论。
# Grover 扩散算符
第 8 行完成了对我们示例的解释,将 Grover 的扩散算符应用于 cand
。 GroverDiff
增加解 的系数,得到 \norm{\gamma_{w^\star}}^+}>\norm{\frac{1}{\sqrt{2^n}}},降低非解 的系数,得到 。在一次循环迭代之后,这将导致状态 。循环的重复,第 6-9 行,进一步增加 的系数,直到它大约为 。因此,在第 10 行测量 cand
返回 的概率很高。
# 非计算
# 非计算的陷阱
# 自动非计算
# 防止错误
# 无效测量
隐含测量
条件性测量
反向测量
# 使用消耗的变量
# 不可能发生的非计算
不是常量
不是 Qfree