【官方双语】我对格罗弗算法的解释有哪些不足|格罗弗算法2？

趁没人偷偷晒一下我的小π[doge]

♥ 272 ↩ 16

《上周》指刚刚

♥ 254 ↩ 7

好耶，三！连！更！ 这里是继《上周》视频之后又一次负责了翻译的忆拾，希望能得到一些翻译上的反馈意见！值得一提的是，翻译组对 2:33 处的 emergent phenomenon 如何翻译进行了很多探讨，最终采用译注的形式，把我们认为最完整的含义解释给大家，希望能让大家对格罗弗算法的理解增进一分！

♥ 88 ↩ 5

12:45 这里是重点，建议配合英文字幕理解，格罗弗算法的前提是你已经有一个编写好的量子验证函数V了，V的作用是不改变所有错误解方向的向量，只翻转正确解方向的向量。格罗弗算法必须配合这个函数V才能组合成求解数独的完整量子计算程序。 至于这个函数V怎么来的，可以认为是某个大聪明帮你提前写好的。。有人可能会觉得，这个大聪明都有能力写出量子版的验证函数来了，就不能直接写出量子版的求解函数吗。我只能猜测，即使在量子计算领域，编写验证函数也远比编写求解函数简单…… 所以，现实中格罗弗算法要对某个问题发挥作用，还得有能力编写针对这个问题的量子验证函数才行。我感觉这才是量子计算的难点所在（之一

♥ 86 ↩ 9

就是你知道答案在一堆数里面，不知道其中哪个是答案，但可以通过一个方法来验证每个数是不是答案（np问题） 然后因为量子属性的原因，可以把每个答案叠加起来（向量和）一起输入进去，会得到正确答案反转，错误答案不变的向量的叠加和，但只是个和，量子是叠加态的，观察一下只会坍缩宏观上形成概率分布，也就是得不到ax+by这种表达式，所以需要用一个方法来把他们分开 所以要重复进行那个算法（实在记不住名字），来让输出的向量无限接近与答案向量，这样观测的时候就能几乎百分百坍缩在答案上

♥ 71 ↩ 11

看似上周，实则商周[滑稽]

♥ 62 ↩ 1

截至2025年5月，比特币网络的全球算力（哈希率）约为 600 EH/s（exahashes per second），即每秒 6 \times 10^{20}次哈希计算（根据近期区块链网络统计数据估算）。 1、使用经典计算破解SAH256加密哈希函数理论需要6.08×10的（48 次方）年 2、量子计算里的格罗弗算法使用全球比特币网络算力破解SAH256加密哈希函数理论需要180亿年。

♥ 55 ↩ 7

任务：从一袋子绿豆中找到唯一的一颗红豆 CPU（单核）：逐个将袋子中的豆拿出来，挨个检查，直到拿到红豆 GPU：逐批次将袋子中的豆拿出来平铺到桌面上，同时检查，直到拿到红豆 QPU：每个袋子只有拿一颗豆子的机会，想再来得换一袋新的，所以先对袋子一通摇和甩，让红豆尽量被甩到最上面，然后尝试拿一颗豆子，如果不是红豆就拿一袋新的再来一次[doge]

♥ 45 ↩ 2

其实整个视频就是在解释为什么可以绕着剩下所有b的和翻转，原因是verify的过程恰好能进行，就这么简单

♥ 35

也就是说，虽然验证器的的作者也不知道提前真值是哪一个，但他能确保多次执行验证器后会让向量更接近真值，此时进行观测就有很高概率看到真值。经典验证器需要执行O(N)次才能找到真值，而量子验证器只需要执行O(sqrt(N))次就有很高概率找到真值。

♥ 31

实际上完全可以把隐藏的部分全部讲了，这个算法毕竟是几乎所有量子计算课程里第一课必讲的东西，所需的前置知识30min绝对是够的

♥ 31

最后一段是重点。几年前我与他人就量子通信的问题辩论，对方说QKD没有认证机制，因而并没有绝对安全。然而事实是量子通信并不需要额外开发新的认证技术，哈希算法本身是具备对量子计算的安全性的，量子计算并没有破解SHA256, 人们所需的唯一工作是将经典通信中的认证机制迁移到量子通信中。

♥ 22 ↩ 9

前排

♥ 11 ↩ 3

SHA-256之类不可逆解的一个主要原因就是人的现实世界太过巨大了，普朗克常数=6.62607015×10⁻³⁴尺度附近的“计算机”以100%光速逻辑门运算才能逼近π/4*2^128次数的404万次时间，而时间标准1000次/473MS下，依然需要恐怖的31分钟，而这已经是宇宙的极限了

♥ 10 ↩ 19

例子中的验证函数有非常大的干扰，数独是更好的例子。 以下是粗略的理解 量子算法里面只写了给出的数独的盘面、数独规则以及评分规则，量子计算机运行算法以后，大自然会对盘面并行遍历所有可能的数独盘面，也就是大自然根据条件初始化一个向量空间，这个向量空间包含着所有状态向量（盘面）。 我们知道这个数独必定有一个答案，大自然也知道这个向量空间必定存在一个状态向量是正确答案，因此大自然已经验证完毕，大自然根据算法将该向量的被抽取概率调高一些，然后随机抽取一个向量输出。 经过多次运行算法以后，正确的状态向量被观测的概率已经很高了，因此再进行类似观测时，我们就有很大概率宣称这是正确答案。 其中关于大自然有无遍历所有盘面的问题，实际上是没有的，当向量空间建立的那一刻所有的状态向量都是存在的，不需要逐个逐个向量添加进向量空间里。也不必纠结如何对状态向量翻转、确定某一状态向量，向量空间里发生的翻转、旋转并不是真实发生的，不是大自然根据算法规则如何运行更是不可理解的，这只是我们借助数学工具，帮助自身理解这一过程的假想。

♥ 10 ↩ 1

感觉这个算法其实是是一种指导搜索算法的算法，因为这个不知道的函数需要我们自己制备，这也是这个算法使用最困难的地方吧，这个函数可以是某个方程，比如x^2+y^2=z^2在有限取值范围的解，这种也可以用暴力搜索。所以机器不知道解，更多的是知道解满足的方程，然后用量子逻辑门编程什么的得到这个方程的量子计算表达，然后用格罗弗算法搜索解。本质上这个算法还是暴力搜索吧，只是有了量子比特效率会快不少，不过感觉根号N的算法还是慢了点。

♥ 8

要是有多解，算法还能给出答案吗？是在正确答案里随机给出一个？

♥ 7 ↩ 15

意思可能是，你有一个函数可以检验数字是不是np的解，方式就是真解输入函数会输出1，其他的会输出0。然后1就是true，0就是false。传统的计算就是我循环一下所有的输出，一直读取到1，然后找到解。量子计算就是我先有量子计算对应的函数，就是把传统函数变换一下，真解现在输出的不是1，而是-1，其他的输出的是1。然后我也不循环读取结果来找到那个-1，我就不停变换让量子计算输出真解概率接近1，这样我输入一个平均概率的量子串，输出的那个数就很大可能是真解

♥ 6 ↩ 3

催一下transformer的训练部分[大哭][大哭][大哭]

♥ 6

我感觉大概看懂了，可能学计算机导致我比较能接受“你不要管为什么反正这个函数就是能起这个作用”，但不得不说确实诡异吧

♥ 5 ↩ 2