Improved ant colony optimization for quantum cost reduction

Shaveta Thakral


Heuristic algorithms play a significant role in synthesize and optimization of digital circuits based on reversible logic yet suffer with multiple disadvantages for multiqubit functions like scalability, run time and memory space. Synthesis of reversible logic circuit ends up with trade off between number of gates, quantum cost, ancillary inputs and garbage outputs. Research on optimization of quantum cost seems intractable. Therefore post synthesis optimization needs to be done for reduction of quantum cost. Many researchers have proposed exact synthesis approaches in reversible logic but focussed on reduction of number of gates yet quantum cost remains undefined. The main goal of this paper is to propose improved Ant Colony Optimization (ACO) algorithm for quantum cost reduction. The research efforts reported in this paper represent a significant contribution towards synthesis and optimization of high complexity reversible function via swarm intelligence based approach.  The improved ACO algorithm provides low quantum cost based toffoli synthesis of reversible logic function without long computation overhead.


Heuristic; Synthesis; Ant Colony Optimization; Quantum Cost; Complexity


W.J. Gutjahr, “ACO Algorithms with Guaranteed Convergence to the Optimal Solution”, Information processing

letters, 82(3), 145-153, 2002.

D.M.Miller, et al., “A transformation Based Algorithm for Reversible Logic Synthesis”, In Proceedings 2003. Design

Automation Conference (IEEE Cat. No. 03CH37451) , IEEE, June 2003,pp. 318-323.

P.Gupta, et al., “An Algorithm for Synthesis of Reversible Logic Circuits”,IEEE Transactions on Computer-Aided

Design of Integrated Circuits and Systems, 25(11), pp.2317-2330,2006.

V.V.Shende, et al., “Synthesis of Reversible Logic Circuits”, IEEE Transactions on Computer-Aided Design of

Integrated Circuits and Systems, 22(6), pp.710-722,2003.

M.Saeedi, et al. “On the Behavior of Substitution-Based Reversible Circuit Synthesis Algorithms: Investigation and

Improvement’, In IEEE Computer Society Annual Symposium on VLSI (ISVLSI'07), IEEE,March 2007, pp. 428-436.

M.Saeedi, et al.,”A Novel Synthesis Algorithm for Reversible Circuits”, In 2007 IEEE/ACM International

Conference on Computer-Aided Design , IEEE,Nov 2007,pp. 65-68.

K.Fazel, et al. “ESOP-Based Toffoli Gate Cascade Generation”, in 2007 IEEE Pacific Rim Conference on

Communications, Computers and Signal Processing, pp. 206-209, 2007.

R.Wille and R.Drechsler , “BDD-Based Synthesis of Reversible Logic for Large Functions” in Proceedings of the

th Annual Design Automation Conference , ACM,July 2009, pp. 270-275.

N.Alhagi, et al., “Synthesis of Reversible Circuits with no Ancilla Bits for Large Reversible Functions Specified with

Bit Equations”, In 2010 40th IEEE International Symposium on Multiple-Valued Logic, IEEE, May 2010,pp. 39-45.

M.Arabzadeh, et al., “Rule-Based Optimization of Reversible Circuits”, in Proceedings of the 2010 Asia and South

Pacific Design Automation Conference, IEEE press,Jan 2010, pp. 849-854.

D.K.Kole, et al., “Optimal Reversible Logic Circuit Synthesis Based on a Hybrid DFS-BFS Technique”, In 2010

International Symposium on Electronic System Design , IEEE, Dec 2010, pp. 208-212.

M.Saeedi, et al., “A Library-Based Synthesis Methodology for Reversible Logic”, Microelectronics Journal, 41(4),

pp.185-194, 2010

M. Li, et al., “Reversible Logic Synthesis through Ant Colony Optimization” in Proceedings of the Conference on

Design, Automation and Test in Europe,2010,pp. 307-310.

M.Islam,‘BSSSN: Bit string swapping sorting network for reversible logic synthesis’,arXiv preprint


M.Islam and A.A.Mahmud, “Sorting Network for Reversible Logic Synthesis’, arXiv preprint arXiv:


K.Datta, et al., “Particle Swarm Optimization Based Circuit Synthesis of Reversible Logic”, in 2012 International

Symposium on Electronic System Design (ISED), IEEE, pp. 226-230, Dec 2012.

M.Sarkar,et al., “Reversible Circuit Synthesis using ACO and SA Based Quine-McCluskey Method”, in IEEE 56th

International Midwest Symposium on Circuits and Systems (MWSCAS), IEEE, 2013,pp. 416-419.

T.N.Sasamal, et al.,”Reversible Logic Circuit Synthesis and Optimization using Adaptive Genetic Algorithm”,

Procedia Computer Science, 70, 2015, pp.407-413.

S.Thakral, et al., “Review of Truth Table Based Reversible Logic Synthesis Methods, “in International Conference

on Soft Computing Techniques and Implementations (ICSCTI) , IEEE,2015, pp. 164-169.


  • There are currently no refbacks.

Bulletin of EEI Stats