[1]薛希玲,陈汉武,陈开中,等.基于BDD的Grover算法仿真[J].东南大学学报(自然科学版),2009,39(1):28-33.[doi:10.3969/j.issn.1001-0505.2009.01.006]
　Xue Xiling,Chen Hanwu,Chen Kaizhong,et al.BDD based simulation of Grover’s algorithm[J].Journal of Southeast University (Natural Science Edition),2009,39(1):28-33.[doi:10.3969/j.issn.1001-0505.2009.01.006]
点击复制

基于BDD的Grover算法仿真()
分享到：

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
39
期数:
2009年第1期
页码:
28-33
栏目:
计算机科学与工程
出版日期:
2009-01-20

文章信息/Info

Title:
BDD based simulation of Grover’s algorithm
作者:
薛希玲1;  陈汉武1;  陈开中1;  李志强1; 2
1 东南大学计算机科学与工程学院, 南京 210096; 2 扬州大学信息工程学院, 扬州 225009
Author(s):
Xue Xiling1;  Chen Hanwu1;  Chen Kaizhong1;  Li Zhiqiang1; 2
1 School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2 College of Information Engineering, Yangzhou University, Yangzhou 225009, China
关键词:
量子算法;  Grover算法仿真;  二项决策图;  Grover迭代
Keywords:
quantum algorithm;  simulation of Grover’s algorithm;  binary decision diagram;  Grover iteration
分类号:
TP387
DOI:
10.3969/j.issn.1001-0505.2009.01.006
摘要:
为了解决仿真量子计算过程中复杂性随量子比特数的增加呈指数级递增的问题,采用二项决策图(BDD)表示矩阵算子仿真Grover提出的量子搜索算法.BDD利用矩阵算子在量子计算过程中呈现出的结构化特性,可以高效地压缩存储空间并实现在压缩数据结构上直接进行矩阵的各种运算.利用改进的BDD实现了仿真过程需要的各种矩阵运算,用C++编写的程序对Grover算法的实例进行仿真,最后从多个角度对违反直观的实验结果进行了分析,阐述了量子算法的内在并行性.
Abstract:
Simulating quantum algorithms on classical computer is difficult, for the matrices representing quantum gates and the vectors modeling qubit states grow exponentially with the increase in the number of qubits. In this paper, binary decision diagram(BDD),which exploits the structure displayed in quantum computing, is adopted to simulate Grover’s algorithm. First the original BDD is adapted to implement a series of algorithms such as matrix multiplication to represent and manipulate matrices and vectors. Then instances of Grover’s algorithm are simulated with our programme written in C++. Finally an intensive analysis of the counter-intuitive experimental results in quantum mechanism is presented from multiple points of view, which may help understand the inner parallelism of quantum algorithms.

参考文献/References:

[1] Keyes R W.After the transistor,the qubit? [J]. Computing Science & Engineering,2005,7(1):36-41.
[2] Grover L K.Quantum mechanics helps in searching for a needle in a haystack [J]. Physical Review Letters,1997,79(2):325-328.
[3] Karafyllidis I G.Quantum computer simulator based on the circuit model of quantum computation [J].IEEE Transactions on Circuits and Systems,2005,52(8):1590-1596.
[4] Viamontes G F.Gate-level simulation of quantum circuits [EB/OL].(2002-08-01)[2008-05-06].http://arxiv.org/abs/quant-ph/0208003v1.
[5] Viamontes G F.Improving gate-level simulation of quantum circuits[J]. Quantum Information Processing,2003,2(5):347-380.
[6] Bryant R E.Graph-based algorithms for Boolean function manipulation [J]. IEEE Trans on Computers,1986,35(8):677-691.
[7] Fujita M,McGeer P,Yang J-Y,et al.Multi-terminal binary decision diagrams:an efficient data structure for matrix representation [J]. Formal Methods in System Design,1997,10(2/3):149-169.
[8] Bahar B I,Frohm E A,Gaona C M,et al.Algebraic decision diagrams and their applications [J].Formal Methods in System Design,1997,10(2/3):171-206.
[9] Miller D M,Thornton M A.QMDD:a decision diagram structure for reversible and quantum circuits [C] //IEEE Proceedings of the 36th International Symposium on Multiple-Valued Logic.Singapore,2006:30-30.
[10] Miller D M,Thornton M A.A decision diagram package for reversible and quantum circuit simulation [C] //IEEE Congress on Evolutionary Computation.Vancouver,Canada,2006:2428-2435.
[11] Warren P,Grant P M.The future of computing new architectures and new technologies [C] //IEE Proceedings Nanobiotechnology.Ipswich,UK,2004:1-9.
[12] Boyer M.Tight bounds on quantum searching [R].Denmark:University of Southern Denmark,1996.
[13] Nielsen M A,Chuang L.Quantum computation and quantum information [M].北京:高等教育出版社,2003:248-255.
[14] Lanzagorta M,Uhlmann J K.Hybrid quantum-classical computing with application to computer graphics [R].California:ACM,2005.

备注/Memo

备注/Memo:
作者简介: 薛希玲(1985—),女,硕士生; 陈汉武(联系人),男,博士,教授,博士生导师,hw_chen@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60572071, 60873101)、江苏省自然科学基金资助项目(BK2005053, BM2006504, BK2007104, BK2008209)、江苏省高校自然科学基金资助项目(06KJB520137).
引文格式: 薛希玲,陈汉武,陈开中,等.基于BDD的Grover算法仿真[J].东南大学学报:自然科学版,2009,39(1):28-33.
更新日期/Last Update: 2009-01-20