量子近似优化算法（QAOA）

想象你面对一道难解的“最佳排布”谜题，比如把一群人分成两队，使得被切断的朋友关系尽量少。QAOA 是一套配方，让一台小型量子计算机与一台普通计算机携手合作，去寻找好的排布方案。量子的部分先把量子比特准备成某个状态，然后在两个步骤之间来回推动它：一个步骤奖励那些在你的谜题上得分高的排布，另一个步骤轻轻搅动量子比特，让不同的可能性相互混合、相互干涉。你把这一对步骤重复若干次（p 轮），每一轮由几个可调的角度控制。接着你测量这些量子比特，得到一个候选答案，再用普通计算机检查它的得分。

下面是诚实的部分。QAOA 并不会“一次性尝试所有排布”。那些角度真正控制的，是振幅如何相互干涉，从而让你在测量时，平均而言更常得到好的排布、更少得到差的排布。所以你要运行很多次，并保留你见过的最好结果。一个经典优化器会在两次运行之间调整这些角度，把那个平均水平往上推。它之所以叫“近似”，是因为它追求的是足够好的答案，而不是保证最优的答案；而且在轮数很少时，质量是有限的。在当今这些有噪声的小型机器上，QAOA 是研究得最多的算法之一，确实很有意思，但到目前为止，还没有人证明它在某个真实、有用的问题上能胜过强大的经典优化求解器。