CLASSICAL COMPUTING, QUANTUM COMPUTING, AND SHOR’S FACTORING ALGORITHM 1
CLASSICAL COMPUTING, QUANTUM COMPUTING, AND SHOR’S FACTORING ALGORITHM 1
复制标题
经典计算、量子计算和 SHO 分解算法 1
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Yuri I. Manin
中科院分区：
文献类型：
--
作者：
Yuri I. Manin
0.为什么是量子计算？信息处理（计算）是由技术（计算机）或自然（大脑）产生的高度组织的物理系统的动态演化。这个系统的初始状态是它的输入，它的最终状态是输出。物理学以两种互补的模式描述自然：经典和量子。直到90年代，计算的基本数学模型，图灵机，都是经典的对象，尽管研究量子模型的第一个建议至少可以追溯到1980年。粗略地说，研究量子计算的动机来自几个来源：物理和技术，认知科学和数学。我们将依次简要讨论它们。(i)物理上，量子描述模式比经典描述模式更基本。在70年代和80年代，有人指出，由于叠加原理，在经典计算机上模拟量子过程在计算上是不可行的（[Po]，[Fe 1]）。粗略地说，量子化一个具有N个状态的经典系统，我们得到一个量子系统，其状态空间是一个（N-1）维复射影空间，其体积随N呈指数增长。人们可以说，量子化学的主要关注点是与由此产生的困难作斗争。反过来说，人们可能会期望量子计算机，如果它们能够建造的话，将比经典计算机强大得多（[Fe 1]，[Ma 2]）。现代计算机的微制造技术的进步已经使我们达到了量子噪声成为微芯片无错误功能的重要障碍的水平。在设计计算机时，开始利用小物体的基本量子力学行为，而不是中和它，这是唯一合乎逻辑的。（ii）作为另一个动机，人们可以援引高度投机性的，但有趣的假设，我们的大脑实际上是一台量子计算机。例如，最近在编写高效的国际象棋软件（深蓝）的进展表明，模拟世界锦标赛水平只使用经典算法，一个必须能够分析约10 6位置/秒，并使用约10 10存储字节。由于神经元处理的特征时间约为10 - 3秒，因此很难解释经典大脑如何能够像卡斯帕罗夫那样成功地完成这项工作并下国际象棋。一个不那么壮观，但消耗资源不少的任务是语音生成和感知，这是由数十亿人类大脑常规完成的，但仍然存在一个复杂的问题。
0. Why quantum computing? Information processing (computing) is the dynamical evolution of a highly organized physical system produced by technology (computer) or nature (brain). The initial state of this system is (determined by) its input; its final state is the output. Physics describes nature in two complementary modes: classical and quantum. Up to the nineties, the basic mathematical models of computing, Turing machines, were classical objects, although the first suggestions for studying quantum models date back at least to 1980. Roughly speaking, the motivation to study quantum computing comes from several sources: physics and technology, cognitive science, and mathematics. We will briefly discuss them in turn. (i) Physically, the quantum mode of description is more fundamental than the classical one. In the seventies and eighties it was remarked that, because of the superposition principle, it is computationally unfeasible to simulate quantum processes on classical computers ([Po], [Fe1]). Roughly speaking, quantizing a classical system with N states we obtain a quantum system whose state space is an (N − 1)– dimensional complex projective space whose volume grows exponentially with N. One can argue that the main preoccupation of quantum chemistry is the struggle with resulting difficulties. Reversing this argument, one might expect that quantum computers, if they can be built at all, will be considerably more powerful than classical ones ([Fe1], [Ma2]). Progress in the microfabrication techniques of modern computers has already led us to the level where quantum noise becomes an essential hindrance to the error– free functioning of microchips. It is only logical to start exploiting the essential quantum mechanical behavior of small objects in devising computers, instead of neutralizing it. (ii) As another motivation, one can invoke highly speculative, but intriguing, conjectures that our brain is in fact a quantum computer. For example, the recent progress in writing efficient chess playing software (Deep Blue) shows that to simulate the world championship level using only classical algorithms, one has to be able to analyze about 10 6 positions/sec and use about 10 10 memory bytes. Since the characteristic time of neuronal processing is about 10 −3 sec, it is very difficult 1 2 to explain how the classical brain could possibly do the job and play chess as successfully as Kasparov does. A less spectacular, but not less resource consuming task, is speech generation and perception, which is routinely done by billions of human brains, but still presents a …