量子啟發式禁忌搜尋演算法求解可逆電路合成問題

Synthesis of Reversible Logic Circuits Through Quantum-Inspired Tabu Search Algorithm

王雯欣(Wen-Hsin Wang)

指導教授 ： 周耀新

國立暨南國際大學/科技學院/資訊工程學系/碩士(2011年)

摘要

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

關鍵字

量子計算 ； 可逆計算 ； 可逆電路合成

並列摘要

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.

並列關鍵字

quantum computing ； reversible computing ； reversible circuits synthesis.

參考文獻

[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.