Tài liệu Synthesis of reversible and quantum circuit using rocbdd and mixed polarity toffoli gate

VIETNAM NATIONAL UNIVERSITY – HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY -------------------- NGUYEN TRUNG HIEU SYNTHESIS OF REVERSIBLE AND QUANTUM CIRCUIT USING ROCBDD AND MIXED-POLARITY TOFFOLI GATE Major: Electronic Engineering Major’s Code: 8520203 MASTER THESIS HO CHI MINH CITY, August, 2021 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG - TPHCM Cán bộ hướng dẫn khoa học : TS. Trần Hoàng Linh ............................... Cán bộ chấm nhận xét 1 : TS. Nguyễn Minh Sơn Cán bộ chấm nhận xét 2 : TS. Trương Quang Vinh ................................ Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM ngày 26 tháng 08 năm 2021 (trực tuyến). Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. Chủ tịch hội đồng: TS. Huỳnh Phú Minh Cường 2. Thư ký hội đồng: TS. Nguyễn Lý Thiên Trường 3. Ủy viên Phản biện 1: TS. Nguyễn Minh Sơn 4. Ủy viên Phản biện 2: TS. Trương Quang Vinh 5. Ủy viên hội đồng: TS. Bùi Trọng Tú Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã được sửa chữa (nếu có). CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA ĐIỆN ĐIỆN TỬ ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập – Tự do – Hạnh phúc. -----✩---------✩----- NHIỆM VỤ LUẬN VĂN THẠC SỸ HỌ VÀ TÊN: NGUYỄN TRUNG HIẾU Ngày, tháng, năm sinh: 01/05/1997 Chuyên ngành: Kỹ Thuật Điện Tử MSHV: 1970635 Nơi sinh: Khánh Hòa Mã số: 8520203 TÊN ĐỀ TÀI: SYNTHESIS OF REVERSIBLE AND QUANTUM CIRCUIT USING ROCBDD AND MIXED-POLARITY TOFFOLI GATE NHIỆM VỤ VÀ NỘI DUNG: - Xây dựng, cải tiến giải thuật tổng hợp mạch khả đảo dựa trên cấu trúc ROCBDD và cấu trúc cổng Mixed-polarity Toffoli gate. - Xây dựng chương trình cho giải thuật đã đề ra, so sánh với các kết quả trong các nghiên cứu trước đó. ....................................................................................................................................................... ....................................................................................................................................................... NGÀY GIAO NHIỆM VỤ: 21/09/2020....................................................................................... NGÀY HOÀN THÀNH NHIỆM VỤ: 13/06/2021...................................................................... CÁN BỘ HƯỚNG DẪN: TS. Trần Hoàng Linh ...................................................................... CÁN BỘ HƯỚNG DẪN Tp.HCM, ngày…... tháng ….. năm 2021 CHỦ NHIỆM BỘ MÔN TRƯỞNG KHOA ĐIỆN - ĐIỆN TỬ Acknowledgement NGUYEN TRUNG HIEU ACKNOWLEDGEMENT “Thanks to my solid academic training, today I can write hundreds of words on virtually any topic without possessing a shred of information, which is how I got a good job in science.” – “Just kidding, sciene is my obsession and becoming a scientist is always my dream. Gather more and more knowledge is the best way to make my dream come true even when I’m in bad situation.” – “Keep going, …” I would like to give thanks to people who caring and helping me by Vietnamese – my mother language: Xin cảm ơn thầy TS. Trần Hoàng Linh đã hướng dẫn tạo mọi cơ hội tốt nhất để giúp em hoàn thành luận văn tốt nghiệp này. Xin cảm ơn mọi người tại PTN 203B3 – Khoa Điện Điện tử - nơi em nghiên cứu và làm việc đã giúp đỡ và hỗ trợ em trong suốt thời gian qua. Xin gửi lời cảm ơn tới những người bạn đã luôn ủng hộ và ở cạnh mình trong thời gian qua – cảm ơn vì đã ở bên ngay cả khi mình muốn bỏ cuộc. Xin chân thành cảm ơn tất cả !!! Tp. Hồ Chí Minh, ngày 06 tháng 08 năm 2021. Học viên i Master Thesis NGUYEN TRUNG HIEU ABSTRACT In the last decade, the synthesis of reversible circuits has become a trending topic because of its future necessity and importance. Reversible circuits are circuits that do not lose information during computation. These circuits can create unique output vector from each input vector, and vice versa, that is, there is a one-to-one mapping between the input and the output vectors. Historically, the reversible circuits have been inspired by theoretical research in low power electronics as well as practical progress of bit-manipulation transforms in cryptography and computer graphics. Interest in reversible circuit is also sparked by its applications in several up-todate technologies, such as Nanotechnology, Quantum Computing, Optical Computing, and Low Power Adiabatic CMOS. However, the most important application of reversible circuits is in Quantum Computing. Logic synthesis methodologies for reversible circuits are very different from those for classical CMOS and other technologies. Many methods have been studied and Proposed. For instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its own limitation related to time processing, ancilla and garbage line, quantum cost, … The motivation for this thesis is developing a method to help reduce the number of ancilla, quantum gates and quantum cost. In this dissertation, an algorithm for synthesizing quantum circuit based on Mixedpolarity Toffoli gate and ROCBDD is introduced. ROCBDD is a variant of binary decision diagram (BDD) standing for reduced-ordered-complemented edge-bdd. It is an optimized method of BDD-based method. This work help reduce the number of nodes in representation of Boolean functions which leads to adding more lines and quantum gates in result reversible circuit. To achieve the reduction goals, in the first chapter, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. In chapter two, related knowledge in this field of research is introduced. In chapter three, this thesis describes a new structure consisting of Mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to ii Master Thesis NGUYEN TRUNG HIEU match BDD representation to reversible logic circuit is also mentioned. In chapter four, this dissertation shows the experimental result and compares with previous related methods’ results. It indicates that our algorithm has better synthesizing cost comparing to the results of previous BDD-based methods. iii Master Thesis NGUYEN TRUNG HIEU TÓM TẮT LUẬN VĂN Trong những năm gần đây, kỹ thuật tổng hợp các mạch khả đảo đã trở thành một chủ đề đang được quan tâm và nghiên cứu bởi vì sự cần thiết, tầm quan trọng trong lĩnh vực tính toán lượng tử - được đánh giá là công nghệ của tương lai. Các mạch khả đảo có ưu điểm nổi bật là không bị mất mát thông tin trong quá trình tính toán và có khả năng xử lý được nhiều phép toán một cách “song song” bởi sử dụng các qubit lượng tử. Thêm vào đó, các mạch này có đặc điểm ứng với mỗi vector ngõ vào chỉ có duy nhất từ một vectơ ngõ ra và ngược lại, hay có một ánh xạ 1-1 giữa các vectơ đầu vào và đầu ra. Trong lịch sử, việc nghiên cứu các mạch khả đảo được lấy ý tưởng từ việc nghiên cứu lý thuyết các thiết bị điện tử công suất thấp cũng như trong tính toán mật mã và đồ họa máy tính. Ngoài ra, các mạch khả đảo cũng được nghiên cứu để ứng dụng trong một số công nghệ mới nhất, chẳng hạn như: công nghệ nano, máy tính lượng tử, máy tính quang học và nghiên cứu các mạch CMOS công suất thấp. Tuy nhiên, ứng dụng quan trọng nhất của mạch khả đảo là ở các máy tính lượng tử. Các kỹ thuật dùng để tổng hợp mạch khả đảo có nhiều điểm khác biệt so với các kỹ thuật dùng để tổng hợp cho mạch sử dụng công nghệ CMOS cổ điển. Trên thế giới, hiện nay, đã có nhiều kỹ thuật đã được nghiên cứu và phát triển. Các kỹ thuật tiêu biểu có thể kể đến như: transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Mỗi kỹ thuật đều có những giới hạn riêng liên quan đến thời gian xử lý, số đường ancilla và garbage, chi phí lượng tử, … Ý tưởng của luận văn này là phát triển một giải thuật tổng hợp mạch khả đảo dựa trên các kỹ thuật hiện có nhằm mục đích làm giảm số đường ancilla, số cổng lượng tử cũng như chi phí lượng tử. Trong luận văn này, tác giả giới thiệu một giải thuật tổng hợp mạch khả đảo dựa trên cấu trúc cổng Mixed-polarity Toffoli và cấu trúc cây ROCBDD. ROCBDD (reduced-ordered-complemented edge-bdd) là một biến thể của cấu trúc tìm kiếm nhị phân (BDD). Việc sử dụng cấu trúc ROCBDD nhằm làm giảm số node hay làm đơn giản cấu trúc gốc của BDD. Từ đó, việc tổng hợp mạch khả đảo sử dụng kỹ thuật BDD-based sẽ cho kết quả tối ưu hơn về số đường line cũng như chi phí lượng tử và số cổng lượng tử. Cấu trúc luận văn được chia làm 5 chương. Ở 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 BDDbased 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. INTRODUCTION.......................................................................................1 1.1 INTRODUCTION .............................................................................................1 1.2 GOAL.................................................................................................................3 Chapter 2. THEORY .....................................................................................................4 2.1 REVERSIBLE LOGIC FUNCTION .................................................................4 2.1.1 REVERSIBLE LOGIC FUNCTION .............................................................4 2.1.2 LINES IN REPRESENT CIRCUIT ...............................................................4 2.2 QUANTUM LOGIC GATE ..............................................................................5 2.3 QUANTUM COST ............................................................................................6 2.4 QUANTUM CIRCUIT ......................................................................................7 2.5 BINARY DECISION DIAGRAM (BDD) BASED SYNTHESIS ...................8 2.6 BINARY DECISION DIAGRAM (BDD) BASED SYNTHESIS ...................9 2.7 FROM BDD TO ROCBDD .............................................................................11 Chapter 3. ALGORITHM FOR SYNTHESIS ...........................................................13 3.1 TEMPLATE FOR MATCHING TO CIRCUIT USING MIXED-POLARITY TOFFOLI GATE ........................................................................................................13 3.2 ALGORITHM FOR SYNTHESIS ..................................................................16 3.3 THEORETICAL ANALYSIS OF THE COMPLEXITY AND THE GATE COST..........................................................................................................................19 Chapter 4. EXPERIMENTAL RESULT ....................................................................21 Chapter 5. CONCLUSION AND DEVELOPMENT .................................................27 5.1 CONCLUSION ................................................................................................27 5.2 DEVELOPMENT ............................................................................................27 PUBLICATION.............................................................................................................28 REFERENCES ..............................................................................................................29 vii Master Thesis NGUYEN TRUNG HIEU LIST OF FIGURES Figure 1: Reversible circuit with (n − k) wires Y of temporary storage. .......................5 Figure 2. Toffoli gate and mixed-polarity gate. .............................................................6 Figure 3. Decompostion of Toffoli gate to unity gate. ....................................................7 Figure 4. Two circuits realizing a full adder. ..................................................................8 Figure 5. Decision tree and decision diagram for the disjunction of a and b. .................8 Figure 6. Represent a function using BDD and quantum circuit. ...................................9 Figure 7. Represent two functions using BDD and quantum circuit. ...........................10 Figure 8. BDD with complement edges. .......................................................................12 Figure 9. Two templates represent for a function. ........................................................16 Figure 10. One node shared many functions. ................ Error! Bookmark not defined. Figure 11. Diagram to describe algorithm. ....................................................................18 Figure 12. The result of diagram in figure 7. ................................................................19 Figure 13. The result case 4mod5_8. .............................................................................24 Figure 14. The result case aj-e11_81. ...........................................................................24 viii Master Thesis NGUYEN TRUNG HIEU LIST OF TABLES Table 1: Example reversible logic function. ...................................................................4 Table 2. Quantum cost for mixed-polarity toffoli gates. .................................................6 Table 3. Template for matching of ROCBDD. .............................................................13 Table 4. Gate Cost and Quantum Cost for templates. ...................................................15 Table 5. Special template for matching of ROCBDD. ..................................................16 Table 6. Table of results compare with [24]. ................................................................21 Table 7. Table of results compare with [22]. ................................................................25 ix Master Thesis NGUYEN TRUNG HIEU Chapter 1. INTRODUCTION 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 selectionpart 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. 1.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. THEORY 2.1 REVERSIBLE LOGIC FUNCTION 2.1.1 REVERSIBLE LOGIC FUNCTION n m A multiple output Boolean function is a mapping f : B  B . Let denote X   x1, x2 ,..., xn  and Y   f1 , f2 ,..., f m  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 A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 F1 1 1 1 0 1 0 0 0 Ngõ ra F2 1 0 0 1 1 0 0 1 F3 0 1 0 1 1 1 0 0 Table 1: Example reversible logic function. 2.1.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.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 ⊘, in which ,…, }⊂ and ={ is called the set of control lines and , ,…, }⊂ with ∩ = 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 }.  1 input and 1 output: { } to {1⨁ } - NOT gate (Figure 2a)  2 inputs and 2 outputs: { , } to { , ⨁ } - CNOT gate (Figure 2b) 5 Master Thesis NGUYEN TRUNG HIEU  3 inputs and 3 outputs: { , } to { , , , ⨁ } - Toffoli gate (Figure 2c) Mixed-polarity Toffoli gate with 2 or 3 input and output are defined similarity:  2 inputs and 2 outputs: { , } to { , ⨁ } - Negative CNOT gate (Figure 2d)  3 inputs and 3 outputs: { , , } to { , , } to { , , ⨁ } - Semi-negative ⨁ } - Negative Toffoli Toffoli gate (Figure 2e)  3 inputs and 3 outputs: { , , gate (Figure 2f) (a) (b) (c) (d) (e) (f) Figure 2. Toffoli gate and mixed-polarity gate. 2.3 QUANTUM COST In this thesis, to evaluate each gate, we use quantum cost defined in [8], [26]. The quantum cost of a reversible gate is the number of 1x1 and 2x2 reversible gates or quantum gates required in its design. The quantum costs of all reversible 1x1 and 2x2 gates are taken as unity. Table 2. Quantum cost for mixed-polarity toffoli gates. Quantum Quantum cost cost Figure 1a 1 Figure 1d 3 Figure 1b 1 Figure 1e 5 Figure 1c 5 Figure 1f 7 Since every reversible gate is a combination of 1x1 or 2x2 quantum gate, therefore the quantum cost of a reversible gate can be calculated by counting the numbers of 6 Master Thesis NGUYEN TRUNG HIEU NOT, Controlled-V, Controlled-V+ and CNOT gates used. The quantum cost for 6 gates is shown in Table 2. For instance, to calculate the quanum cost for Toffoli gate, it is decomposed into 5 unity gates (Figure 3). It leads the cost for the Toffoli gate of 5. (a) (b) Figure 3. Decompostion of Toffoli gate to unity gate. 2.4 QUANTUM CIRCUIT In quantum circuits, qubit is used instead of bit. The state of a qubit for two pure logic states can be expressed as |     | 0    | 1 , where | 0  and |1 denote pure logic states 0 and 1, respectively. In this formula, α and β are complex numbers 2 2 satisfying     1. This type of circuits realize functions with the help of elementary quantum gates. Quantum circuits are inherently reversible and manipulate qubits rather than pure logic values. The most frequently occurring elementary quantum gates are the NOT gate (a single qubit is inverted), the controlled-NOT (CNOT) gate (the target qubit is inverted if the single control qubit is 1), the controlled-V gate (also known as a square root of NOT, since two consecutive V operations are equivalent to an inversion), and the controlled-V+ gate (which performs the inverse operation of the V gate and thus is also a square root of NOT). Figure 4a shows a Toffoli gate realization of a full adder. This circuit has four inputs (the constant input 0, the carry-in cin, as well as the summands a and b), four outputs (the carry-out cout and the sum as well as two garbage outputs), and consists of four Toffoli gates. Thereby, the control lines of each Toffoli gate are denoted by ● while the target lines are denoted by ⊕. Figure 4b shown another representation of this circcuit using control-V gate. This circuit has the same inputs and outputs but consists of six gates in total. The notation is similar to a Toffoli circuit, except that the 7 Master Thesis NGUYEN TRUNG HIEU target lines are denoted with respect to the particular gate type. More precisely, a Vbox is used to denote a controlled-V gate and a V+-box is used to denote a controlledV+ gate. The notations for NOT and CNOT gates are equal to the notation for Toffoli gates. (a) (b) Figure 4. Two circuits realizing a full adder. 2.5 BINARY DECISION DIAGRAM (BDD) BASED SYNTHESIS Binary Decision Diagram (BDD) is a graph used to represent a Boolean function. Assume that we have Boolean function ( , ,…, , 1, ,…, ) and ( , = ( , ,…, ,…, ). Let denote: , 0, ,…, = ). Using Shannon decomposition [27], we have: = + (1 ≤ ≤ ) Each node in BDD represents a Shannon expression with a variable. For each , and are called high node and low node respectively. By using Shannon on the and with another variable, these nodes also have their high and low node (Figure 5a). (a) (b) Figure 5. Decision tree and decision diagram for the disjunction of a and b. 8