黑匣子量子电路背后的原理是什么？

Question

我读过一些关于量子计算机和量子电路的材料。一些已知的算法(西蒙算法，周期查找算法，格罗弗算法，…算法)有以下表格：

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

等等..。与经典电路的关系是什么？经典问题是指满足某些属性的未知输入，该输入表示来自外部的状态(用户操作、文件系统、数据库、服务器等)。如果这种状态是由另一个电路/算法生成的，则逻辑应用于之前的输入。最后，我们没有推理未知的电路，而是关于未知的输入。电路(算法/函数)是已知/选择的元件。

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

现在，这并不能真正解释你如何将一堆先验未知的经典输入位(我相信你的键盘将来会继续产生，除非薛定谔的猫坐在上面)转换成一个“黑匣子量子电路”，转换成0…。0>变成了要被逆转的东西。例如，Grover的算法对于与函数f：{0，1}^n -> {0，1}对应的量子电路，对于单个未知输入产生1，提出了一种确定此输入的有效方法。好的!但是，首先，你必须如何以及为什么要从这样一个回路开始呢？

Answer 1

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

这是有用的，因为它更容易制造一个电路来检测一个解决方案，而不是实际找到一个解决方案。然后Grover的算法将我们的检测器电路扩展为一个求解电路：

​

​

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的算法也做了同样的事情，但是二次速度更快，并且必须将识别器实现为可逆电路。