Optimization of Reversible Circuits: Toffoli Decompositions, Negative Controls

Title: Optimization of Reversible Circuits Using Toffoli Decompositions with Negative Controls

Abstract: ​
The synthesis and optimization of quantum circuits are essential for the construction of quantum computers. This paper proposes two methods to reduce the quantum cost of 3-bit reversible circuits. The first method utilizes basic building blocks of gate pairs using different Toffoli decompositions. These gate pairs are used to reconstruct the quantum circuits where further optimization rules will be applied to synthesize the optimized circuit. The second method suggests using a new universal library, which provides better quantum cost when compared with previous work in both cost015 and cost115 metrics; this proposed new universal library “Negative NCT” uses gates that operate on the target qubit only when the control qubit’s state is zero. A combination
of the proposed basic building blocks of pairs of gates and the proposed Negative NCT library is used in this work for synthesis and optimization, where the Negative NCT library showed better quantum cost after optimization compared with the NCT library despite having the same circuit size. The reversible circuits over three bits form a permutation group of size 40,320 (23!), which is a subset of the symmetric group, where the NCT library is considered as the generators of the
permutation group.

Speaker: Mariam Medhat
Biography: Mariam is a phD candidate of Alexandria University in Egypt. She earned her master's degree in computing science from the same school. Currently, she is a teaching assistant of Egypt-Japan University of Science and Technology and researcher of Alexandria Quantum Computing Group.

Moderators:
Pawel Gora, CEO of Quantum AI Foundation
Olawale Ayoade, phD candidate of Baylor University
Kareem El-Safty, co-organizer of Alexandria Quantum Computing Group, coordinator of QEgypt