凡人也能了解量子计算吗

当然可以。

凡人也能了解量子计算吗？你偷偷看图试试自己的智力

2017/06/18

参考文献：

1. E.Rieffel,W.Polak, An Introduction to QuantumComputing for Non-Physicists.

2.E.Strubell, An Introduction to QuantumAlgorithms.

-----------------------------

【转】理解计算 (一篇谈经典计算,DNA计算和量子计算的科普短文)

随着计算机日益广泛而深刻的运用，计算这个原本专门的数学概念已经泛化到了人类的整个知识领域，并上升为一种极为普适的科学概念和哲学概念，成为人们认识事物、研究问题的一种新视角、新观念和新方法。
什么是计算与计算的类型
在大众的意识里，计算首先指的就是数的加减乘除，其次则为方程的求解、函数的微分积分等；懂的多一点的人知道，计算在本质上还包括定理的证明推导。可以说，“计算”是一个无人不知元人不晓的数学概念，但是，真正能够回答计算的本质是什么的人恐怕不多。事实上，直到1930年代，由于哥德尔（K.Godel，1906-1978）、丘奇(A.Church，1903-1995)、图灵(A.M.TUI-ing，1912-1954)等数学家的工作，人们才弄清楚什么是计算的本质，以及什么是可计算的、什么是不可计算的等根本性问题。
抽象地说，所谓计算，就是从一个符号串f变换成另一个符号串g。比如说,从符号串12+3变换成15就是一个加法计算。如果符号串f是x^2，而符号串g是2x,从f到g的计算就是微分。定理证明也是如此，令f表示一组公理和推导规则，令g是一个定理,那么从f到g的一系列变换就是定理g的证明。从这个角度看，文字翻译也是计算，如f代表一个英文句子，而g为含意相同的中文句子，那么从f到g就是把英文翻译成中文。这些变换间有什么共同点？为什么把它们都叫做计算？因为它们都是从己知符号(串)开始，一步一步地改变符号(串)，经过有限步骤，最后得到一个满足预先规定的符号(串)的变换过程。
从类型上讲，计算主要有两大类：数值计算和符号推导。数值计算包括实数和函数的加减乘除、幕运算、开方运算、方程的求解等。符号推导包括代数与各种函数的恒等式、不等式的证明,几何命题的证明等。但无论是数值计算还是符号推导,它们在本质上是等价的、一致的，即二者是密切关联的，可以相互转化，具有共同的计算本质。随着数学的不断发展,还可能出现新的计算类型。
计算的实质与E奇－图灵论点
为了回答究竟什么是计算、什么是可计算性等问题，人们采取的是建立计算模型的方法。从20世纪30年代到40年代，数理逻辑学家相继提出了四种模型，它们是一般递归函数、λ可计算函数、图灵机和波斯特(E.L.Post，1897-1954)系统。这种种模型完全从不同的角度探究计算过程或证明过程，表面上看区别很大，但事实上却是等价的，即它们完全具有一样的计算能力D在这一事实基础上，最终形成了如今著名的丘奇-图灵论点：凡是可计算的函数都是一般递归函数(或是图灵机可计算函数等)。这就确立了计算与可计算性的数学含义。下面主要对一般递归函数作一简要介绍。
哥德尔首先在1931年提出了原始递归函数的概念。所谓原始递归函数,就是由初始函数出发，经过有限次的使用代人与原始递归式而做出的函数。这里所说的初始函数是指下列三种函数：
(1) 零函数0(x)=0(函数值恒为零)；
(2) 射影函数(x1,x2,…,xn)=xi(1≤i≤n)(函数的值与第i个自变元的值相同)；
后继函数S(x)=x+1(其值为x的直接后继数)。
代人与原始递归式是构造新函数的算子。
代人(又名叠置、迭置)，它是最简单又最重要的算子,其一般形式是:由一个m元函数f与m个n元函数g1，g2，…，gm造成新函数f(g1(x1,x2,…,xn),g2(x1,x2,…,xn),…,gm(x1,x2,…,xn))。
原始递归式，其一般形式为
(公式略)
特殊地为
(公式略)
其特点是，不能由g,h两已知函数直接计算新函数的一般值f(u,x