黑盒量子电路背后的基本原理是什么？

Question

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

Suppose I have an unknown classical function f: {0,1}^n -> {0, 1}^m satisfying a certain number of statements. I can associate the (unknown) quantum circuit U_f to it and plug the |0.. 0> input state. Now let us define circuit X and show that when appended to U_f, the global output can be measured to extract some information about f.

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

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

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

Answer 1

在实践中，'unknown function black box' 只是一个电路，用于检查其输入是否满足某些条件或者是问题的解决方案。

这很有用，因为制作检测解决方案的电路比实际找到解决方案更容易。然后 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 的算法做同样的事情，但二次方更快，并且需要注意的是识别器必须作为可逆电路来实现。

黑盒量子电路背后的基本原理是什么？

What is the rationale behind black-box quantum circuit?

quantum-computing