可逆電路合成與多值量子電路驗證

Reversible Circuit Synthesis and Multiple-Valued Quantum Circuit Verification

盧勤庸(Chin-Yung Lu)

指導教授 ： 郭斯彥

國立臺灣大學/電機資訊學院/電子工程學研究所/博士(2010年)

https://doi.org/10.6342/NTU.2010.02636

摘要

可逆電路已經被應用在許多領域上面，例如：數位信號處理、低功率電路設計和量子計算。如果一個電路是可逆的，則它可以降低因為訊息損失所造成的功率消耗。對於組合邏輯電路而言，卡諾圖這個方法比其他電路化簡方法，能夠更快並且更容易化簡電路，但是傳統的卡諾圖方法是無法直接應用在可逆電路的化簡工作上，這是因為在基本邏輯閘中，除了NOT閘之外，都不是可逆的邏輯閘，在這篇博士論文中，我們提出了一個方法可以解決這個問題，使得卡諾圖化簡方法可以應用在可逆電路的合成工作上，所以我們的合成演算法提供了一種系統化方法，可以化簡可逆電路。這種方法能夠產生以互斥和形式表示的式子，這個式子可以轉換為具有較低量子成本的最終可逆電路。此外，我們可以把置換電路合成為可逆電路，這種可逆電路具有較低量子成本並且沒有不必要的無用量子位元，我們也可以轉換不可逆電路變成可逆電路，只需要加入量子位元到電路中。實驗結果證明：和以前的方法比較，平均可以節省15.82％的量子成本。
到目前為止，除了窮舉演算法之外，沒有其他合成演算法可以找到所有的最佳化可逆電路。我們提出了一種方法，這是基於分割後分別處理的方式，可以顯著改善已發表合成演算法的性能，並且合成所需要的可逆電路。一個可逆電路首先分割成兩個子電路，較小子電路輸入m個邏輯閘的所有可能組合，對於具有相同函數的組合，只有具有最少邏輯閘的組合才會被輸入到這個子電路中，另一個子電路可以用已發表的合成演算法執行電路合成，然後這兩個子電路合併成完整的可逆電路，在所有可能的合成結果中，我們選擇一個最簡單的可逆電路當成最後的結果，根據所有3變數可逆電路的實驗結果，我們可以發現：使用我們的方法，可以顯著改善已發表合成演算法的性能，因此我們所合成的可逆電路會比以前結果更簡化。
此外，為了有效地表示量子操作功能，我們提出 X-分解量子決策圖（XQDD），XQDD可以容易地執行矩陣運算，並且XQDD可以用來驗證量子電路和可逆電路的功能，即使可逆電路具有不同數目的無用量子位元，我們也可以驗證它們的功能，對於記憶空間和使用時間而言，這是更有效的表示方式。我們把原來的XQDD表示方式擴展到多值量子邏輯，擴展的XQDD表示方式可以表示多值量子操作和執行矩陣運算，它可以用在驗證兩個多值量子電路或可逆電路是否相等，而且這些電路可用不同的方法合成得到的。根據模擬的結果，對於使用時間而言，擴展的XQDD表示方式明顯優於多值QuIDD表示方式，並且非常接近QMDD表示方式，此外我們證明多值XQDD表示方式的使用記憶空間低於其它表示方式。
最後，原來的量子安全直接通信協議（QSDC）通常需要消耗一個"Einstein-Podolsky-Rosen (EPR)對"傳輸一個量子位元，如果Alice想要發送一個n位元的訊息並且使用編碼方式時，她需要至少n / 2 EPR對。我們提出了一種新的QSDC協議，使用EPR對傳輸訊息，如果 Alice和Bob預先和信任的伺服器共享2c+1 個EPR對，其中c是一個常數，Alice可以傳輸任意數量的量子位元給Bob，Alice和Bob使用2c個EPR對執行彼此之間的驗證工作，其餘的EPR對用於量子位元訊息的編碼和解碼，因此在一次傳輸所需要的EPR對之總數量是一個常數，而且不管有多少位元被傳送。除了預先共享固定數量的EPR對，在傳輸秘密訊息之前，它並不需要傳輸EPR對，這可以減少量子通道的使用和風險。除此之外，在身份驗證之後，伺服器不參與訊息傳輸，因此我們可以防止伺服器知道訊息內容。

關鍵字

可逆電路 ； 邏輯合成 ； 量子計算 ； 多值邏輯 ； 驗證 ； 身份驗證

並列摘要

Reversible circuits have applications in many areas such as digital signal processing, low power design, and quantum computing. If a circuit is reversible, it can reduce the energy consumption caused by information loss. The Karnaugh map method is faster and easier to apply than other simplification methods for combination logic circuits. But the classical Karnaugh map is not directly applicable to reversible circuits because the basic logic gates, except the NOT gate, are not reversible gates. In this dissertation, we propose a method to solve the problem so that the Karnaugh map can be applied to the reversible circuit synthesis. Our algorithm provides a systematic method for simplifying the reversible circuit. This can generate the resulting expression in exclusive-sum form and transform it into a final reversible circuit with lower quantum cost. Moreover, we can realize permutations to be reversible circuits with lower quantum cost and without unnecessary garbage bits. We can also convert irreversible circuits by adding qubits to make the circuits reversible. The experimental results show that the average saving in quantum cost is 15.82% compared with previous approaches.
So far there are no synthesis algorithms that can find all the optimal reversible circuits except an exhaustive algorithm. We propose a method based on the divide and conquer approach which can significantly improve the performance of the existing synthesis algorithms to synthesize reversible circuits. A reversible circuit is first divided into two subcircuits. The smaller subcircuit will input all possible combinations of m gates, except for those combinations with the same functionality only the one with fewest gates is selected for input. The other subcircuit can be synthesized with an existing algorithm. The two subcircuits are then combined to form all the possible results and from these results we can choose the most simplified one. According to the experimental results on all the 3-variable reversible functions, we can see that the performance of the existing algorithms can be significantly improved by using our method. Therefore the synthesized reversible circuits are much more simplified than previous results.
Moreover, in order to efficiently represent a quantum operation, we propose X-decomposition Quantum Decision Diagram (XQDD) which can easily perform matrix operations. XQDD can be used to verify quantum and reversible circuits even if the reversible circuits have different number of garbage qubits. It is more efficient in terms of space and time. We extend the binary-valued XQDD to multiple-valued quantum logic. The extended XQDD can represent a multiple-valued quantum operation and perform matrix operations. It can be applied to verify the equivalence of two multiple-valued quantum or reversible circuits which are synthesized by different approaches. According to the simulation results, it is much better than multiple-valued QuIDD and very close to QMDD in terms of time. Besides, we show that the space in multiple-valued XQDD is less than other representations.
Finally, previous quantum secure direct communication (QSDC) protocols usually consume one Einstein-Podolsky-Rosen (EPR) pair to transmit a single qubit. If Alice wants to transmit an n-bit message, she needs at least n/2 EPR pairs when dense coding scheme is used. We propose a new QSDC protocol based on EPR pairs. If both Alice and Bob pre-share 2c+1 EPR pairs with the trusted server where c is a constant, Alice can transmit arbitrary number of qubits to Bob. The 2c EPR pairs are used by Alice and Bob to authenticate each other and the remaining EPR pair is used to encode and decode the message qubit. Thus the total number of EPR pairs used for one communication is a constant no matter how many bits will be transmitted. It does not need to transmit EPR pairs before transmitting the secret message except the pre-shared constant number of EPR pairs. It reduces both the utilization of the quantum channel and the risk. In addition, after the authentication, the server is not involved in the message transmission. Thus we can prevent the server from knowing the message.

並列關鍵字

Reversible Circuits ； Logic Synthesis ； Quantum Computing ； Multiple Valued Logic ； Verification ； Authentication

參考文獻

[1] R. Landauer, “Irreversibility and Heat Generation in the Computing Process, “ IBM J. Research and Development, pp. 5:183-191, 1961.

[2] C. H. Bennett, “Logical Reversibility of Computation, “ IBM J. Research and Development, pp. 17:525-532, November, 1973.

[4] P. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” in Proc. of the 35th Annual IEEE Symposium on the Foundations of Computer Science, pp. 124-134, 1994.

[5] L. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” in Proc. of the 28th Annual ACM symposium on the Theory of Computing, pp. 212-219, 1996.

[10] P. Kerntopf, “A New Heuristic Algorithm for Reversible Logic Synthesis, “ in DAC, pp. 834-837, June, 2004.