请科技公司做网站需要注意什么/清远市发布
本文原发于 如何用 IT 业者能听懂的话介绍量子计算的原理？ ，不知道是因为问题实在太老了还是新号没人权，只有几十的阅读量。虽然是一时上头写的，但是毕竟写了这么长不想浪费，所以就以文章的形式再发一次。
写这篇的起因是发现是知乎上的现有科普都“太物理”了，而且往往罗列了很多概念但是并没有完整地陈述任何算法，我想可能后者是计算机/数学背景者更想听的，所以着重做点补充。
当然，这可能主要是因为目前国内除了应组基本上都是物理背景为主，知乎上量子方面的大V也都基本都是物理背景。但既然近些年的趋势是越来越侧重量子计算，一份针对CS背景、跳过物理实现直接从数学抽象入手的入门介绍，应该是有价值的。
本文只是一份并不完整的粗浅解读，但是不需要任何物理背景，也不去谈各种高大上的概念，侧重于具体的计算模型和简单的算法例子，感兴趣的话可以拿起笔跟着一步步推下去。希望能帮助计算机/数学背景者对量子计算有个大概的了解。欢迎指正。
可以这么理解，量子计算能加速的本质在于其自带一定的叠加性。经典计算机上计算1+2和5+8需要调用两次加法器分别计算1+2=3和5+8=13，而量子计算机上输入“1叠加5”和“2叠加8”，调用一次量子加法器就可以得到“3叠加13”。
当然，我们并不能直接在“3叠加13”中获取到3和13这两个信息。但是凭借巧妙的设计，有些时候通过叠加态就能直接得到我们需要的结果。
（本文只讨论纯态pure state。本文主要介绍通用量子计算。）
经典计算机中每个比特要么是0要么是1，而量子计算机中对应的是
这里是狄拉克符号，对应的矩阵就是
不同于经典计算机中每个比特要么是0要么是1，量子计算机中每个qubit可能是0和1的叠加态，例如
这里说几个常用的记法，
经典计算机中当然是要用到很多比特的，量子计算机中一个系统同样有很多qubit。我们直接使用张量积(tensor product)连接。例如一个两qubit的系统，第一个qubit是
注意多个qubit同样有叠加态，例如：
又例如：
可能你已经注意到了，对两qubit的系统来说，这个矩阵的四个系数对应的就是
（感兴趣可以去具体看一下tensor product具体的运算规则，不过这个不影响对后文的理解）
经典计算机中有与或非等各种门，量子计算机同样需要各种门(gate)来进行计算(again,跳过背后的物理意义)。一个作用在n位量子比特上的门描述为一个
关于各种常见的门，参考维基百科就好了。
https://en.wikipedia.org/wiki/Quantum_logic_gateen.wikipedia.orgen.wikipedia.orgen.wikipedia.org我们一般使用量子线路(circuit)来描述量子计算。
例如维基上这个例子，先经过H门，再经过CNOT门。不难验算，输入
写得更容易看懂一点就是：
最后，关于测量，就是把量子信息再转化为经典信息。比如一qubit的态
可能你已经注意到了，就测量的表现而言，我们并不能区分
（注意一定要overall才能忽略，
有了上面这些铺垫，相当于我们已经理解了经典计算机中什么是0,什么是1，什么是运算，可以开始看具体的算法了。
Deutsch Algorithm
先看一个玩具问题。我有一个黑盒函数
不难看出最少需要两次，
那么来看量子。
既然要发挥量子计算机的威力，自然要输入叠加态。
先注意一个有趣的现象，计算
于是我们把
输入
所以，我们只需要测量第一个qubit是
相比经典计算机调用了两次
Deutsch-Jozsa Algorithm
这次稍微扩展一下：我有一个黑盒函数
不难看出，使用经典计算机，最坏情况需要调用
接下来考虑使用量子计算机。
要判断究竟是“一致的”还是“平衡的”最少需要调用多少次
这次给出完整步骤：
输入是
第一步，通过若干
第二步，过
第三步，再给前
这个时候来看最终的表达式，每一个
如果
如果
上面分析了这么多，实际做的时候反倒很简洁：
过
对比一下，经典计算机下，最坏需要调用
通过这两个看起来没什么用，其实真的也没什么用的算法，应该可以感受到量子计算机超越经典计算机的威力。
【全文完】