No programming theorem?
谢邀. 这里的 No-programming theorem 看起来 Michael Nielsen 很喜欢这么叫, 我甚至找到了他做的某个 Slides 上的说明:
(吐槽: 把 Bill Gates 这么支持 Quantum Computing 的人叉掉真的好么......)看了看定义, 说的类似 No-cloning theorem. 简单的说, 就是任意的量子态不可能精确的复制, 除了系统的本征态. 不太严格的说, 考虑一个 CNOT 门和下面的初态(输入):
我们想在第二个 Qubit 上复制它, 那么需要得到:
即上式满足
, 但是用 CNOT 作用输入可以得到
也就是说, 能复制的只有
和
而已.回到 No-programming theorem,
的输入形式看起来非常像通用 Turing 机(Universal Turing Machine)的处理手法. 我们考虑比较简单的情况:
只有一个 Qubit, 而
是单比特量子门. 由于单比特量子门对应 Bloch Sphere 上的一个三维旋转, 所以对其进行 Euler 角分解, 考虑 Euler 角的而二进制形式. 那么, 我们可以把
编码成一系列类似
的旋转, 这里的
表示编码中第
位. 如果我们的程序是互相正交的, 也就是说由三个确定的旋转(z 轴, y 轴, z 轴)决定, 那么当然可以执行. 但是, 如果编码中允许叠加态, 也就是说这里的程序
是多个单比特量子门的叠加的话. 考虑类似 CNOT 的实现, 不过这里的 target Qubit 对应的不是 Pauli X 门, 而是一个旋转. 相当于第一个 Qubit 之前是
, 我们需要把第二个 Qubit 的东西拷贝上去, 那么套用上一段的结果即得. 当然, 对于 Fixed Array 覆盖所有单比特量子门已经不太现实了...不管你怎么编码, 我总是能让长度变得无穷大. 但即使是精度有限的情形, 这样的编码也不能把允许叠加的
作用到第一个 Qubit 上. 于是简单的复制是不可能了, 但是 Programming 也不一定要能复制嘛?... Functional Programming 里面不是也不允许复制么, 大家的 Haskell 还不是写的好好的. 关于量子程序语言, 现在绝大多数成型的理论或者系统都是基于经典控制流的. 我曾经介绍过应明生老师在 CCCF 上写的一篇综述, 量子软件是否有位数之说？ - Climber.pi 的回答. 简单的说, 可以类比成 FPGA 对应的硬件设计语言, 不同的是这里处理的是量子门(酉矩阵)的线路综合. 这种东西足够我们来实现量子算法了, 虽然就像是没有通用 Turing 机只有 Turing 机233. 但是基于量子控制流的那些就复杂得多(看看这里的 No-cloning theorem), 甚至有人为此引入了 Categorical Quantum Mechanics 之类的东西...有兴趣的话, 可以看看 Quipper 或者 ScaffCC, 前者是基于 Haskell 的, 后者是比较正常的 Imperative Programming. 关于前者还有篇科普, 里面对这种"Quantum data, classical control"的方式有很清楚的说明, 还给出了他们实现的几个 non-trivial 的量子算法:
推荐阅读
![[聪明的人财]毛利哥：RCS概念回调勇敢买入！必有大机会！](https://imgcdn.toutiaoyule.com/20200412/20200412055032109602a_t.jpeg)
- 王者荣耀李白能不能出肉
- 大三学生准备日本留学过程中要不要准备考研
- 工作3、4的人怎样转行当警察
- 游戏中有哪些让人感动的情节
- 华威大学计算机本科咋样
- 为啥没人做好KTV的UI
- 为啥现在没有一家信用评级系统的公司
- 上海或苏州有没有比较好的大数据培训机构
- 纸质书籍还有生存的余地没
- 30岁的人生，想自学一门编程并从事，这个选择怎样呢