量子计算机通过操纵量子态的概率幅度,利用干涉来放大正确的解。Grover 或 Shor 等量子算法利用叠加,即量子比特同时存在于多个状态中。当这些状态通过量子操作(门)演化时,它们的概率幅度——决定测量特定状态可能性的数学值——像波一样发生干涉。正确的解被设计成相长干涉(相加),增加它们的幅度,而错误的解则相消干涉(抵消)。这个过程系统地提高了在测量量子比特时观察到正确答案的概率。
例如,Grover 算法在 ( O(\sqrt{N}) ) 步中搜索 ( N ) 个项目的未排序数据库。最初,所有状态都处于相同的叠加状态。一个预言机门通过翻转目标状态的幅度来标记它。然后,一个扩散门将所有幅度围绕平均值反转,从而放大标记状态的幅度。重复这个序列会进一步增加目标状态的概率。这些门的设计使得相长干涉集中在正确的解上,而相消干涉抑制其他解。这类似于调整无线电信号:噪声(错误的答案)被消除,留下更清晰的信号(正确的答案)。
开发人员可以将这看作是一种控制概率偏差的方法。经典算法逐一检查解决方案,但量子干涉并行评估所有可能性,并将系统“引导”到最佳结果。然而,设计有效的干涉模式需要精确的门序列和理解问题的结构。例如,Grover 的扩散算子之所以有效,仅仅是因为它利用了叠加的对称性。退相干或门错误等挑战会扰乱干涉,因此纠错和噪声抑制至关重要。这种方法并非普遍更快,但对于特定的问题,干涉提供了相对于经典方法的平方或指数级的加速。