尽管量子计算机早在2001年就成功分解了数字15，但至今仍未分解21。这并非因为技术停滞，而是因为分解21在计算上比分解15要复杂超过100倍。其根本原因在于15具有独特的数学捷径，这些捷径在分解21时完全不适用。因此，将分解15作为衡量量子计算进展的基准具有误导性，真正的进步应关注量子纠错和系统扩展等更基础的领域。
一个惊人的成本差异
将数字15和21进行因数分解所需的量子电路（即一系列量子逻辑门）成本差异巨大，这揭示了问题核心。
- 分解15： 2001年的实验电路总共使用了 21个纠缠门。
- 分解21： 一个经过优化的电路需要 2405个纠缠门。
这个成本差异超过了 115倍。人们通常猜测分解21的难度可能只比分解15高一点，但实际上，它的复杂度高出了两个数量级。
为何分解15如此“便宜”？
量子因数分解的主要成本来自一系列条件模乘法运算。数字15之所以特别容易，是因为以下三个因素极大地降低了运算成本：
- 大量的“乘以1”操作： 在分解15的过程中，大部分乘法步骤最终都变成了乘以1。乘以1在计算上等同于“什么都不做”，因此极大地节省了资源。
- 首次乘法的简化： 算法中的第一次乘法总是可以被简化，因为它作用于一个已知的初始值。在分解15的较少步骤中，这个“免费”步骤的占比非常高，带来了显著的效率提升。
- 通过循环移位实现乘法： 最关键的一步，即乘以4模15，可以被简化为两次循环移位。这是一种极为罕见的特殊情况，它将一个原本昂贵的操作变成了一个非常简单的操作。
这些优势适用于分解15时所有可能的随机基数选择，而不仅仅是特例。
为何分解21如此昂贵？
当我们尝试分解21时，上述所有使分解15变得简单的捷径都消失了。
- 没有“乘以1”的捷径： 分解21的运算过程中，几乎没有可以被省略的乘法步骤，这意味着电路必须为每一次运算付出全部成本。
- 简化效果减弱： 尽管“首次乘法简化”的技巧依然适用，但由于分解21需要更多的乘法步骤，这一项优化的相对收益被大大稀释了。
- 昂贵的标准乘法： 分解21所需的模乘法（如乘以4模21）无法通过简单的循环移位实现。实现这些操作需要极其复杂的电路，例如，仅乘以4模21就需要41个Toffoli门，成本急剧增加。
这三个因素共同导致了分解21的成本相较于分解15出现了超过100倍的暴增。
其他影响因素
除了核心算法的复杂度，还有其他几个重要原因解释了为何分解21至今仍未实现。
- 早期实验的争议性： 2001年分解15的实验使用的是核磁共振（NMR）量子计算机。这类计算机存在固有的扩展性问题，学术界甚至对其是否真正“量子”存有争议。
- 量子纠错的巨大开销： 执行多100倍的门操作，意味着对错误率的要求也高了100倍。实现这种低错误率最可行的方法是量子纠错，但这会引入巨大的冗余，可能轻易地将所需的量子比特数量再增加100倍。
- 误导性的研究报告： 一些声称已用量子计算机分解21的论文，实际上使用了“作弊”的优化方法。这些方法在生成电路时，预先利用了答案（即21的因子）来简化问题，这违背了因数分解的初衷。
由于这些原因，使用小数字进行因数分解并不是一个衡量量子计算进展的良好基准。我们更应该关注那些真正推动领域发展的核心挑战，例如量子纠错的可靠性和解决架构扩展难题的进展。