Synthesis of reversible logic
| dc.contributor.advisor | Dueck, Gerhard | |
| dc.contributor.author | Rahman, Md. Mazder | |
| dc.date.accessioned | 2023-03-01T16:16:46Z | |
| dc.date.available | 2023-03-01T16:16:46Z | |
| dc.date.issued | 2014 | |
| dc.date.updated | 2023-03-01T15:01:09Z | |
| dc.description.abstract | Reversible logic plays an important role in quantum computation. Quantum computations are known to have massive parallelism and hence, exponential speed-up is possible in some algorithms. Logic operations in quantum systems are unitary transformations that are reversible. A computing system that is logically reversible can be physically reversible. Therefore, research in reversible logic can lead to the design of powerful computing devices. The synthesis of reversible logic targeted to the construction of quantum circuits is significantly different from non-reversible logic synthesis. The underlying synthesis procedures start from Boolean function specifications, and generate circuits that are realizable with quantum technologies. In general, for a given Boolean function, the design flow employs a series of methods such as embedding the Boolean function into a reversible one, finding a Multiple-Controlled-Toffoli (MCT) realization, minimizing the Toffoli circuit, decomposing the Toffoli circuit into a quantum circuit, and optimizing the quantum circuit. These approaches are mostly heuristics that show significant room for improvement. The aim of this thesis is to improve existing heuristics. One such optimization heuristic is template matching. The current set of templates (rewriting rules) used in template matching is incomplete. Moreover, the exact mapping of gate sequences of a template to gate sequences of a circuit is a complex problem that has not been solved. If minimal circuits are known, then they can be used as comparison for heuristic methods. However, the entangled state - a phenomenon in quantum computation - makes it difficult to develop a synthesis method that gives minimal circuits. Moreover, different technologies have different constraints. For example, Ion Trapped technology requires Linear Nearest Neighbor (LNN) circuits. Heuristics for constructing LNN circuits use SWAP gates that results in a dramatic increase in the number of gates. There are many possibilities for modelling universal quantum gate libraries; however, which library would be the best suited for quantum technologies is an open question. In this thesis, we first present an exhaustive search method that finds minimal circuits of 3 qubits that serve as benchmarks. We give a new definition of template with a set of properties that show that minimal circuits are embedded in templates. Hence, we prove that a complete set of templates has the power of obtaining a minimal circuit from any non-minimal circuit by using template matching. The properties of templates also lead us to the development of algorithms for constructing new templates. A graph-based data structure enables an efficient formulation as well as implementation of matching problems. A set of algorithms for exact template matching is developed. The efficiency of the proposed algorithms is verified by optimizing the standard benchmarks. We analyse different models as well as minimal ways of constructing LNN circuits without the use of SWAP gates. Our proposed heuristic takes less time to obtain reduced LNN circuits than other methods in the literature. We suggest that if a 2-qubit function can be realized by a single 2-qubit quantum gate, then a new gate library can be built. By considering such a gate has unit quantum cost, we find two different gate libraries that lead to significant cost reductions in realizing 3-qubit minimal circuits. | |
| dc.description.copyright | © Md. Mazder Rahman, 2015 | |
| dc.format | text/xml | |
| dc.format.extent | xix, 133 pages | |
| dc.format.medium | electronic | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/13265 | |
| dc.language.iso | en_CA | |
| dc.publisher | University of New Brunswick | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | Synthesis of reversible logic | |
| dc.type | doctoral thesis | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.fullname | Doctor of Philosophy | |
| thesis.degree.grantor | University of New Brunswick | |
| thesis.degree.level | doctoral | |
| thesis.degree.name | Ph.D. |
Files
Original bundle
1 - 1 of 1