量子计算（二）
2.2量子门
古典计算门是布尔逻辑门，其操纵存储在位中的信息。 在量子计算中，这种栅极由矩阵表示，并且可以在Bloch球体上方被视为旋转。 该可视化表示量子门是单一运算符的事实，即它们保留量子状态的标准（即，U = U = i，其中U是表示量子门的线性操作员，U≠是其伴随）。 在古典计算中，一些门是“通用”。 例如，可以使用一些NAND门（每个输入函数“而不是A和B”）来实现两个输入A和B之间的所有可能的逻辑连接。 另一个通用门也不是。 在量子计算的上下文中，示出了（DivinCenzo 1995），两个Qubit栅极（即，转换两个QUBITS）足以实现任何量子电路，其意义上仅来自（一小组）和两个 - Qubit栅极可以近似于任意精度N个QUbits的任何酉变换。 Barenco et。 铝。 （1995）特别地显示，任何多个Qubit逻辑门可以从单Qubit门和两个qubit控制 - 不是（CNOT）门的组合以这种意义组成，这是根据其状态翻转或保留其“目标”输入位。“控制”输入位（具体地：在CNOT栅极中，目标时量子位的输出状态是类似于输入上的经典专用 - 或（XOR）门的操作的结果。 将它们与经典栅极区分开的量子门的一个一般特征是它们总是可逆：整体矩阵的倒数也是单一矩阵，因此量子栅极可以始终通过另一量子栅极反转。
cnot = [
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
]。
两条水平线; 上线在中间有一个填充的黑色圆圈; 在留下的左边，它被标记为ket（x），最右侧标记为ket（x）; 下线在中间有一个开放的圆圈; 在留下的左边它被标记为ket（y），右侧是标记的ket（x圈加y）; 它是从封闭的黑色圆圈的垂直线一直到打开圆圈的底部。
CNOT门
单一门操纵存储在“量子寄存器”-A量子系统中的信息 - 并且在这种义上的普通（单一）量子演进中可以被视为计算。 然而，为了读取该计算的结果，必须测量量子寄存器。 测量表示为非酉栅极，其“将”寄存器中的量子叠加倒在其术语之一上，其术语与该术语复杂系数相对应的概率。 通常这是关于计算基础描述的，但原则上可以在任何无限多种可能的正交基座中进行测量，所以给定的状态可以表达为基态的线性组合。 恰好发生的是，一些这样的测量比其他测量更难以实现。
2.3量子电路
量子电路类似于古典计算机电路，因为它们由逻辑线和栅极组成。 电线用于携带信息，而闸门操纵它（注意导线是抽象的，并且不一定对应于物理线;它们可以对应于物理粒子，例如，光子，从一个位置移动到空间中的一个位置，或甚至在空间中从一个位置移动到另一个位置）。 传统上，假设量子电路的输入是每个符号，每个贵族都初始化为计算基状态（通常为0°）。 然后以一些正式的基础测量电路的输出状态（通常是计算基础）。
在该范例中构建了第一个量子算法（即，Deutsch-Jozsa，Simon，Shor和Grover）。 今天存在额外的量子计算范式，其存在与许多有趣方式的电路模型不同。 然而，到目前为止，它们都已被证明将计算方式相当于电路模型（见下文），意义上是可以通过这些新模型解决可以通过电路模型解决的任何计算问题，只有计算资源中的多项式开销。 我们注意到这里与各种古典计算模型进行了平行，其中也是任何其他“合理”这样的模型可以通过任何其他型号（用于讨论，参见Cuffaro 2018b，274）。
3量子算法
算法设计是一种高度复杂的任务，并且在量子计算中，巧妙地利用量子力学的特征，以使算法更有效地使任务更加复杂。 但在讨论量子算法设计的这一方面之前，让我们首先说服自己，Quantum计算机实际上可以模拟经典计算。 在某种意义上，鉴于量子力学的普遍性的信念，并且观察到在计算基础上对角线的任何量子计算，即涉及QUBits之间的干扰的观察，有效地是经典的。 然而，Quantum电路可用于模拟经典电路的演示并不简单（召回前者总是可逆的，而后者使用栅极通常是不可逆的）。 实际上，量子电路不能直接使用以模拟经典计算，但是仍然可以使用中间栅极模拟后者在量子计算机上模拟，即Toffoli门。 该通用古典门具有三个输入位和三个输出位。 两个输入位是控制位，不受门的动作影响。 第三输入位是如果将两个控制位设置为1，则会翻转目标位，否则单独留下。 该门是可逆的（其反向本身），但是通过将许多这样的栅极串联在一起，可以模拟任何经典电路。 因此，使用Toffoli Gate的量子版本（根据定义与计算基态类似于经典的Toffoli Gate），可以模拟虽然相当繁琐地，具有Quantum可逆型的不可逆的经典逻辑门。 因此，量子计算机能够执行经典确定性计算机可以执行的任何计算。
概率计算怎么样？ 令人惊讶的是，量子计算机还可以通过使用另一个着名的量子门来模拟这种计算，即Hadamard Gate，将输入状态的单个Qubit门|0⟩
|0⟩+ |1⟩
√
2
和输入状态|1¾到
|0⟩-|1⟩
√
2
。 测量这些输出状态的任何一个产量|0⟩或1¾，具有50/50概率，可用于模拟公平的硬币折腾。
h =
1
√
2
[
1 1
1 -1
]
x-y平面显示一个圆圈; 在正X轴上，圆点标有KET（0）; 在正y轴上，圆点标记为ket（1）; 虚线从起源到45度到右侧45度，向右下降45分; 上部虚线击中圆的点被标记为标记（KET（0）+ KET（1））/ SQRT（2）和较低虚线击中圆圈的点被标记为（KET（0） - KET（1））/ SQRT（2）。
Hadamard门
显然，如果量子算法只能模拟经典算法，则它们的兴趣将比当前的兴趣更受限制。 但是，虽然可能总是有一些抵抗量子加速的计算问题（参见Myers 1997和Linden＆Popescu 1998 [其他互联网资源]），但在社区中存在一般信心量子算法可能不仅模拟古典的社区，而且它们将实际上在某些情况下优于后者，有辩论（咖喱2018b;贺卡2007）对我们的抽象概念的疏忽和难损性的影响。
3.1量子电路基算法
3.1.1 oracles
第一个量子算法旨在解决基本上涉及使用“甲骨文”的问题，因此让我们首先解释这个术语。 Oracle是一个概念设备，证明了在计算问题的复杂性分析中，可以将其视为一种想象的魔法黑匣子（Arora＆Barak 2009,72-73; Aaronson 2013a，29ff。），就像Delphi的着名甲骨文一样，一个姿势（是或否）问题。 与那个古老的甲骨文不同，计算机科学中考虑的oracles总是在一步步骤中返回答案。 例如，我们可以想象一个Oracle来确定给定的布尔公式是否满足或否：给定针对特定命题公式的描述，Oracle输出 - 在单个时间步骤 - 一个单个位，指示是否存在满足该公式的真实值分配。 显然，这样的机器并没有真正存在 - sat（可满足性缩写）是一个NP完全的问题 - 但这不是点。 使用此类假想设备的目的是抽出某些“实施细节”，这是由于任何原因被视为不重要的原因，用于回答给定的复杂性问题。 例如，Simon的问题（Simon 1994）是确定在比特WISE Modulo-2的周期性的定期函数F的周期。 相对于西蒙的问题，我们判断F的内部复杂性是不重要的，因此通过想象我们有一个Oracle来在一个步骤中评估它来解决它。 然而，与这些概念设备一样有用，它们的有用性具有局限性。 要采取一个例子，相对于p = np，以及相对于哪个p≠np的oracell。 oracles不阐明这一点（以及许多其他）问题（见Fortnow 1994）。
3.1.2德意志的算法
Deutsch（1989）询问以下问题：假设我们有一个函数f，它可以是常数-i.e。 这样它为其可能的输入或平衡-1.E产生相同的输出值。 使得其可能输入的一半的输出与另一半的输出相反。 所考虑的特定示例是函数f：{0,1}→{0,1}，如果f（0）= f（1）和平衡，如果f（0）≠f（1）是恒定的。 典型地，这将需要两个函数的评估来判断它是一个或另一个功能。 量子机械地，我们可以在一次评估中回答这个问题。
显示了两个水平并行线; 在左边每个人都标有ket（0）; 从左到右，每个都有一个盒子上标有'x'，然后一个盒子标记为'h'; 继续左侧有一个单一的盒子，覆盖标有'U_F'的两条线; 此后，下线没有标签，上线具有标记为'H'的盒子，并以盒子标记的盒子，盒子由对角线交叉。
Deutsch算法的示意图
在最初准备（Mermin 2007，CH.2）中，状态在状态|0⟩|0⟩的第一和第二码，然后“翻转”两个Qubits（上面看到上图），使用“不是”门（即Pauli X变换）到|1⟩，然后对每个调查栅极进行对象。 然后一个人通过Oracle或'黑盒子发送这两个Qubits哪一个想象作为一个酉门，UF，代表我们希望确定的函数的函数，其中我们定义UF，以便它需要输入，如此x，y∈到| x，y⊕f（x）⟩，使得⊕是添加模2（即独家或）。 然后将第一个量子位送入另一个Hadamard门，并且算法（在测量之前）的最终输出是状态：
1
2
|1⟩（| f（0）⟩-|
f
（0）⟩）
每当F是常数的，和国家：
1
2
|0⟩（| f（0）⟩-|
f
（0）⟩）
每当F平衡，在哪里
f
（x）≡1⊕f（x）。 由于计算基态彼此正交，因此对第一个Qubit的单一测量足以检索对函数性质的原始问题的答案。 由于有两种可能的常量功能和来自F：{0,1}→{0,1}的两个可能的平衡功能，我们可以将算法表征为区分，仅使用一个Oracle呼叫，在两个量子剖钉之间而不是找出真实值分离自己，即，不确定哪个平衡或恒定函数f是（bup 2010）。
Deutsch问题的概括，称为Deutsch-jozsa问题（Deutsch＆Jozsa 1992），扩大了所考虑的函数类别，以包括所有功能f：{0,1} n→{0,1}，即仅考虑n = 1。 用于确定给定此类功能是否恒定或平衡的最佳确定性经典算法
2n
2
+1查询Oracle。 但是，在Quantum计算机中，我们可以使用一个Oracle呼叫来回答问题。 与Deutsch的算法一样，分析表明量子计算机仅需要一个呼叫Oracle来评估所讨论的函数的全局属性的原因，是计算机的输出状态是平衡和常数状态的叠加，使得平衡状态都躺在一个系统的Hilbert空间与恒定状态正交的子空间，因此可以与单个测量中的后者区分开（Bub 2006a）。
3.1.3西蒙的算法
假设我们在n位上的布尔函数f是2-to-1，即，它以每个n位整数x1为n-1位需要n比特的方式，其中有一个n位整数x2，f（x1）= f（x2）。 此外，该函数是定期的，即f（x1）= f（x2）如果x1 =x2⊕a，其中⊕指定位模数2添加，并且a是称为f的时段的n位非零编号。 西蒙的问题是找到给定的问题的问题。 相对于Oracle UF在单一的步骤中评估f，Simon的量子算法（Simon 1994）在许多Oracle调用中找到了几个Oracle呼叫，这些呼叫只能与n的长度线性增长，而最可知的经典算法需要一个呈指数级的Oracle呼叫。 Simon的算法在n = 2时缩短了Deutsch的算法，并且可以被视为后者的扩展，从这个意义上讲，在这两种情况下，函数的全局属性在不超过Oracle调用的（子）多项式的Oracle调用的那种情况下因为由于在最终测量之前的计算机的输出状态被分解为正交子空间，但只有一个包含问题的解决方案。 注意，德意志和西蒙算法之间的一个重要区别是前者肯定会产生解决方案，而后者仅产生概率非常接近的解决方案。对于这些基于第一量子电路的算法的逻辑分析，有更多的逻辑分析，请参见bub（2006A）和BUB（2010）。
3.1.4 Shor的算法
刚刚描述的算法虽然展示了量子在古典计算上的潜在优势，但尽管是显然不重要的计算问题。 此外，它们中的每一个的速度仅相对于它们各自的oracles。 因此，令人疑问是否在20世纪90年代对量子计算的研究会引起如此多的关注，因此可以利用西蒙的算法来解决更有趣和关键的问题，即要考虑，即在广泛的核心使用了RSA（RIVEST，Shamir，Adleman 1978）等加密协议。 Shor的算法将量子计算成量子力学中最令人兴奋的研究领域之一。
Shor的算法利用巧妙的数量理论参数，即通过确定函数f（x）= yxmodn的句点r，可以找到正整数n = pq的两个主要因素p，q的两个主要因素p，q函数f（x）= yxmodn，所述任何y <n与1以外的因素（Nielsen＆Chuang 2010，App.4）。 f（x）的时期取决于y和n.如果一个人知道它，如果r是偶数并且如果是
r
2
≠-1 mod n.这将是与概率大于的情况
1
2
对于随机选择的任何Y（否则，一个人选择另一个值并再次尝试）。 n的因素是y的最大常见分歧
r
2
±1和n，可以使用众所周知的欧几里德算法在多项式时间中找到。 换句话说，Shor的显着结果依赖于发现，考虑的问题减少了找到一定的周期函数的时段的问题。 该问题可以通过Simon的算法暗示的量子计算机可以有效地解决，该算法在比特WISE模2-2下通过在这里考虑的普通加法下的周期性功能下，这使得函数的周期性的更受限的函数。
尽管认为，但仅被认为只在NP中而不是NP-TEMENT（见Aaronson 2013A，64-66），因此避免的结果可以说是已知的量子速度最戏剧性的例子。 为了验证N是PRIME，采用LOG2N中多项式的步骤（自然数N的二进制编码需要log2n资源）。 但没有人知道如何在多项式时间中经典归因于Primes，以及我们为此问题的最佳经典算法是子指数。 因此，许多广泛使用的现代加密协议基于这些事实（Giblin 1993），并且发现量子计算机可以解决多项式时间中的定位的发现具有急剧效果。 因此，在可扩展架构上实现算法将具有经济，以及科学后果（Alléaume等，2014）。
3.1.5格洛弗的算法
在一个辉煌的秘密运作中，代理人13已经设法确保了有关拱门恶棍的下落的两个重要信息：秘密隐藏的电话号码，他打算开始开展Kaos的世界计划统治，并且数字是列出的事实（显然对Siegfried零件的监督）。 不幸的是，您和您的同事们在控制中没有其他信息。 只有使用此号码和电话目录，您可以找到Siegfried的藏身处吗？ 在理论计算机科学中，这项任务被称为非结构化搜索。 在最坏的情况下，如果目录中存在n个条目，则查找条目所需的计算资源将是n的线性。 格罗弗（1996）展示了如何使用仅使用计算资源的量子算法完成此任务
√
n
。 同意，这种加速比Shor更为谦虚，因为非结构化搜索属于P类，但与Shor的病例相反，在本文的经典复杂性仍然是未知的情况下，这里的量子算法的优势肯定是谦虚的。 这种二次加速也是该问题的最佳量子加速，由Bennett，Bernstein，Brassard，＆Vazirani（1997）证明了这一问题。
虽然GROVER的算法的目的通常被描述为“搜索数据库”，但将其描述为“反相函数”，这可能更准确。 粗略地说，如果我们有函数y = f（x），可以在量子计算机上评估，Grover的算法允许我们计算x给定y。 反转函数与搜索数据库有关，因为我们可以提出一个功能，该函数如果x匹配数据库中的所需条目，以及用于x的其他值的另一个值。 格罗弗的算法的应用深远（比较粘合Siegfried的世界统治计划。 例如，它可用于有效地确定对N项搜索问题的解决方案的数量，因此在对NP完全问题上进行详尽的搜索，并且大大减少解决它所需的计算资源。
3.2绝热算法
自从第一个量子算法发现以来已经过去了数十年，但到目前为止已经对求解量子电路解决NP完全问题的“圣杯”而产生的进展。 2000年，来自麻省理工学院和东北大学的一群物理学家（Farhi等，2000 [其他互联网资源]）提出了一种用于量子计算的新型范式，其与电路模型以几种有趣的方式不同。 他们的目标是尝试通过这个算法决定最着名的NP完整问题之一：可靠性。 根据绝热定理（参见，例如，弥赛亚1961）并给出某些特定条件，量子系统沿着它的最低能态状态保持为基位，沿着绝热转换，其中系统从初始变形Hamiltonian到最后一个汉密尔顿人（作为一个插图，想想从起居室到卧室的摇篮中搬到一个睡觉的婴儿。如果过渡慢慢地完成，如果宝宝是一个声音睡眠者，那么它将在整个过渡期间保持睡眠状态）。 本定理中最重要的条件是地面状态和下一个兴奋状态之间的能差（在我们的类比中，这种差距反映了婴儿的声音如何）。 与演化时间t成反比，这种间隙控制后者。 如果整个演化期间存在这种间隙（即，系统的能量状态之间没有水平横穿），定理决定了在绝热极限（当T→∞）中，系统将保持其地位。 在实践中，当然，T总是有限的，但它的时间越长，而且系统在时间进化期间偏离其地位的可能性越少。
