Graduation Year


Document Type




Degree Granting Department

Computer Science and Engineering

Major Professor

Nagarajan Ranganathan


Ancilla Inputs, Garbage Outputs, Modified Fredkin Gate, Quantum Computing, Quantum Cost


The reversible logic has the promising applications in emerging computing paradigm

such as quantum computing, quantum dot cellular automata, optical computing, etc. In

reversible logic gates there is a unique one-to-one mapping between the inputs and outputs.

To generate an useful gate function the reversible gates require some constant ancillary

inputs called ancilla inputs. Also to maintain the reversibility of the circuits some additional

unused outputs are required that are referred as the garbage outputs. The number of

ancilla inputs, number of garbage outputs and quantum cost plays an important role in

the evaluation of reversible circuits. Thus minimizing these parameters are important for

designing an efficient reversible circuit. Barrel shifter is an integral component of many

computing systems due to its useful property that it can shift and rotate multiple bits in a

single cycle.

The main contribution of this thesis is a set of design methodologies for the reversible

realization of reversible barrel shifters where the designs are based on the Fredkin gate and

the Feynman gate. The Fredkin gate can implement the 2:1 MUX with minimum quantum

cost, minimum number of ancilla inputs and minimum number of garbage outputs and the

Feynman gate can be used so as to avoid the fanout, as fanout is not allowed in reversible

logic. The design methodologies considered in this work targets 1.) Reversible logical right-

shifter, 2.) Reversible universal right shifter that supports logical right shift, arithmetic

right shift and the right rotate, 3.) Reversible bidirectional logical shifter, 4.) Reversible

bidirectional arithmetic and logical shifter, 5) Reversible universal bidirectional shifter that

supports bidirectional logical and arithmetic shift and rotate operations. The proposed

design methodologies are evaluated in terms of the number of the garbage outputs, the

number of ancilla inputs and the quantum cost. The detailed architecture and the design of

a (8,3) reversible logical right-shifter and the (8,3) reversible universal right shifter are

presented for illustration of the proposed methodologies.