量仔前沿新闻与技术实践
返回文章

PQC,文章

量子计算机为什么能加速计算?

从量子比特与干涉出发,理解 Grover 搜索与 Shor 分解如何改变公钥密码威胁。

叠加态与坍缩

量子比特可以用 α|0⟩ + β|1⟩ 表达,其中 |α|² + |β|² = 1。按计算基测量时,0 和 1 的概率分别是两个振幅的模平方。测量前保留振幅和相位,测量得到一个经典结果。

阅读原文对应章节 ↗

量子纠缠

多比特状态可能无法拆成各个比特状态的张量积。以 (|00⟩ + |11⟩)/√2 为例,分别测量时结果一致。每个比特的单独结果仍然是随机的。

阅读原文对应章节 ↗

利用叠加性和纠缠性加速计算

量子门可在叠加态上同时改变多项振幅。算法通过相位与干涉强化能回答问题的结果,同时抵消其他振幅。最后读出的是具有较高成功概率的一个结果。

阅读原文对应章节 ↗

量子计算对不同问题的加速效果

无结构搜索对应 Grover 的平方级查询加速,整数分解和离散对数可用 Shor 算法获得更显著的渐近改进。实际运行还取决于门深度、错误校正与读出成本。

阅读原文对应章节 ↗

附录1:叠加态和纠缠的数学表述

用状态向量描述离散基,用波函数描述连续位置。两者都以复振幅表达测量分布和相位关系。

阅读原文对应章节 ↗

叠加态和坍缩的向量表达

离散基下的状态是复向量。对 |0⟩ 测量算子投影并归一化,可得到测量为 0 后的状态。

阅读原文对应章节 ↗

量子纠缠的向量表达

对复合系统取张量积基。贝尔态对应 (1, 0, 0, 1)/√2,不能写成两个单比特向量的乘积。

阅读原文对应章节 ↗

量子态的波函数表达

位置表示中的 ψ(x) 是复波函数,|ψ(x)|² 给出位置概率密度。相位会改变多个分量叠加后的测量分布。

阅读原文对应章节 ↗

量子态的波函数表达与向量表达的关系

选定基以后,状态在该基上的投影就是振幅。离散位置基得到有限或可数个系数,连续位置基得到函数。

阅读原文对应章节 ↗

附录2:量子算法如何威胁经典密码

Grover 与 Shor 约束不同类型的密码原语。比较安全影响时要把查询复杂度、门数、可用量子比特与容错开销一起考虑。

阅读原文对应章节 ↗

Grover算法:加速搜索问题

Grover 反复执行相位标记与关于平均振幅的反射,从初始均匀叠加中放大满足谓词的分量。

阅读原文对应章节 ↗

经典搜索的瓶颈

黑盒只有一个命中项时,经典搜索在最坏情况下需要线性次数的查询。

阅读原文对应章节 ↗

量子计算如何加速搜索?

量子迭代约需 O(√N) 次调用目标判定电路。多目标情形的迭代次数还取决于命中比例。

阅读原文对应章节 ↗

密码学上的应用举例:破解哈希函数

理想化量子预映像搜索把 n 位输出的查询量级降到 2^(n/2),实现时需把哈希函数编成可逆量子电路。

阅读原文对应章节 ↗

Shor算法:加速质因数分解

Shor 把因数分解转化为模幂的周期查找,用量子傅里叶变换提取与周期有关的信息。

阅读原文对应章节 ↗

经典质因数分解的难点

RSA 安全依赖大整数由素因子构造、而从模数恢复因子在经典计算上代价很高。

阅读原文对应章节 ↗

量子计算如何加速质因数分解?

量子子程序给出周期的估计,经典步骤用连分数候选并校验周期,随后计算最大公约数。

阅读原文对应章节 ↗

密码学上的应用:RSA 破解

恢复 RSA 模数的两个素因子后,可算出相关模数阶并恢复私有指数。20 百万比特的旧估算及低于百万比特的新估算依赖不同的物理和电路假设。

阅读原文对应章节 ↗

原文图例

参考文献

  1. Beckman, David, et al. “Efficient networks for quantum factoring.” Physical Review A 54.2 (1996): 1034.
  2. Grover, Lov K. “A fast quantum mechanical algorithm for database search.” Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996.
  3. Shor, Peter W. “Algorithms for quantum computation: discrete logarithms and factoring.” Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994.
  4. Nielsen, Michael A., and Isaac L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010.
  5. Gidney, Craig. “How to factor 2048 bit RSA integers with less than a million noisy qubits.” arXiv preprint arXiv:2505.15917 (2025).
  6. Gidney, Craig, and Martin Ekerå. “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.” Quantum 5 (2021): 433.