0

我读过一些关于量子计算机和量子电路的材料。一些已知的算法（Simon 算法、周期查找算法、Grover 算法……）具有以下形式：

假设我有一个未知的经典函数 f: {0,1}^n -> {0, 1}^m 满足一定数量的语句。我可以将（未知）量子电路 U_f 与它相关联并插入 |0.. 0> 输入状态。现在让我们定义电路 X 并显示当附加到 U_f 时，可以测量全局输出以提取有关 f 的一些信息。

等一下……与经典电路有什么关系？经典问题是指满足某些属性的未知输入，该输入表示来自外部的状态（用户操作、文件系统、数据库、服务器等）。如果此状态是由另一个电路/算法生成的，则逻辑适用于之前的输入。最后，我们不是对未知电路进行推理，而是对未知输入进行推理。电路（算法/功能）是已知/选择的组件。

在这里，我意识到通用名称“电路”在某种程度上具有误导性。在经典世界中，门输入可以被认为是与输出共存的值。但量子门似乎需要时间解释：输入和输出代表相同量子位的时间演化。

现在这并不能真正解释你如何将一组给定的先验未知经典输入位（我相信你的键盘在未来会继续生成，除非薛定谔的猫坐在上面）变成“黑匣子量子电路”将 |0…0> 转换为要反转的东西。例如，格罗弗的算法提出，对于对应于函数 f: {0, 1}^n -> {0, 1} 的量子电路，对于单个未知输入产生 1，这是一种确定该输入的有效方法。好的！但是，您首先要如何以及为什么要从这样的电路开始呢？

4

1 回答 1

0

在实践中，“未知功能黑匣子”只是一个检查其输入是否符合某些标准或是否是问题解决方案的电路。

这很有用，因为制作检测解决方案的电路比实际找到解决方案更容易。然后，格罗弗的算法将我们的检测器电路扩充为求解器电路：

格罗弗搜索

Grover 算法的经典等价物是这样的蛮力搜索函数：

def bruteForceSearch(min, max, predicate):
    for i in min..max:
        if predicate(i):
            return i
    return none

你会像这样使用它：

let mersennePrimeWithFiveDigitExponent = bruteForceSearch(
     10000,
     99999,
     i => isMersennePrime(2**i - 1))

请注意蛮力搜索如何将我们关于如何识别某物的知识转化为寻找某物的机制。Grover 的算法做同样的事情，但速度要快两倍，并且需要注意的是识别器必须实现为可逆电路。

于 2016-06-02T20:04:54.483 回答