臺灣博碩士論文加值系統

對於量子電腦而言，量子布林電路的合成是一個基本目標。此外，
使用n 3 的n位元「托佛利」閘建構一個量子電路似乎是不切實際也不
符合經濟效益的。於此論文中，我們介紹一個使用僅含「非」、「控
制非」和「托佛利」等閘之閘元件庫來合成任何組合量子布林電路的
啟發式演算法。
我們的演算法主要是採用基本連結規則與次要連結規則來簡化電
路。此外，在簡化過程中，我們也提出一選擇成本較低路徑的方法。
最後，我們再提出一方法，其分析化簡後之電路並找出共同項，以進
一步地降低電路成本。於本文中，我們使用一些例子並配合卡諾夫圖
呈現來說明我們的演算法。

For a quantum computer, the synthesis of quantum Boolean circuits is
an essential aim. In addition, it seems that constructing a circuit with an
n-bit Toffoli gatewith n 3 is neither practical nor economical. In this
paper, we introduce a heuristic algorithm for synthesizing any
combinational quantum Boolean circuit with a gate library containing only
Not, CNot and Toffoli gates.
Our algorithm mainly adopts the primary linking rule and secondary
linking rule to simplify a circuit. Moreover, we propose a method for
selecting a path with lower cost during the simplification process. Finally,
we propose another method, which analyzes the simplified circuit and finds
out common terms, to further reduce the circuit cost. In the context, we
employ some examples, in company with the Karnaugh map presentation,
to explain our algorithm.

摘要
ABSTRACT
致謝
目錄
圖目錄
表目錄

第一章 緒論
1.1 簡介
1.2 研究動機與背景
1.3 研究方法
1.4 文獻探討
1.5 論文架構

第二章 背景知識
2.1 量子計算概論
2.2 量子位元
2.3 量子讀寫
2.4 量子運算
2.5 量子平行性
2.6 量子容錯計算
2.7 量子電腦問題複雜度

第三章 量子電路邏輯與量子電路
3.1 量子邏輯
3.2 量子卡諾夫圖
3.3 連結規則
3.4 量子閘
3.5 量子電路成本

第四章 量子電路縮減法
4.1 演算法概述
4.2 尋找化簡項
4.3 使用連結規則
4.4 低成本實現電路

第五章 模擬程式
5.1 QCAD 模擬器
5.1.1 EPS 檔案格式
5.1.2 執行結果
5.2 資料結構

第六章 結果與討論

參考文獻

[1] P. W. Shor, “Polynomial-time algorithm for prime factorization and
discrete logarithms on a quantum computer, “ SIAM J. Computing, vol. 26,
no. 5, pp. 1484-1509, Oct. 1997.
[2] L. K. Grover, “A fast quantum mechanical algorithm for database
search,” Proc. Of the 28th Annual ACM Symp. Theory of Computing
(STOC), pp. 212-221, 1996.
[3] A. Yao, “Quantum circuit complexity, “Proc. of the 34th Annual IEEE
Symp. Foundations of Computer Science, pp. 352-361, 1993.
[4] T. Toofoli, “Reversible computing, automata, languages, and
programming,” Springer-Verlag, pp. 632-644, 1980.
[5] J. Lee, Y. Cheong, J. Kim, and S. Lee, “A practical method of
constructing quantum combinational logic circuits,”
http://arXiv.org/quant-ph/9911053, 1999
[6] S. A. Wang, C. Y. Lu, I. M. Tsai, and S. Y. Kuo, “Modified karnaugh
map for quantum Boolean circuits construction,” Proc. 2003 IEEE Conf.
Nanotechnology, pp.651-654, 2003

[7] A. Younes and J. Miller, “Representation of Moolean quantum circuits
as Reed-Muller expansions,” http://arXiv.org/quant-ph/0305134, 2003.
[8] A. E. A. Almaini, Electronic logic systems, Second edition,
Prentice-Hall, 1989.
[9] G. Bioul, M. Davio, and J. P. Deschamps, “Minimization of ring-sum
expansions of Boolean functions,” Philips Research Report, vol, 28, no. 2.
pp. 17-36, 1973.
[10] M. H. Miessler, “Use of Exclusive-Or gates for Boolean
minimization,” Proc. the IEE, vol. 119, no. 9, pp. 1269-1272, Sep. 1972.
[11] G. Papakonstantinou, “Minimization of modulo-2 sum of products,”
IEEE Trans. Computers, vol. 28, no. 2 pp. 163-167, Feb. 1979.
[12] S. Even, I. Kohavi, and A. Paz, “On minimal modulo-2 sum of
products for switching functions,” IEEE Trans. Electronic Computers, vol.
16, pp. 671-674, Oct. 1967.
[13] H. Fleisher, M. Tavel, and J. Yeager, “Exclusive-OR representation of
Boolean functions,” IBM J. Research and Development, vol. 27, pp.
412-416, July 1983.

[14] H. Fleisher, M. Tavel, and J. Yeager, “A computer algorithm for
minimizing Reed-Muller canonical forms,” IEEE Trans. Computers, vol.
36, no. 2, pp. 247-250, Feb. 1987.
[15] J. M. Saul, “An improved algorithm for the minimization of mixed
polarity Reed-Muller representation,” Proc. IEEE Int’l Conf. Computer
Design, pp. 372-375, Sep. 1990.
[16] M. Helliwell and M. Perkowski, “A fast algorithm to minimize mixed
polarity generalized Reed-Muller forms,” Proc. ACM/IEEE Design
Automation Conference, pp. 427-432, 1988.
[17] Alan Mishchenko and Marek Perkowski, “Fast Heuristic Minimization
of Exclusive-Sums-of- Products,”5th Int’l Reed-Muller Workshop, pp.
242–250, Aug. 2001.
[18] http://acolyte.t.u-tokyo.ac.jp/~kaityo/qcad/