chương 1, tác giả giới iv Master Thesis NGUYEN TRUNG HIEU thiệu về kỹ thuật tổng hợp mạch dựa trên cấu trúc ROCBDD và sự khác biệt so với cấu trúc cũ BDD. Thêm vào đó, tác giả còn so sánh điểm nổi trội của kỹ thuật BDD- based so với các kỹ thuật còn lại. Ở chương 2, một vài kiến thức cơ bản liên quan đế lĩnh vực này cũng như một số quy ước được đề cập. Ở chương 3, tác giả trình bày các template mới sử dụng cấu trúc cổng Mixed-polarity Toffoli dùng để tổng hợp tại từng node.
Tác giả còn trình bày một giải thuật dùng để tối ưu cho việc tổng hợp mạch tại từng node sao cho đạt được hiệu quả tối ưu như mục đích ban đầu. Ở chương 4, tác giả trình bày các kết quả có được khi thực thi giải thuật trên các hàm chuẩn. Sau đó, tác giả so sánh các kết quả này với các kết quả được trình bày trong các nghiên cứu liên quan. Kết quả cho thấy giải thuật của tác giả cho kết quả tốt hơn so với các giải thuật cùng sử dụng kỹ thuật BDD-based trước đó.
v Master Thesis NGUYEN TRUNG HIEU DECLARATION OF AUTHORSHIP I, Nguyen Trung Hieu, declare that this thesis titled, “Synthesis of Reversible and Quantum Circuit using ROCBDD and Mixed-Polarity Toffoli Gate” and the work presented in it are my own. I confirm that: This work was done wholly while in candidature for a research degree at this University. Where I have consulted the published work of others, this is always clearly attributed. Where I have quoted from the work of others, the source is always given.
With the exception of such quotations, this thesis is entirely my own work. I have acknowledged all main sources of help. Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself. Author NGUYỄN TRUNG HIẾU vi Master Thesis NGUYEN TRUNG HIEU CONTENTS Chapter 1.1 REVERSIBLE LOGIC FUNCTION .1 REVERSIBLE LOGIC FUNCTION .2 LINES IN REPRESENT CIRCUIT .2 QUANTUM LOGIC GATE .5 BINARY DECISION DIAGRAM (BDD) BASED SYNTHESIS .6 BINARY DECISION DIAGRAM (BDD) BASED SYNTHESIS .7 FROM BDD TO ROCBDD.
ALGORITHM FOR SYNTHESIS .1 TEMPLATE FOR MATCHING TO CIRCUIT USING MIXED-POLARITY TOFFOLI GATE .2 ALGORITHM FOR SYNTHESIS .3 THEORETICAL ANALYSIS OF THE COMPLEXITY AND THE GATE COST. CONCLUSION AND DEVELOPMENT .29 vii Master Thesis NGUYEN TRUNG HIEU LIST OF FIGURES Figure 1: Reversible circuit with (n − k) wires Y of temporary storage. Toffoli gate and mixed-polarity gate. Decompostion of Toffoli gate to unity gate.
Two circuits realizing a full adder. Decision tree and decision diagram for the disjunction of a and b. Represent a function using BDD and quantum circuit. Represent two functions using BDD and quantum circuit.
BDD with complement edges. Two templates represent for a function. One node shared many functions. Error! Bookmark not defined.
Diagram to describe algorithm. The result of diagram in figure 7. The result case 4mod5_8. The result case aj-e11_81.24 viii Master Thesis NGUYEN TRUNG HIEU LIST OF TABLES Table 1: Example reversible logic function.
Quantum cost for mixed-polarity toffoli gates. Template for matching of ROCBDD. Gate Cost and Quantum Cost for templates. Special template for matching of ROCBDD.
Table of results compare with [24]. Table of results compare with [22].25 ix Master Thesis NGUYEN TRUNG HIEU Chapter 1.1 INTRODUCTION Many studies about the application of quantum logic circuits [1]–[3] have been introduced and proved ever before. Two main problems solved by quantum logic circuits are reducing circuit power consumption and increasing the density of transistors in an area of layout circuit. In [1], [4], the authors show that the power consumption of a calculation using qubit can be less than KTln2 – which is the least power consumption of the same calculation using a traditional bit.
In the definition of the quantum equation, a qubit can express many states simultaneously, which leads to calculations being conducted simultaneously. It solves processing time and resources problems. Its application in many domains is also introduced, like DNA computing [1], optical computing [5], nanotechnology [6] and quantum computing [7]. However, almost all algorithms used to synthesize irreversible traditional logic cannot be carried on to synthesis reversible logic due to two issues: fan-out and feedback.
Only cascade structure is accepted in reversible circuits. To solve the earlier problems, many techniques for synthesizing quantum circuit has been researched and developed over the past two decades. In [8], [9], Maslov et al. proposed a transformation-based method that transforms outputs sequentially and relies on the properties of the pre-selected quantum gate (Toffoli, Fredkin, …) to choose the path from output to input and synthesis the circuit.
This first method depends on the size of the truth table, which leads to a considerable processing time when the numbers of inputs are increased. The following method introduced is search-based (heuristic methods), [10]–[12] which iteratively finding the possible path selection using Hamming distance [13]. After this phase, a variety of reversible gates are selected by finding the possible matching reversible gate. Similar to the transformation-based method, this method relies on the size of the truth table, but the results are better due to using Hamming distance to find the best path.
In [14], [15], Saeedi et al. introduced a technique called the cycle-based method to decompose Boolean functions into smaller cycles. From each cycle, this method synthesizes it 1 Master Thesis NGUYEN TRUNG HIEU into a quantum circuit. The result of this method depends on the number of cycles and the decomposition process.
The ESOP-based method proposed in [16]–[20] was the synthesis algorithm with no adding lines. By using Positive-polarity Reed-Muller expansion [21], this method synthesis quantum circuits by matching each selection- part in expansion to a built-in template in the library. Its disadvantage is the processing time to build the library when the numbers of input grow up. This research starts by using the BDD-based method – which was first introduced by Wille in [22].
The first step of this method is building a BDD [23] for Boolean functions. An advantage of conduct BDD is the capability of large function expression infinite time which overcomes the weakness of previous methods. Then, each node of BDD is matched to a cascade of reversible gates or templates. The additional templates may add more garbage lines to the circuit result due to the properties of the shared nodes of BDD.
Many BDD versions are introduced to optimize the algorithm. Three structures called shared BDD, complement edges BDD and advanced ordering BDD were used in synthesis and evaluation individually in [24]. Shared edges BDD reduces lines and quantum costs by sharing nodes for many functions. The complement-edge version decreases the total sizes of BDD (measured by the numbers of nodes) in half, causing a reduction in additional lines.
Besides, by using complement edges, the templates are more complicated with only Toffoli gate expression, which lead to higher quantum cost. Meanwhile, advanced ordering BDD required many loops to choose the correct orders of variables to get the simplest structure of BDD. Taking all the advantages of the two last versions, ROCBDD is used to synthesize the quantum circuit. Moreover, we also study an algorithm to match templates at share nodes – an important property of BDD.
Inheriting the properties of complement edges BDD, a new template using mixed-polarity Toffoli gates is proposed to decrease the number of gates. These gates comprise of Toffoli gate, semi-controlled Toffoli gate and negative-controlled Toffoli gate, which were studied in [15], [25] and used with search-based and cycle-based methods. From these reasons, I select the topic: “Synthesis of Reversible and Quantum Circuit using ROCBDD and Mixed-Polarity Toffoli Gate” for my thesis. 2 Master Thesis NGUYEN TRUNG HIEU The thesis is organized as follows: Chapter 2, Theory, introduces basic definitions of reversible logic, BDD and theory of transforming from BDD to ROCBDD.
Chapter 3 introduces a template rebuilt relying on mixed-polarity toffoli gates and illustrates the algorithm that matches each node to the corresponding quantum circuit. Chapter 4 presents experimental results. Chapter 5 concludes the thesis and the development.2 GOAL The goal of my thesis includes: Develop an algorithm for synthesizing the reversible quantum circuit using Mixed-Polarity Toffoli Gate and BDD-based synthesis method. Design a software of the algorithm.
Evaluate the performance of my algorithm with the previous algorithm’s one. Optimize the algorithm as well as the software to achive the best performance. 3 Master Thesis NGUYEN TRUNG HIEU Chapter 2.1 REVERSIBLE LOGIC FUNCTION 2.1 REVERSIBLE LOGIC FUNCTION n m A multiple output Boolean function is a mapping f : B B ., f m and are the input set and output set respectively. Function f is called reversible if: The number of input is equal to the number of output which means n = m.
The mapping from inputs to output is bijective or the any input only maps to a unique output. With this definition, a multiple output function having n input and m < n output can become reversible when adding (n-m) value to output called ancilla line. Example for this function is shown in Table 1. Ngõ vào Ngõ ra A B C F1 F2 F3 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 Table 1: Example reversible logic function.2 LINES IN REPRESENT CIRCUIT "Garbage" is the number of outputs added to make a (n, k) function reversible.
While the word "constant inputs" is used to denote the preset value inputs that are added to an (n, k) function to make it reversible. The constant inputs are known as ancilla inputs. The relation between garbage outputs and constant inputs are: input + constant input = output + garbage 4 Master Thesis NGUYEN TRUNG HIEU As with reversible gates, a reversible circuit has the same number of input and output wires; the reversible circuit with n inputs is called an n x n circuit, or a circuit on n wires. More generally, Figure 1 illustrates the general reversible circuit of temporary storage.
The top (n - k) lines transfer (n - k) signals Y to the corresponding wires on the other side of the circuit. The bottom k wires enter as the input value X and emerge as the output value f(X). These wires usually serve as an essential workspace for computing f(X). This circuit is said to compute f(X) using (n - k) lines of temporary storage.
This leads to the following definition. Figure 1: Reversible circuit with (n − k) wires Y of temporary storage.2 QUANTUM LOGIC GATE To implement a reversible logic function to a quantum circuit, quantum logic gates are used. Differentiating from classic gates, quantum gates have the numbers of inputs equal to the numbers of outputs. These properties allow us to realize quantum circuits by connecting cascade quantum gates.
In general, a quantum gate expresses a function : →. Let ={ , ,…, }⊂ and ={ , ,…, }⊂ with ∩ = ⊘, in which is called the set of control lines and is called the set of target lines. In this research, we focus on Toffoli gate and mixed-polarity Toffoli gate with maximum three inputs and three outputs. From previous definition: Toffoli gate has function map { , ,…, , } to { , ,…, , ⨁ }.