Shor:动摇互联网根基的因式分解
前两篇是"开胃菜"。这一篇,我们讲那个真正让密码学家失眠的算法——Shor 算法。
PERSONAL BLOG · 个人博客
这里记录主理人的长期学习、解释和思考。首期从量子计算科普系列开始。
LATEST WRITINGS
第 2 / 4 页,共 27 篇已发布
前两篇是"开胃菜"。这一篇,我们讲那个真正让密码学家失眠的算法——Shor 算法。
Shor 那么猛,Grover 也不差——是不是说明,量子计算机已经"全面碾压"经典计算机了?
前面讲测量时我们提过:量子比特娇贵,一受干扰就"退相干"(第 4 篇)。讲算法时我们又默认:比特都乖乖待着,门都精准无误。
前面说,量子纠错要"成千上万个物理比特"托底。那这些比特,到底是用什么"做"出来的?
聊了这么多原理、算法、硬件,你心里一定有个最实际的问题:这东西,到底能干嘛?
十四篇走到这里,该给你一个最实在的交代:现在到底能不能用?未来五年会怎样?
前情提要:第 9 篇《Shor:动摇互联网根基的因式分解》里,我们说到 Shor 算法把"分解大数"变成"找一个周期"。但"找周期"这句话本身并不产生魔法——真正让经典计算机望尘莫及的加速,藏在一个你当时没见过的变换里。它就是量子傅里叶变换(QFT)。
前情提要:第 2 篇《量子比特:一枚"既正又反"的硬币》里,我们用"旋转的硬币"建立了叠加的直觉。那枚硬币很好懂,但也埋下了一个最常见的误读——这一篇,我要把硬币换掉,给你看量子比特真正的样子。