臺灣博碩士論文加值系統

可逆電路是量子計算中是重要的研究領域之一，而目前關注的是若給定一個可逆
電路的輸出規格，如何自動化合可逆電路成並在最快的時間內找到成本最低的可逆電
路，本研究內容提出一個基於量子啟發式禁忌搜尋演算法應用於自動化合成可逆電路
的方法。可逆電路合成可視為組合最佳化問題，我們可以利用量子啟發式禁忌搜尋演
算法由深而廣搜尋方式找到邏輯閘個數較少的可逆電路，換句話說就是能找到接近最
佳解或就是最佳解的可逆電路。此外，將本研究合成的可逆電路邏輯閘數量與其他啟
發式、演化式演算法進行實驗數據的比較，結果顯示本研究提出基於量子啟發式禁忌
搜尋演算法的方法用於求解可逆電路合成問題可以得到不錯的結果。

Quantum reversible logic plays an important role in the quantum computation which
is one of the most promising research fields. The problem of reversible logic synthesis is
concerned with the ability to generate a reversible circuit given a reversible function
automatically. In this paper, a new synthesis technique for synthesis of reversible circuits
based on Quantum-Inspired Tabu Search Algorithm (QTS) has been proposed. Synthesis
of reversible logic circuits is formulated as a combinatorial optimization problem. In our
algorithm, QTSbased approach which is used to find fewer gates to the reversible function
output. Furthermore, the results of experiment are also compared with the other heuristic
algorithm experimental results. The final outcome shows that the QTS-based approach
performs much better than the other algorithms.

誌謝 I
摘要 II
Abstract III
目錄 IV
List of Figures VI
List of Tables VII
Chapter 1 Introduction 1
Chapter 2 Relative Work 2
Chapter 3 Background 3
3.1 Reversible gates 3
3.2 Reversible circuits 4
3.3 Quantum-Inspired Tabu Search Algorithm 6
Chapter 4 Methodology 7
4.1 Encode 7
4.2 QTS Algorithm for Synthesis of Reversible Logic Circuits 8
4.3 Initialize quantum population 9
4.4 Termination condition 10
4.5 Produce solutions 10
4.6 Repair solutions 11
4.7 Evaluate solutions 12
4.8 Update quantum bits 13
Chapter 5 Experimental result 15
Chapter 6 Conclusion 20
Reference 21

21
Reference
[1] R. Landauer, “Irreversibility and heat generation in the computing process,” IBM J.
Research & Development, vol. 5, no. 3, pp. 183–191,July 1961.
[2] C. Bennett, “Logical reversibility of computation,” IBM J. Research &
Development, vol. 17, no. 6, pp. 525–532, Nov. 1973.
[3] Y. H. Chou, C. H. Chiu, and Y.J. Yang. “Quantum-inspired tabu search algorithm
for solving 0/1 knapsack problems, ” annual conference companion on Genetic and
evolutionary computation, pp.55-56, 2011.
[4] D. Maslov, G. W. Dueck, and D. M. Miller, “Toffoli network synthesis with
templates,” IEEE Transactions on Computer-Aided Design, vol. 24, no. 6, pp.
807–817, 2005.
[5] I. M. Tsai and S. Y. Kuo, “An algorithm for minimum space quantum Boolean
circuits construction,” J. Circuits, Syst., Comput., vol. 15, no. 5, pp. 719–738, Oct.
2006.
[6] M. Li, Y. Zheng, M. Hsiao, and C. Huang, “Reversible logic synthesis through ant
colony optimization, ” in Proc. Conf. Design, Automation and Test in Europe, Mar.
2010.
[7] M. Zhang, S. Zhao, and X. Wang, “Automatic synthesis of reversible logic circuit
based on genetic algorithm,” IIEEE International Conference on Intelligent
Computing and Intelligent Systems, pp. 542 – 546, Nov. 2009.
[8] V. V. Shende, A. K. Prasad, I. L.Markov, and J. P. Hayes. “Synthesis of reversible
logic circuits,” IEEE Transactions on Computer Aided Design, vol.22, no.6,
pp.710-722, 2003. [9] P. Gupta, A. Agrawal, and N.K. Jha. “An algorithm for synthesis of reversible
logic circuits,” IEEE Transactions on Computer-Aided Design, vol.25, no.11,
pp.2317–2330, Nov. 2006.
[10] M. Saeedi, M. S. Zamani, and M. Sedighi, “Moving forward: A nonsearch based
synthesis method toward efficient CNOT-based quantum circuit synthesis
algorithms,” Asia and South Pacific Design Automation Conference, pp. 83–88,
Jan. 2008
[11] O. Golubitsky, S. M. Falconer, and D. Maslov, “Synthesis of the Optimal 4-bit
Reversible Circuits,” Design Automation Conference, pp. 653-656. 2010
[12] D. Maslov. Reversible logic synthesis benchmarks page.
http://webhome.cs.uvic.ca/˜dmaslov/