基于改进遗传算法的量子可逆电路综合

J4 ›› 2017, Vol. 34 ›› Issue (2): 192-202.

基于改进遗传算法的量子可逆电路综合

胡江,张巧文,王阳

浙江万里学院

收稿日期:2015-12-22 修回日期:2016-03-07 出版日期:2017-03-28 发布日期:2017-04-06
通讯作者: 胡江

Improved Genetic Algorithm for Quantum Reversible Circuits Synthesis

Received:2015-12-22 Revised:2016-03-07 Published:2017-03-28 Online:2017-04-06

摘要/Abstract

摘要： 针对可逆电路到量子电路的有效映射问题，提出带禁忌表的大变异自适应遗传算法及其量子可逆电路综合方法。该文选取量子非门、控制非门、控制V门与控制V+门（NCV）构成量子门库，建立量子电路计算模型，采用二进制串行编码方案，设计适应度函数、进化算子及优化规则，实现带禁忌表的大变异自适应遗传算法的量子可逆电路综合，并利用Revlib电路库进行测试。测试结果表明，该综合方法能同时得到多个功能解，且所生成电路的量子代价优于库中电路，验证了算法用于量子可逆电路综合的正确性和有效性。

关键词: 量子电路, 可逆逻辑综合, 大变异自适应遗传算法, 禁忌表, quantum circuits, reversible logic synthesis, big mutation adaptive genetic algorithm, tabu list

Abstract: In order to efficiently map reversible circuits to quantum circuits, a big mutation adaptive genetic algorithm with tabu list was proposed for quantum reversible circuits synthesis. The calculation model of quantum circuits was established. The generic coding scheme of reversible circuits, the design of fitness function and the operation of evolution operators were given. Using benchmarks in Revlib for testing the new synthesis method, the experimental results show that the synthesis method could simultaneously obtain multiple solutions and the quantum costs of the synthesized circuits were less than the circuits in Revlib.

中图分类号:

TN79+1

胡江张巧文王阳. 基于改进遗传算法的量子可逆电路综合[J]. J4, 2017, 34(2): 192-202.

参考文献

[1] Barends R, Kelly J, Megrant A, et al. Superconducting quantum circuits at the surface code threshold for fault tolerance[J]. Nature, 2014, 508(7497): 500-503.
[2] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM journal on computing, 1997, 26(5): 1484-1509.
[3] Pedrocchi F L. Spin Systems and Long-Range Interactions for Quantum Memories and Quantum Computing[D].[Doctor],University of Basel,German,2013.
[4] Soeken M, Wille R, Hilken C, et al. Synthesis of reversible circuits with minimal lines for large functions[C].Design Automation Conference (ASP-DAC), 2012 17th Asia and South Pacific. IEEE, 2012: 85-92.
[5] Maslov D, Saeedi M. Reversible circuit optimization via leaving the Boolean domain[J]. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 2011, 30(6): 806-816.
[6] Gupta P, Agrawal A, Jha N K. An algorithm for synthesis of reversible logic circuits[J]. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 2006, 25(11): 2317-2330.
[7] Bandyopadhyay C, Roy S J, Biswal L, et al. Synthesis of ESOP-based reversible logic using negative polarity reed-muller form[C].Students' Technology Symposium (TechSym), 2014 IEEE. IEEE, 2014: 286-291.
[8] Ruican C, Udrescu M, Prodan L, et al. A Genetic Algorithm Framework Applied to Quantum Circuit Synthesis[M].Nature Inspired Cooperative Strategies for Optimization (NICSO 2007). Springer Berlin Heidelberg, 2008: 419-429.
[9] Wang You-ren, Huang Yuan-yuan,Feng Ran,et al. Evolutionary Design Technology of Quantum Reversible Logic Circuit Based on Matrix Coding[J]. Acta Electronica Sinica, 2012, 39(11): 2576-2582.
[10] Fan Fu-you, Yang Guo-wu, Le Qian-qi, et al.A surry of the research on multi-valued quantum circuits[C]. Wavelet Active Media Technology and Information Processing (ICWAMTIP), Chengdu:China,2012:338-341.
[11] Wille R, Soeken M, Otterstedt C, et al. Improving the mapping of reversible circuits to quantum circuits using multiple target lines[C].ASP-DAC. 2013: 145-150.
[12] Shafaei A, Saeedi M, Pedram M.Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures[C].Proceedings of the 50th Annual Design Automation Conference. ACM, 2013: 41-46.
[13] Li Zhi-qiang, Chen Han-wu,Liu Wen-jie, et al. Efficient Algorithm for Synthesis of Optimal NCV 3-Qubit Reversible Circuits Using New Quantum Logic Gate Library[J]. Acta Electronica Sinica,2013, 41(4): 690-697.
[14] Héctor J. Garcia, Igor L. Markov. Quipu: High-performance simulation of quantum circuits using stabilizer frames[C]. International Conference on Computer Design, ICCD, Asheville:USA,2013:404-410.
[15] Banerjee A. Synthesis, optimization and testing of reversible and quantum circuits[D]. [Doctor],Jaypee Institute of Information Technology,India,2011.
[16] Soeken M, Frehse S, Wille R, et al. RevKit: an open source toolkit for the design of reversible circuits[M].Reversible Computation. Springer Berlin Heidelberg, 2012: 64-76.