量子计算原理入门

最近 IBM 出了一款 50bit 的量子计算机. 于是好奇的去学了下量子计算原理.

在经典计算机中, 用高电平表示1, 低电平表示0, 使用与, 或, 非三种门来实现对二进制位的基本操作, 比如计算1+1等. 这样的计算结果能保证准确可靠, 不过由于电流是’单线程’的, 那么在多次计算的时候, 便只能不停的循环计算. 比如需要计算1+1, 再计算2+2, 计算机只能先计算出一个结果, 再去计算另一个.

在量子计算机中, 这一切都不同了. 首先量子计算机在运行时没有准确的1和0状态. 就像’薛定谔的猫’一样, 只有在观测的时候才能准确的知道该量子状态是1还是0. 那么使用量子计算机的时候, 便可以假设所有位都是1和0的混合状态. 如果对某一位进行操作, 那么会同时对1和0两种状态进行操作, 生成两种结果, 但是该结果在观测的时候是随机的由1或0生成的结果, 各自比例为50%. 如果对多位进行同时操作, 那么会对它们都造成影响, 生成的结果有2^n个, 观测时候结果为某一位, 概率为1/2^n.

到这一步了以后可能就觉得量子计算不就是坑爹的嘛, 全凭计算出的运气随机观测结果, 结果到底是不是对的也不知道, 就如进行1+1, 可能的结果为: 0,1,1,2.

这时候算法大神们就出场了. Grover算法为一个对数据库进行随机搜索的量子算法. 在传统计算机和数据库中, 如果需要根据某个条件查找一条数据(非主键和索引)时, 需要从头到尾一条条数据循环查找, 这样的计算复杂度为O(N). 而在量子计算机中, 可以将所有数据导入到量子比特中, 只需要占用log2(N)个量子比特, 然后同时对该条件求值, 那么会生成N个计算结果, 而且必有 1 个结果为正确结果, 但是每个结果发生的概率均为1/N. Grover算法思想是, 同时计算出这么多结果以后, 先不要去读取结果, 即不’观测’, 先通过量子操作, 增加正确结果发生的概率. 在一系列复杂的量子操作以后, 该概率会增加一点, 在进行π * √N / 4次操作以后, 要找到的那个数据的发生概率会达到最大, 最大值为1 - 1/2^N. 这时候再去读取数据, 就会以极大的概率读取到正确的数据.

该搜索算法在量子计算机中, 可以将普通搜索的O(N)复杂度变为O(√N), 但是不足之处在于成功读取正确数据的概率永远都不是100%, 所以并不能算完美. 其他使用量子计算机的算法原理也基本类似, 所以都不可能达到完美的结果.

那么量子计算的应用领域也比较清晰了, 适合大量并行任务进行的场景, 如’猜密码’等. 而且需要特殊设计算法, 用于对所有结果进行计算而且选出正确结果的特殊算法.

参考:Grover 算法实现