月归档:八月 2017

量子计算机能快速求解推箱子关卡吗?

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3757 量子计算机常被大众媒体描述得十分神奇,甚至有科学家也添油加醋,如 David Deutsch 的 The Fabric of Reality 一书。用量子计算机能设计出快速求解推箱子关卡的算法吗?我在读了David Deutsch的书后,对此问题颇感兴趣。这个月,阅读了不少相关文献,找到了答案。答案是否定的。 首先,制造出通用的量子计算机仍然有极大的工程技术困难。 第二,再看看理论上,量子算法能干什么。最有名的量子算法就是Peter Shor的整数分解算法,这一算法使得基于大数分解比较困难的公钥加密算法岌岌可危。Shor的算法是1994年提出(Shor因此获得哥德尔奖Godel Prize),历史也没有太长。想要知道这一算法与传统计算机算法有何不同,可读Scott Aaronson的博文 《Shor, I’ll do it》。Scott Aaronson生于1981年,才36岁,是德州大学奥斯汀分校的教授,在理论计算机科学特别是计算复杂度理论方面有非常高的造诣。他博文中对Shor算法的核心解释得深入浅出。关键是整数分解还是有某种规律,量子算法恰恰能更好地利用这一规律,一定程度上避免了暴力穷举。 要注意的是,整数分解并非特别难的问题。在基于传统计算机(图灵机)的计算复杂度理论中,整数分解被认为不属于P,但也只是比P问题略难一些,介于P和NP-Complete之间,且更靠近P。因此,量子算法能快速分解大数也只是情理之中。 知道量子算法是怎么做的,能做什么,就更好地理解量子算法不能做什么。Scott Aaronson博客的站名banner位置有这么一段话,澄清大众对量子计算的误解: If you take just one piece of information from this blog: Quantum computers would … 继续阅读

发表在 推箱子, 数学, 算法, 计算机 | 留下评论