ACM通信
ACM新闻
计算机科学证明揭示了意想不到的纠缠形式
PCP定理(“概率可检验证明”)指出，不仅条形磁铁漂浮在水中(或与之相关的方面)的最终状态难以计算，而且许多通向该状态的步骤也难以计算。
图片来源:Kristina Armitage/Quanta Magazine
关于量子计算复杂性的一个惊人的新证明可能最好通过一个有趣的思想实验来理解。冲个澡，然后把一堆漂浮的条形磁铁倒进水里。每个磁铁会前后翻转方向，试图与相邻的磁铁对齐。它会推拉其他磁铁，反过来也会被推拉。现在试着回答这个问题:这个系统的最终安排是什么?
事实证明，这个问题和其他类似的问题复杂得令人难以置信。只要有超过几百块磁铁，计算机模拟就会花费相当多的时间来得出答案。
现在让这些磁体成为量子——个体原子服从量子世界的错综复杂的规则。正如你可能猜到的，问题会变得更难。“相互作用变得更加复杂，”他说亨利袁哥伦比亚大学的。“当两个相邻的‘量子磁铁’快乐时，有一个更复杂的约束。”
从广达电脑杂志
查看全文
没有发现记录