PDF《北京大学》

- I - 北京大学 本科生毕业论文题目: 置换的量子线路复杂性 Quantum Circuit Complexity of Permutation 姓名: 洪柳学号:

00008073 院系: 信息科学技术学院 专业: 计算机科学与技术 指导老师: 刘旭峰-I- 摘要 量子计算机是建立在量子力学基础上的新一代计算机.

与经典计算机相比, 它有许多特殊的优越性,因而具有广阔的发展前景.目前,量子计算机方面的 研究工作非常活跃,而关于酉变换的量子线路实现复杂性是一个重要的研究方 向.本文给出了置换变换(酉变换的子群)的量子线路实现复杂性方面的一些 结果. 我们首先介绍了量子计算机的基本知识以及量子计算复杂性理论,然后着 重讨论置换变换的量子线路实现复杂性.我们给出一些置换变换多项式可实现 的判定定理;

论证对称群 2n S 不是多项式可实现的;

分析了顺序轮换的量子线路 实现及其复杂性.最后,总结全文并对量子计算机的发展作了展望. 关键字:量子计算机,量子线路,量子逻辑门,量子计算复杂性,置换变换 Abstract - II- Quantum Circuit Complexity of Permutation Abstract Quantum computer is a new generation of computer based on quantum mechanics. It has many advantages over classical computer and owns a bright future. Nowadays the research on quantum computer is active. And the quantum circuit complexity of unitary transformation is an important aspect. In this thesis, we derive some results on the quantum circuit complexity of permutation, which is a subgroup of unitary group. Firstly we review the basic knowledge of quantum computer and the theory of quantum computational complexity. Then we focus on the quantum circuit complexity of permutation, presenting some theorems on it. We prove that the symmetry group 2n S can not be implemented by polynomially many basic quantum logic gates. We analyze the quantum circuit complexity of ordered cyclic permutation. Finally we make some concluding remarks and some comments on the development of quantum computer. Key words:quantum computer, quantum circuit,quantum logic gate, quantum computational complexity,permutation transformation 符号表 - III- 符号表

2 ( ) i (i 的二进制表示) ? (右矢) ( ) i x ? ? (有i个控制位的 C-NOT 门) 1( ) n x ? ? ? (广义 1( ) n x ? ? ? 门) (2) U (二阶酉矩阵) U ? (U 的共轭转置算符) A B ? (A 和B的直积) ( ) Poly n (n 的多项式) ( ) Exp n (n 的指数) (2 ) n P (作用在2n 个元素上的置换) 2n S (2n 阶对称群) x S? (只由 x ? 门生成的置换集合) (1,2,3, ,2 1,2 ) n n ? ? (含2n 个元素的置换) ( ( )) O Poly n (函数的上界为 n 的多项式) 目录 -1- 目录 摘要 I Abstract II 符号表 III 目录

1

第一章 引言

3 1.1 量子计算机

3 1.1.1 量子计算机概论

3 1.1.2 量子计算机特点

3 1.1.3 量子计算机优越性

4 1.2 计算的可逆性

5 1.2.1 不可逆计算

5 1.2.2 可逆计算

6

第二章 量子计算复杂性

7 2.1 量子图灵机

7 2.2 量子线路模型

8 2.3 量子计算复杂性

9

第三章 量子逻辑门

10 3.1 通用量子逻辑门

10 3.2 单比特量子逻辑门

10 3.2.1 一般的单比特量子逻辑门

10 3.2.2 特殊的单比特量子逻辑门

11 3.3 C-NOT 门.11

第四章 置换的量子线路实现及其复杂性.15 4.1 数学准备

15 4.2 任意对换的实现

15 目录 -2- 4.3 (2 ) n P 多项式可实现的判定.17 4.3.1 基本门实现 (2 ) n P

17 4.3.2 广义 1( ) n x ? ? ? 门实现 (2 ) n P

18 4.3.3 x ? 门和 1( ) n x ? ? ? 门实现 (2 ) n P

19 4.4 2n S 不是多项式可生成的.19 4.5 一类顺序轮换的实现

20

第五章 结论及展望

24 5.1 结论及进一步的工作

24 5.2 展望

25 参考文献

26 致谢

29 附录 A 量子力学简介.30 附录 B 计算复杂性理论概要

32 附录 C 网络资源.34 索引

35

第一章 引言 -3-

第一章 引言 1.1 量子计算机 1.1.1 量子计算机概论 迄今为止,在实际中使用的各种不同类型的计算机,都是以经典物理学作 为理论基础的, 称为经典计算机. 从1946 年第一台电子计算机 ENIAC 问世算起, 经典计算机在短短五十年间取得了巨大的成就.然而辉煌的背后,经典计算机 发展的矛盾也越来越突出.根据 Moore 定律[Mal95] ,计算机芯片的集成化程 度每

18 个月增长一倍.按照这个趋势,到2020 年左右,器件将发展到单个原 子的尺度.那时,经典物理规律将不再适用,经典计算机将无法工作.因此便 需要开发工作原理建立在量子力学基础上的计算机,即量子计算机. 那么量子计算机应当是什么样呢? S. Lloyd 给出了一个通用标准[Llo96]: ① 可以设定计算机的初态,而不需要事先知道计算结果. ② 计算机体系按照它内部的动力学过程将初态演化为输出,这个内部的动 力学过程在计算机制造时给定. ③ 可以依靠测量从计算机中提取计算结果. 1.1.2 量子计算机特点 与经典计算机相比,量子计算机有如下主要特点: (1)叠加性 在经典计算机中,含n个数据位的存储器只能存储一个 n 位的二进制数, 而量子存储器则能同时存储2n 个n位二进制数;

在经典计算机中,每次操作只 能对一个 n 位二进制数进行处理,而量子计算机则能同时对2n 个n位二进制数 进行处理.由于量子叠加态的存在,不仅大大提高了量子计算的效率,而且实 现了连续变量和真正意义上的并行计算. 虽然经典计算机也可以利用并行性来减少计算所需要的时间,例如现在广 泛采用的多 CPU 并行计算和网络并行计算等等.但若要使计算时间呈指数级地 下降,则需要指数级地增加所用的物理资源.而在量子计算机中,只需要物理 资源的线性增加,就可使并行量呈指数级地提高,这就是量子并行和经典并行 的根本区别.

第一章 引言 -4- (2)干涉性 对于有 n 个位的量子计算机,其状态可以表示为

1 0 n i i c i ? ? ? ? ? .这种叠加不 是简单的概率相加,而是概率幅相加.由于量子态之间可能存在相位差,所以 在演化过程中会出现干涉相长或干涉相消,这是经典布尔态所不具备的.干涉 性在量子算法中常常被用到. (3)纠缠性 量子体系不同部分间可能存在着量子纠缠.量子纠缠是一种没有经典对应 的纯量子效应,在量子通信中具有重要地位. (4)不可克隆性

1982 年,Wootters 和Zurek 证明[WZ82]:由于态叠加原理和态的演化遵 循幺正变换,使得任何量子体系的任意未知量子态无法被精确复制.也即无法 在不破坏原来未知态的情况下对之进行观察和测量,这就是量子不可克隆定理. 量子不可克隆定理是进行量子密码通信的理论基础. 1.1.3 量子计算机优越性 (1)量子模拟

1982 年,Feynman 研究表明[Fey82] ,经典计算机不能有效模拟量子体系. 他猜想,可以利用量子计算机来模拟一切局域量子系统.这一猜想,在1996 年由Lloyd 得到证实 [Llo96].Lloyd 进一步指出,大约需要几百至几千个量子 比特,就可精确地模拟一些具有连续变量的量子系统.因此,一旦有了量子计 算机,就不必通过求解薛定谔方程或是采用蒙特卡罗方法做数值运算,即可精 确地研究量子体系的特性. (2)量子算法 量子力学的许多特性,诸如叠加性,纠缠性,并行性,测量塌缩等等,为 计算效率的提高带来了极大的帮助,形成了一种崭新的计算模式DD量子算法. 量子算法的出现对经典计算理论产生了重大的影响.

1994 年,Peter Shor 利用量子纠缠性和叠加性提出了著名的大数因子分解 的量子算法[Sho94] .Shor 算法在多项式时间内解决了经典计算中的 NP 问题, 是对经典算法的指数级加速,使得公开的 RSA 密钥系统受到巨大的挑战,激发 了人们研究量子计算机的高潮. 后来,又有一大类与经典算法相比有指数级加速的量子算法被提出,统称

第一章 引言 -5- 为量子黑箱问题算法.黑箱是可以执行某种计算任务的一段程序,为它制备一 个输入后,则测量输出可以得到计算结果.如果以黑箱被运行的次数作为计算 复杂性考虑的对象,那么可以证明,供给量子黑箱叠加态的输入比供给经典的 输入有指数级的加速.比较著名的量子黑箱问题算法有:Deutsch-Jozsa 问题算 法[DJ92], Bernstein-Vazirani 问题算法[BV93], Simon 问题算法[Sim94]等等.

1996 年,Grover 提出了在无序库中搜索满足特定条件项目的量子算法 [Gro96] ,使得从未经排序的 n 个数据中搜索一个特定数据只需要 ( ) O n 次运 算;

而利用经典计算机平均需要

2 n 次运算. 但是,量子算法也不是万能的.对于某些问题则不存在量子加速,例如迭代 问题和宇称问题等. 1.2 计算的可逆性 1.2.1 不可逆计算 经典计算机中的信息处理是通过逻辑门来实现的.19 世纪 George Boole 证 明了任何复杂的逻辑任务和算术任务都可以通过 NOT , AND 和 COPY 这 三种简单操作的组合来完成. 逻辑门 真值表 NOT 门AND 门COPY 门 经典计算机中的逻辑门操作一般都是不可逆的. 例如对两个比特进行 AND 操作,只有一个输出比特带有有用的信息,而另一个比特的信息被丢弃.为了 以后的使用,这个比特要复原到标准态,如

0 .由于在复原过程中不知道这

第一章 引言 -6- 个比特的初始信息,故是一个不可逆的操作.按照热力学定律,将会产生一定 热量,这就是能耗的来源.20 世纪

60 年代,IBM 公司的 R. Landauer 提出了 Landauer 原理[Lan61]:假设计算机擦除一个比特的信息,则散发到环境中的能 量至少是 ln

2 B k T ,其中 B k 是Boltzman 常数,T 是环境温度.Landauer 原理实 际上给出了不可逆计算的能耗下限.在2000 年左右,经典计算机每个逻辑运算 大概消耗的能量为500 ln

2 B k T ,远远大于已知的下限.不可逆计算引起的能耗问 题已成为制约经典计算机发展的主要瓶颈之一. 1.2.2 可逆计算 不可逆计算并非是不可避免的.Landauer 认为[Ben88],只要消除计算过程 中的不可逆操作,则从物理上讲,不存在计算的能耗下限.这就引发了对可逆 计算的研究热情.

20 世纪

70 年代,C. H. Bennett 严格证明了[Ben73],所有的经典不可逆 图灵机都可以改造成可逆图灵机,而且不影响计算能力.这样只要在计算的最 后抄下结果, 并将计算机反向运转, 就可从输出可逆地返回到原始输入. Bennett 的研究为可逆计算机打下了理论基础. 接着,许多物理学家着手研究可逆计算机的物理实现方案[Tof80][FT82]. Toffoli 讨论了如何用可逆门来实现传统的布尔运算[Tof80],并给出了一个通 用的三比特可逆门DDToffoli 门. 事实上任意通用的可逆布尔逻辑门至少有三 比特. 逻辑门 真值表 Toffoli 门 在量子计算中,由于操作是幺正变换,所以量子逻辑门都是可逆的,进而 量子计算机也是可逆的.这样在物理上,对量子计算的能耗没有下限要求.

第二章 量子计算复杂性 -7-

第二章 量子计算复杂性 2.1 量子图灵机 计算在本质上是由一定的输入按照确定的规则进行操作得到输出的过程. 经典计算机的可计算理论是建立在著名的丘奇―图灵论题上的[Tur36][Chu36].该论题声称:直觉可计算 = 图灵机可计算 = 递归可计算. 丘奇―图灵论题指出了人类计算能力的极限,它断言任何直觉上可计算的东西 都可以用图灵机来计算;

而不能用图灵机计算的都是不可计算问题. 计算机中进行的计算在本质上是一个物理过程.David Deutsch 在详细考察 了丘奇―图灵论题后,将其表述为如下的物理原理[Deu85]: 任何有限的可实现 的物理系统必能被一个包含有限操作的通用计算模型所精确地模拟.换言之, 每个物理规律必能被可计算的函数类表达;

而进入物理学的也必须是可计算函 数.Deutsch 所谓的具有有限操作的计算模型不可能是经典图灵机,因为经典图 灵机是离散的,而现实物理中的态空间是连续的.只有量子图灵机才有可能满 足要求.

1980 年,Paul Benioff 提出了量子图灵机的概念[Ben80][Ben82].1985 年,David Deutsch 给出了第一个真正的通用量子图灵机的具体模型[Deu85]. Deutsch 的量子图灵机主要包括两部分[GGZ97]: ① 具有有限内部状态的处理器.假设该处理器由 M 个二能级系统构成,相 应的本征值为 ( 1,2, , 1) i n i M ? ? ? .为了标志处理器所处的状态,设定可观测量 X,它的本征值是任意整数. ② 无限长的存储单元序列.每个单元是一个二能级系统,整个存储单元的 状态用所有二能级体系的观测量集合来描述,记为 M. 再增加一个可观测量

0 n ,计算开始时

0 0 n ? ,结束时

0 1 n ? .这样量子图灵 机的状态就可以表示为

0 1

1 0

1 M x n m x n n m m m ? ? ? ? ? ? ? ?? ? ? ? ,而体系的 演化则可用幺正算符 U 描述为 ( ) (0) n nT U n Z UU I U U I ? ? ? ? ? ? ? ? ? . 值 得注意的是体系在初始时刻有

0 x=0,n

0 ? .存储单元中存放的计算程序,用计算 基表示为

2 (0) 0;

0;

,

1 m m m m m ? ? ? ? ? ? ? ,即体系是处于叠加态上的.存储单 元和处理器均可处于叠加态上. 通用量子图灵机的一个特点是它能以任意高的精度进行计算,但不能实现

第二章 量子计算复杂性 -8- 完全的精确计算,原因在于它只含有限个操作.Deutsch 指出[Deu85],除了经 典图灵机的操作外,通用量子图灵机还具有八个操作,................