Synthesis of reversible logic
Loading...
Files
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
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.