Reversible logic synthesis with minimal usage of ancilla bits
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/100615 |
| _version_ | 1826200179826491392 |
|---|---|
| author | Xu, Siyao, M.Eng. Massachusetts Institute of Technology |
| author2 | Scott Aaronson. |
| author_facet | Scott Aaronson. Xu, Siyao, M.Eng. Massachusetts Institute of Technology |
| author_sort | Xu, Siyao, M.Eng. Massachusetts Institute of Technology |
| collection | MIT |
| description | Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. |
| first_indexed | 2024-09-23T11:32:23Z |
| format | Thesis |
| id | mit-1721.1/100615 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:32:23Z |
| publishDate | 2016 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1006152019-04-11T09:35:28Z Reversible logic synthesis with minimal usage of ancilla bits Xu, Siyao, M.Eng. Massachusetts Institute of Technology Scott Aaronson. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 49-50). Reversible logic has attracted much research interest over the last few decades, especially due to its application in quantum computing. In the construction of reversible gates from basic gates, ancilla bits are commonly used to remove restrictions on the type of gates that a certain set of basic gates generates. With unlimited ancilla bits, many gates (such as Toffoli and Fredkin) become universal reversible gates. However, ancilla bits can be expensive to implement, thus making the problem of minimizing necessary ancilla bits a practical topic. This thesis explores the problem of reversible logic synthesis using a single base gate and a few ancilla bits. Two base gates are discussed: a variation of the 3- bit Toffoli gate and the original 3-bit Fredkin gate. There are three main results associated with these two gates: i) the variated Toffoli gate can generate all n-bit reversible gates using 1 ancilla bit, ii) the variated Toffoli can generate all n-bit reversible gates that are even permutations using no ancilla bit, iii) the Fredkin gate can generate all n-bit conservative reversible gates using 1 ancilla bit. Prior to this paper, the best known result for general universality requires three basic gates, and the best known result for conservative universality needs 5 ancilla bits. The second result is trivially optimal. For the first and the third result, we explicitly prove their optimality: the variated Toffoli cannot generate all n-bit reversible gates without using any extra input lines, and the Fredkin gate cannot generate all n-bit conservative reversible gates without using extra input lines. We also explore a stronger version of the second converse by introducing a new concept called borrowed bits, and prove that the Fredkin gate cannot generate all n-bit conservative reversible gates without ancilla bits, even with an unlimited number of borrowed bits. by Siyao Xu. M. Eng. 2016-01-04T19:58:55Z 2016-01-04T19:58:55Z 2015 2015 Thesis http://hdl.handle.net/1721.1/100615 932626803 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 50 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Xu, Siyao, M.Eng. Massachusetts Institute of Technology Reversible logic synthesis with minimal usage of ancilla bits |
| title | Reversible logic synthesis with minimal usage of ancilla bits |
| title_full | Reversible logic synthesis with minimal usage of ancilla bits |
| title_fullStr | Reversible logic synthesis with minimal usage of ancilla bits |
| title_full_unstemmed | Reversible logic synthesis with minimal usage of ancilla bits |
| title_short | Reversible logic synthesis with minimal usage of ancilla bits |
| title_sort | reversible logic synthesis with minimal usage of ancilla bits |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/100615 |
| work_keys_str_mv | AT xusiyaomengmassachusettsinstituteoftechnology reversiblelogicsynthesiswithminimalusageofancillabits |