无需先前知识的量子计算基础指南
有人将人类统治地球资源的过去几千年描述为人类世，源自希腊词汇“anthropo”指人类，以及“cene”指近代。特别是过去的一个世纪被称为第四次工业革命，因为20世纪中期计算机的出现引发了技术创新的速度。
在过去的七十年里，计算已经改变了社会的方方面面，实现了高效率的生产、从主要生产到服务的人力转移，并通过电信技术指数级地增强了信息存储、生成和传输。
我们是如何到达这里的？从根本上说，技术进步依赖于现有科学。如果没有电磁学的本质和原子的结构的理解，我们将无法拥有电力和驱动计算机的集成电路技术。因此，想要利用由量子力学提供的物理现象的最准确、最基本的描述进行计算只是迟早的事。
我对量子计算产生了兴趣，既是因为我对物理学和计算机本质的浓厚兴趣。如果成功，量子计算可以通过指数级地增强当前计算机的效率，开启我们信息时代无与伦比的新篇章。作为对数据、计算和信息科学感兴趣的人，了解量子信息的基本原理不仅可以让您对量子物理学有一个非常基本的了解，还可以为我们信息时代的下一个重大技术前沿做好准备。
量子现象与量子信息
为了理解计算的基础知识，有必要对量子计算所利用的物理现象有一个基本的了解。
相关的现象是电子自旋和光偏振，后者是光子自旋的另一种说法。回想一下，电子是负电荷的亚原子粒子，围绕着一个带有正电荷的原子核，而光子是电磁学或光的粒子等效物。电子和光子的自旋是相关的，因为它们都涉及到在经典力学中没有类似物的量子特性，而经典力学描述的是日常物体的尺度。
然而，介绍自旋最简单的方法是将其与一个称为角动量的经典属性进行比较。角动量是指经典系统中的旋转动量等效物，其中动量被计算为质量和速度的乘积。因此，动量是一个矢量量，因为它具有大小和方向。角动量表示为粒子位置和动量的叉积。由于角动量是一个经典属性，它允许连续的值，并且可以表示为体积积分（从二维情况下的曲线下面积推广为积分）。
自旋通常被定义为固有角动量。回想在经典力学中，力被定义为动量的变化。此外，系统的能量是通过运动或运动的变化率来定义的，这就预设了质量。与经典力学不同，爱因斯坦的狭义相对论通过E = mc²等式将固有能量归因于静止质量。类似地，固有角动量与亚原子粒子的固有能量状态密切相关。事实上，这是一个基本粒子无论是否旋转都具有的属性，也就是说，与动量和位置等外在因素无关，因此具有”固有”这个限定词。与经典角动量不同，量子自旋在旋转下发生变化。然而，与经典角动量不同，自旋是量子化的，这意味着它只允许一组离散的值。
一个基本粒子的最大自旋由 n（n/2 的任意整数半整数值）和约化普朗克常数 ℏ（h/2𝜋）的乘积给出。所有普通粒子，即费米子，都有半整数（1/2）的自旋，而光子等称为玻色子的力传递粒子具有整数（1）的自旋。电子和光子都有两种可能的自旋状态：自旋“向上”或“向下”。 在数学术语中，电子的最大自旋为 1/2ℏ 或 -1/2ℏ，即正“旋转”或负“旋转”。 光子的最大自旋为 1ℏ 和 -1ℏ，因为它采用整数自旋值。 即使我们使用“旋转”一词，最好不要将其视为空间变换。
现在让我们来看一下将用于量子计算的奇怪量子特性。 我们之前注意到电子可以有两种可能的自旋状态，但在任何给定时刻它处于哪种状态？ 这就是区分系统状态和测量状态的用处所在。 在经典力学中，状态和测量完美地重合：系统的状态就是你所测量的。 但在量子力学中则不然。 测量前的系统状态由波函数 𝛹i 的相干叠加给出。 测量后，如果我们测量单个粒子，系统的状态将由 𝛹↓ 或 𝛹↑ 给出。 状态和测量之间的这种分离使得量子计算机能够在二维复向量空间中执行可以取无限值的操作。
最后，测量相对于测量的方式遵守某些规则。 具体来说，测量的方向对于结果很重要。 假设我们有两个方向：垂直和水平。 如果我们在垂直方向测量电子的自旋，我们将得到自旋向上或向下的状态。 如果我们进行完全相同的测量，也就是在垂直方向再次测量自旋，我们将得到相同的结果。 这表明存在一个可产生可预测结果的实验设置。 但是，如果我们首先在垂直方向测量电子的自旋，然后在水平方向测量并重复进行测量，结果将是自旋向上或向下的随机序列，在足够的试验中均匀分布在两者之间。 这意味着如果我们不小心，量子测量可能产生随机结果。 量子算法的目的将是控制操作，以便获得我们所期望的结果。
尽管量子计算的信息单位量子位(qubits)可以用电子或光子自旋来表示，但我们将使用前者作为量子计算的物理模型。
从量子现象到量子计算
经典计算机的基本信息单位称为比特，它具有两个离散状态，通常表示为 0 或 1。由于计算机是一台物理机器，这个数学抽象必须映射到某种物理现象上。经典计算机将这些离散状态映射到流动电流或电压上。当电压低或接近于零时，我们用它表示状态 0，当电压较高时，我们用它表示状态 1。换句话说，电压大小的调制使我们能够机械地实现一个二进制的表示系统。这些低电压和高电压状态的序列随后被排列成模拟逻辑门（如与门、异或门等）的电路。通过电路中逻辑操作的组合，能够执行任何可计算算法。
现在我们看到经典计算机利用电来实现计算，这有助于我们理解量子计算机的运作方式。与经典计算机不同的是，量子计算机利用量子或亚原子尺度现象进行计算。在我们日常宏观尺度上，电压是作为连续变量来测量的，但量子力学告诉我们，在亚原子尺度上，实际情况并非如此。根据所有的实验观察，亚原子粒子似乎只能占据离散的能量状态。这意味着电子和光子可以占据一些能量状态，而不是其他状态。这违背了我们关于物体能够占据任何连续能量状态的直觉。例如，我们通常将时间看作一个纯连续变量，可以无限细分，但对于亚原子粒子的能量状态来说，这明显不是问题。
这带来的奇特后果是亚原子粒子不能被描述为具有固定位置和动量。虽然我们可以尝试同时描述这些变量，但存在一个物理尺度，精度会失去，这意味着知道动量就意味着无法追踪位置，反之亦然。这个物理尺度被称为普朗克尺度，用h表示：6.626070·10⁻³⁴ m²kg/s，表示经典和量子尺度现象之间的物理阈值。在这个尺度上，再次根据所有的实验证据，亚原子粒子同时占据所有可能的状态。由于这个属性，我们只能将亚原子粒子描述为所有可能状态的概率分布，这由薛定谔方程描述。正如我们之前指出的，有第二种描述称为测量。在测量之前，粒子存在于由薛定谔波函数描述的叠加态中。测量后，粒子会坍缩到一个离散的位置状态。量子计算利用了量子力学的这一奇特属性进行计算，即利用叠加态和测量态的优势。如果您想在超位置的客观基础上有更明确的理解，请阅读此处的实验证据。
因此，如果传统计算机在两个可能的离散状态中构建计算，我们可以将量子计算机看作是从离散状态和叠加态构建计算的方式。当我们测量量子比特时，它可以处于状态0或1。然而，在测量之前，量子比特处于0和1的叠加态中。在叠加态期间，量子比特可以占据无限的状态。通过利用量子力学的规律，量子计算超越了计算空间仅局限于2^n的经典计算能力。确保测量将量子状态转化为经典状态，即相同的2^n状态空间。那么，量子计算如何提供超越经典计算的优势呢？
正如我们将在下面看到的，量子算法允许在叠加态中进行受控操作，使我们能够在测量后获得有用的答案。计算机科学家根据解决算法所需的时间步骤定义算法的复杂性。如果$n$表示算法的输入长度，$T(n)$表示解决其所需的时间，则复杂度指的是描述$T(n)$增长的函数。如果$T(n)$是一个多项式，那么该算法被认为属于多项式时间类问题。如果$T(n)$是指数函数，那么它属于指数时间类问题。那些属于指数时间类的问题，如大数的素因数分解，对于经典计算机来说是棘手的，因为解决问题所需的时间呈指数级增长，很容易超过人类可接受的时间限制。
量子计算的诺言部分在于能够快速解决指数时间类问题。
量子比特的表示：线性代数
为了理解量子计算，我们必须了解一些支撑比特表示的数学。这些数学工具需要对应于我们将映射计算的基础现象，主要是线性代数。
我们用二维单位向量表示量子比特。
什么是向量？
向量是由至少两个值表示的量：大小和方向。向量的大小由欧几里得距离给出，而方向由起始点给出。例如，(1，-3)表示一个二维向量，长度为3.162，方向由x值给出。
什么是单位向量？
单位向量是长度或大小等于1的向量。例如，<0,1>是一个单位向量，因为我们使用勾股定理计算欧几里得距离时得到值为1。
为什么是二维单位向量？
由于有两个可能的电子自旋测量结果，我们需要一个由ℝ²表示的二维向量空间。我们使用单位向量，因为我们希望将测量结果限制在两个可能的值：0或1。正如我们将看到的，我们在比特上执行的运算等效于在一个幺正平面上进行旋转。然而，可能的结果空间应该包括所有可能的在三维球体上的旋转，其底层空间仍然是二维的，表示两个可能的测量结果。为此，我们将向量表示为复数，而不是实数，用复向量空间ℂ²表示。（复数包括任何涉及实数和虚数的运算，其中虚数i等于√-1）出于简化起见，我们现在将使用ℝ²，避免复数。
为了将结果限制为两个可能的值，我们不仅需要单位向量，还需要两个单位向量彼此正交。如果两个向量的内积或点积等于零，那么它们彼此正交。当组合的单位向量彼此正交时，我们称其为正交规范基，结合了代表单位向量和正交的单词。
正交性：如果两个向量的内积等于零，那么它们是正交的：<a|b> = 0。
我们可以通过检查任何$n$维的ket是否是正交规范基，来验证矩阵$A$和其转置$A^T$的乘积是否等于一个单位矩阵In。
尖括号表示法
在我们描述这些基之前，让我们先谈一下在线性代数中使用的标准符号，以便你能正确解释符号。
列向量称为共轭矢量，而行向量称为凯特矢量，表示如下：<a| & |b>，其中：
它们共同构成了共轭矢量。根据点乘规则（即向量乘法），只有相同维度的共轭矢量和凯特矢量才可以相乘。
上述共轭矢量和凯特矢量之间的内积表示为<a|b>，表示：
然而，相同类型的向量（共轭矢量或凯特矢量）且具有相同维度的向量可以相加。
我们可以使用箭头来表示与电子自旋测量相关的标准正交对。
自旋有三个标准正交基：
当我们将相同自旋的共轭矢量和凯特矢量相乘时，得到的值为1：
相反，当我们将不同自旋的共轭矢量和凯特矢量相乘时，得到的值为0：
正如你可以看到的，标准正交括号乘积给出了模拟二进制结果的测量值。
第一个基，由上箭头和下箭头表示，称为标准基，对应于自旋的垂直测量，即沿y轴的测量。第二个基，由右箭头和左箭头表示，对应于自旋的水平测量，即沿x轴的测量。一般来说，有序的标准正交基表示自旋沿某个方向的测量。事实上，我们可以在任何角度或方向𝛳上测量自旋，输出将在该方向上坍缩为自旋向上或向下的离散结果，因为自旋态只能是离散的。
单个或多个量子比特的量子态将由这些基的线性组合给出。因此，基向量将表示量子态的可能结果。正如我们之前提到的，量子比特的状态可以模拟为电子或光子的自旋。在测量之前，粒子或量子态处于叠加态，由基|b1>和|b2>的线性组合表示，形式为c1|b1> + c2|b2>，其中c1和c2表示概率振幅。由于概率振幅可以是负值，所以只使用它们的平方值来表示结果的概率，其中c1² + c2² = 1。因此，在叠加态中，c1²和c2²的概率分别为0.5。
测量后，自旋态将坍缩到正交基|b1>或|b2>中的一个。坍缩到|b1>的概率由c1²给出，而坍缩到|b2>的概率由c2²给出。如果测量坍缩到|b1>，则c1²等于1，c2²等于0，反之亦然。更直白地说，与概率值为1相乘的基矢量将表示测量的结果。
在经典计算中，多个比特由这些比特的张量积表示，用以下符号表示：⊗
我们说[1,0]和[0,1]态代表标准基，因此在经典比特中分别对应0和1。我们还说任何量子态必须保持以下等式：c1² + c2² = 1。我们称之为单位测量约束（概率论的第二公理），这意味着所有的态必须是ℝ²中的单位向量。然而，由于实际量子粒子的状态是用复数表示的，实际的状态空间由ℂ²给出。因此，实际的单位测量约束为：‖𝛼‖² + ‖β‖² = 1，其中𝛼和β是复数，表示概率幅。
为了表示多个量子比特的状态，我们取标准基|0>和|1>的张量积。注意，无论我们连接多少个量子比特，乘积都会满足单位测量约束。
由于我们一直在ℝ²中工作，我们可以用二维空间（x，y）的单位圆来启发地表示量子比特的状态空间。请记住，所有操作都将在我们上述列举的正交基上进行。此外，所有量子逻辑门将由酉和因此正交矩阵表示。为什么？因为由正交矩阵进行向量乘法会通过保持向量的内积产生旋转。这在欧几里德空间上产生等距变换。
还要注意每个180⁰旋转的负号。负号有助于区分等效的输出，使得每个操作理论上都可以可逆或可逆的。所有量子计算都需要是可逆的，以利用量子态（即叠加态和纠缠态）在测量之前赋予的计算能力。正如我们后面将看到的，叠加态（以及纠缠态）赋予量子计算优于经典计算的优势。在叠加态中，任意数量的量子比特N同时占据它们的所有可能状态。如果我们有4个量子比特，样本将有2⁴种可能的状态，但在叠加态下，所有这些状态将同时发生。测量时坍缩到这些状态中的一个的概率将平均分布在单位向量的线性组合中。
下面的单位圆中的线条表示通过与哈达玛门进行操作从输入到输出的状态变化，这将量子比特置于叠加态和反叠加态。由于以下等式 ‖𝛼‖² + ‖β‖² = 1，测量将始终将系统坍缩为不同的经典态，在我们的情况下对应于电子或光子的自旋。然而，使用量子门进行的操作可以改变单个或多个量子比特的状态，而不会使波函数坍缩。
如果我们应用位翻转运算符，相当于经典计算的NOT门，它将反转输入状态的值。例如，|1> ket将翻转为下面所示的|0> ket，通过状态从（0,1）转变为（1,0）。
与此同时，Hadamard门将（0,1）作为输入，并通过与以下正交或酉矩阵相乘将其输出为（1/√2,−1/√2）：
如果你想知道状态的确切变化方式，这里有一个关于Hadamard门与|1>输入状矢量的矩阵乘法的明确说明：
Hadamard门是如何工作的，它有什么特别之处？
通过观察单位圆，可以注意到位翻转操作相当于单位圆上的90⁰旋转，而Hadamard门相当于180⁰旋转。需要记住的是，所有量子门都是通过正交或酉矩阵实现的，这些矩阵在原点产生旋转。特别地，Hadamard门在x轴和y轴之间产生半旋转，对应于概率振幅为0.5。
还要注意到输出矢量是单位矢量，因为（1/√2,−1/√2）满足以下等式 ‖𝛼‖² + ‖β‖² = 1。尝试将输出值代替𝛼和β进行计算。
可以将量子位在单位圆上的某一点的状态想象为将概率振幅从0和1的类似物分布到一些保持单位和的值之间的集合中。Hadamard门将该分布精确设置为50/50的结果。换句话说，测量有50/50的机会将qubit坍缩到|0>或|1>状态矢量。这是数学上超position态的类比。之后我们将看到如何在计算上利用superposition。
最后，迄今为止，我们的演示都是在ℝ²中，将单位圆作为量子位可能状态的空间表示。由于实际的qbit状态用ℂ²中的复数表示，qubit状态空间的更准确的表示是所谓的block sphere，其旨在捕捉复值数的可能状态，如下图所示为三维球体。
量子逻辑门
与传统计算机类似，量子计算中的逻辑门由对qubit或一组qubit执行某些操作的电路组成。前面我们看到，量子门在数学上等于对qubit进行矩阵乘法。我们还说过，qubit由单位矢量表示，而量子逻辑门由正交或酉矩阵表示。正如我们所看到的，这些矩阵在单位球体或圆上产生旋转，将复杂的空间简化为二维的。
然而，为了在qubit上执行操作，量子门必须是可逆的。可逆性意味着从输入到输出的每个操作也必须能够从输出到输入进行逆操作。这是因为量子态是可逆的，具有时间反演不变性，并在超position态中保持信息。然而，我们所谓的测量将量子态变为经典态。测量或坍缩是不可逆的，因此无法保持输入信息。换句话说，我们无法将坍缩回其先前的超position态。因此，量子门构成了在处理量子态的同时保持量子态的可控操作。实现这些结果所需的电路利用了被称为量子点的几纳米大小的半导体粒子，需要将其保持在接近零开尔文的温度下。然而，重要的是要注意，只有通过测量才能获得量子计算的期望输出。
因此，当涉及到量子逻辑门时，最重要的是两个属性：a）可逆性和b）普适性。普适性指的是一种可以对位进行所有可能操作的逻辑门。在经典计算中，最知名的普适门是 NAND（NOT AND），如下表所示：
注意，NAND 是 AND 的真值补。最多只需两个逻辑运算符就能表示所有可能的逻辑陈述，包括逻辑定理。这被称为功能完备性。由于 NAND 将 NOT 和 AND 结合为一个操作，因此顺带地它 qualifies 为一个功能完备和普适逻辑运算符和门。为了对比而言，让我们看一下 AND 的真值表：
在经典计算中，大多数操作都是不可逆的。例如，如果我们将一个序列 010011110 输入到大多数逻辑门中，并得到另一个二进制序列作为输出，仅凭输出序列我们将无法得到输入序列。XOR 和 NAND 都是不可逆的。然而，有一些门可以允许我们仅通过输出来恢复输入，例如 CNOT（等效于 XOR 但是可逆），Hadamard 和 TOFFOLI 门。在这些门中，Hadamard 和 TOFFOLI 都具备可逆性和普适性。然而，还有其他满足这些要求的门，例如 FRIEDKIN 门。我们将重点讨论前三个门。
现在让我们来看看对大多数量子计算至关重要的两个门：CNOT 和 Hadamard。CNOT 在两个或更多量子比特之间进行纠缠。Hadamard 门在一个或多个量子比特上进行超position。我们还将看看第三个门，TOFFOLI 门，也称为控制-控制 NOT 门，它是 CNOT 门的一个普适版本。
CNOT 门的目的是什么？它允许我们通过可逆的位翻转操作来将两个输入量子比特纠缠在一起。CNOT 门由两个输入组成：控制输入和目标输入。当控制位等于 1 时，CNOT 门翻转目标输入。当控制位等于 0 时，CNOT 门不执行任何操作。通过这种方式，每个输出组合都可以追溯到一个且仅有一个输入组合。
CNOT 门何以等同于纠缠？
让我们来看看 CNOT 门对 |1> 和 |0> 量子比特的操作。我们将两个量子比特的张量积乘以 CNOT 门的 unitary 矩阵，将输入的张量积从 |10> 转换为 |11>。为什么？因为只有当控制比特等于 |1> 时，CNOT 才会翻转目标比特的值。
同样地，如果我们的目标比特是 |1> 而不是 |0>，CNOT 门可预见地将值翻转回 |0>，如下所示：
换句话说，CNOT是XOR（异或门）的可逆经典计算等价物。
正如我们之前提到的，Hadamard门可以得到完美的叠加态。它是如何做到的呢？看一下下面的正交矩阵：
如果我们将该矩阵与标准基底|0>相乘，那么输出的状态将是：(1/√2, 1/√2)，相当于(|0>+|1>)/√2。反过来，如果我们将其与|1>相乘，将得到(1/√2,−1/√2)，相当于(|0>−|1>)/√2。尽管每个输入都将输出转换为等概率幅度的分布，但负号使我们能够区分输入（是|0>还是|1>），从而确保操作是可逆的。
在经典世界中，每个值都有50/50的概率。请注意，在我们的示例中，我们对单比特执行了该操作。那么如何将多个量子比特放入叠加态中呢？
我们需要将每个量子比特分别通过Hadamard门，然后进行张量积。正如我们之前提到的，多比特态可以表示为单比特态的张量积。
下面是通过将标准基底|1>与Hadamard矩阵相乘来执行单比特操作：
最后，让我们来看一下TOFFOLI门，也称为控制-控制-非（CCNOT）门。TOFFOLI门与CNOT门几乎相同，只是多了一个控制变量。有两个控制变量时，TOFFOLI门利用一个8×8的正交矩阵对三个输入量子比特进行操作。与CNOT类似，TOFFOLI产生量子纠缠，并可用于量子纠缠和解纠量子比特。
TOFFOLI门的输入输出表格：
为什么我们需要TOFFOLI门，而不是使用CNOT门？
因为像NAND门一样，TOFFOLI在经典计算中是通用的，因此量子计算机可以使用它来模拟可逆的经典计算。然而，TOFFOLI在量子计算上并不是通用的，因为它无法产生叠加态。
既然我们了解了量子逻辑门及其执行的操作，我们如何将它们结合起来得到量子算法呢？
由于量子门保持叠加态的状态，我们可以使用它们来进行可逆的酉运算。从物理上讲，系统随时间的演化由薛定谔波函数描述。然而，要从量子计算机中获取任何信息，我们需要坍缩波函数。
通常，我们结合位翻转和Hadamard门的操作来获得所需的结果。然而，位翻转是不可逆的。量子计算的挑战在于设计以可逆方式编写非可逆函数的方法。我们将看到如何使用Deutsch算法实现这一点。
经典位是量子位的特殊情况
原则上，量子计算机可以实现所有经典计算，因为后者是量子计算的一个子集。
为了通过量子计算机实现经典计算，我们必须将计算限制在由常规基底（类似于经典位的模拟示例）表示的量子比特，并设计可利用经典通用可逆门（如Toffoli门）的电路。由于Toffoli门是经典计算的通用门，它可以用来实现经典计算。
然而，到目前为止，我们还没有讨论任何关于量子算法的内容。我们要如何构建一个量子算法呢？
量子算法：Deutsch Oracle
从计算的角度来看，如果我们无法构建比经典算法更具计算优势的量子算法，那么我们到目前为止所阐述的一切将是无意义的。
1985年，戴维·德沃斯提出了第一个明显实现这一点的算法，即德沃斯的Oracle。
假设有四个函数f₀-f₃。对于输入的0或1，f₀的输出始终为0。对于输入的0或1，f₁的输出如果输入为0则为0，如果输入为1则为1。对于输入的0或1，f₂的输出如果输入为0则为1，如果输入为1则为0。对于输入的0或1，f₃的输出始终为1。
我们可以将函数f₀和f₃称为常量，因为它们无论输入如何都产生相同的输出。我们将函数f₁-f₂称为平衡的，因为它们以对等的方式分配输出。
然后我们要问的问题是：如果我们随机获得其中一个函数，我们需要查询算法多少次才能确定该函数是常量还是平衡的？
答案是，经典计算无法在少于两次查询中确定正确答案。让我们看看这是如何工作的。我们可以选择输入0或1。如果我们输入0，我们可能会得到0或1作为输出。同样，如果输入1，我们可能会得到0或1作为输出。在这两种情况下，我们无法确定输出是由常量还是平衡函数产生的。因此，我们必须再次查询算法才能得出正确的确定。
通过量子算法，德沃斯证明我们只需进行一次查询就可以知道正确答案。为了实现这一点，我们除了输入比特之外，还使用了Hadamard门和控制比特。我们将输入通过Hadamard门。请记住，H将比特置于叠加状态。因此，如果我们输入对|0>和|1>，我们将得到以下各自的状态：(1/√2, 1/√2) ，(1/√2, −1/√2)。然后我们将目标门通过随机fₓ。
由于Hadamard是可逆的，fₓ应将我们的比特放在以下状态之一：
(1/√2) (|0>+|1>); (1/√2) (|0>−|1>); (−1/√2) (|0>−|1>); (−1/√2) (|0>+|1>)
我们再次通过Hadamard门传递控制比特以反转叠加态。由于这些操作是可逆的，我们得到以下可能的结果：
f₀ →|0>; f₁ →|1>; f₂ → −|1>; f₃ →−|0>
这意味着当我们在最后测量比特时，如果输出是|0>，该函数是常量，如果输出是|1>，该函数是平衡的。尽管德沃斯Oracle没有实际用途，但它提供了量子计算优于经典计算的强有力的例子。
Deutsch-Jozsa算法
对多个变量推广的Deutsch Oracle称为Deutsch-Jozsa算法。下面的图示提供了该算法的示意性量子电路。
Shor算法
Shor算法是一种用于分解大整数的量子算法。该算法包含两个部分，第一个部分在经典计算机上执行，第二个部分在使用量子傅里叶变换的量子计算机上执行。我们不会深入探讨该算法的数学细节，因为它们非常复杂，超出了本文的范围。
Shor算法需要两个分别具有1024和2048个量子比特的寄存器，以便对具有309位数字的1024位数进行分解。到目前为止，已分解的最大数字长度为48位，还不足以达到RSA 100位半素数的里程碑。迄今为止，没有量子计算机满足RSA数字挑战的任何一项，该挑战包括一系列仅具有两个素因子的大数字。RSA数字在政府和金融机构的公钥密码学中用于安全数据传输。
借助足够强大的量子计算机，Shor算法可以用于解码使用经典计算机认为在计算上无法处理的非常大的素数的公钥密码学。
量子优越性与未来
正如我们一开始所说，量子优越性指的是量子计算机能够在合理的时间内解决经典上无法解决的问题的能力。原则上，经典计算机可以解决任何理论上可计算的算法。问题在于实践：有限的处理能力使它们无法在有用的时间范围内解决某些问题。这就是量子计算机承诺填补这一差距的地方。2019年，谷歌宣布他们的Sycamore量子计算机（53个量子比特）已经实现了量子优越性。在他们名为《使用可编程超导处理器的量子优越性》的Nature论文中，他们声称Sycamore花费了200秒对一个量子电路的一次实例进行一百万次采样，而这个任务据他们进一步声称，经典超级计算机需要1万年才能完成。IBM反驳了后者的说法，声称他们的一台超级计算机可以在2.5天内完成这个任务，削弱了谷歌跑到终点的声称。
到目前为止，迄今最大的量子计算机IBM的Osprey拥有433个量子比特的处理器。目前构建具有足够大处理器的量子计算机的尝试受到潜在的噪声问题的困扰，即量子态与其周围环境（如温度和磁场的变化）的相互作用导致量子态出现解相干或崩溃成经典态的潜在可能。
噪声问题构成了将量子计算机扩展到分解非常大的素数等计算潜力的关键挑战之一。消噪比特可能可以抵消其中一些挑战，但目前量子计算的发展仍处于初级阶段。
参考文献
Bernhardt, Chris. 《量子计算机：适用于任何人的指南》。The MIT Press, 2020.
IBM unveils 400 qubit-plus quantum processor and next-generation IBM Quantum System Two. IBM Newsroom. (n.d.). https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two
Kaye, P., Laflamme, R., & Mosca, M. (2020). 《量子计算简介》。牛津大学出版社。
“降噪”量子比特可以最小化量子计算机中的错误。芝加哥大学新闻。 (无日期)。 https://news.uchicago.edu/story/noise-cancelling-qubits-can-minimize-errors-quantum-computers#:~:text=As%20existing%20quantum%20computers%20are,to%20high%20rates%20of%20error.
Roush, W. (2020年7月13日)。谷歌-IBM“量子霸权”争斗。麻省理工科技评论。 https://www.technologyreview.com/2020/02/26/905777/google-ibm-quantum-supremacy-computing-feud/
Zubairy, Muhammad Suhail. Quantum Mechanics for Beginners: With Applications to Quantum Communication and Quantum Computing. 牛津大学出版社, 2020年。