Optimization of Quantum Cellular Automata Circuits by Genetic Algorithm

Document Type : Original Article


1 Faculty of Electrical & Robotic Engineering, Shahrood University of Technology

2 Faculty of Computer Engineering, Shahrood University of Technology


Quantum cellular automata (QCA) enables performing arithmetic and logic operations at the molecular scale. This nanotechnology promises high device density, low power consumption and high computational power. Unlike the CMOS technology where the ON and OFF states of the transistors represent binary information, in QCA, data is represented by the charge configuration. The primary and basic device in this paradigm is the three-input majority gate, thus in QCA, the conventional AND-OR mapping for implementation of logic functions is not effective. We introduce four primitive admissible geometric patterns,  which aid in the identification of majority functions. For a non-majority function, a genetic algorithm (GA) is used to map the function to at most four majority gates in a wide range of implementations. We show that the emergence of specific genes will result in a further reduction in the number of majority gates in the network. The GA is intrinsically parallel and results in variety of implementations, which allows  merging the layout and logic levels of the design and provides an important approach towards designing high-performance QCA circuits.


1. H. Sasaki, M. Ono, T. Yoshitomi, T. Ohguro, S.-I. Nakamura,
M. Saito, and H. Iwai, “1.5 nm direct-tunneling gate oxide si
mosfet’s,” IEEE Transactions on Electron Devices , Vol. 43,
No. 8, (1996), 1233-1242. 
2. T. Nguyen and J. Plummer, “Physical mechanisms responsible
for short channel effects in mos devices,” IEEE International 
Electron Devices Meeting, Vol. 1, (1981), 596-599. 
3. C. S. Lent, P. D. Tougaw, W. Porod, and G. H. Bernstein, 
“Quantum cellular automata,” Nanotechnology, Vol. 4, (1993),
4. C. S. Lent, “Bypassing the transistor paradigm,” Science, Vol.
288, No. 5471, (2000), 1597-1599.  

5. R. S. Zebulum, M. A. Pacheco, and M. M. B. Vellasco,
Evolutionary electronics: automatic design of electronic circuits
and systems by genetic algorithms. CRC press, 2001.  
6. J. F. Miller, D. Job, and V. K. Vassilev, “Principles in the
evolutionary design of digital circuits—part i,” Genetic
Programming and Evolvable Machines, Vol. 1, (2000), 7-35. 
7. W. Wang, K. Walus, and G. A. Jullien, “Quantum-dot cellular
automata adders,” 3rd IEEE Conference on Nanotechnology,
Vol. 2, (2003), 461-464. 
8. K.Walus,T.J.Dysart,G.A.Jullien,andR.A.Budiman,“Qcadesigner:
a rapid design and simulation tool for quantum-dot cellular
automata,” IEEE Trans. Nanotechnol., Vol. 3, (2004), 26-31. 
9. K. Walus, M. Mazur, G. Schulhof, and G. A. Jullein, “Simple 4-
bit processor based on quantum-dot cellular automata (qca),”
IEEE International Conference on Application-Specific Systems,
Architecture Processors, Vol. 1, (2005), 288-293. 
10. Z. Kohavi and N. K. Jha, Switching and finite automata theory.
Cam- bridge University Press, 2009. 
11. R. Zhang, P. Gupta, and N. K. Jha, “Majority and minority
network synthesis with application to qca-, set-, and tpl-based
nanotechnologies,” IEEE Computer-Aided Design of
Integrated Circuits and Systems, Vol. 26, No. 7, (2007), 12331245.
12. K. Walus, G. Schulhof, G. Jullien, R. Zhang, and W. Wang,
“Circuit de- sign based on majority gates for applications with
quantum-dot cellular automata,” Asilomar Conference on
Signals, Systems and Computers, Vol. 2, (2004), 1354-1357. 
13. R. Zhang, K. Walus, W. Wang, and G. A. Jullien, “A method of
majority logic reduction for quantum cellular automata,” IEEE
Transaction Nanotechnol., Vol. 3, No. 4, (2004), 443-450. 
14. L.Amaru,P.-E.Gaillardon,andG.DeMicheli,“Majorityinvertergraph:
A new paradigm for logic optimization,” IEEE
Computer-Aided Design of Integrated Circuits and Systems,
Vol. 35, No. 5, (2015), 806-819. 
15. M. Soeken, L. G. Amaru`, P.-E. Gaillardon, and G. De Micheli,
“Exact synthesis of majority-inverter graphs and its
applications,” IEEE Computer-Aided Design of Integrated
Circuits and Systems, Vol. 36, No. 11, (2017), 1842-1855. 
16. L. Amaru, P.-E. Gaillardon, A. Chattopadhyay, and G. De
Micheli, “A sound and complete axiomatization of majority-n
logic,” IEEE Transactions Nanotechnology, Vol. 65, No. 9,
(2015), 2889-2895. 
17. E. Testa, M. Soeken, L. G. Amaru`, W. Haaswijk, and G. De
Micheli, “Mapping monotone boolean functions into majority,”
IEEE Transactions Computers, Vol. 68, No. 5, (2018), 791797.
18. H. Riener, E. Testa, L. Amaru, M. Soeken, and G. De Micheli,
“Size optimization of migs with an application to qca and stmg
technologies,” in Proceedings of the 14th IEEE/ACM
International Symposium on Nanoscale Architectures. ACM,
(2018), 157-162. 
19. M. Bonyadi, S. Azghadi, N. Rad, K. Navi, and E. Afjei, “Logic
opti- mization for majority gate-based nanoelectronic circuits
based on genetic algorithm,” International Conference on
Electrical Engineering, (2007), 1-5. 
20. C. C. Coello, A. D. Christiansen, and A. H. Aguirre, “Automated
design of combinational logic circuits by genetic algorithm,”
Artificial Neural Nets and Genetic Algorithms, (1998), 333336.
21. M. Houshmand, S. H. Khayat, and R. Rezaei, “Genetic
algorithm based logic optimization for multi-output majority
gate-based nano-electronic circuits,” IEEE International
Conference on Intelligent Computing and Intelligent Systems,
Vol. 1, (2009), 584-588. 
22. R. Rezaee, M. Houshmand, and M. Houshmand, “Multiobjective
opti- mization of qca circuits with multiple outputs
using genetic program- ming,” Genetic Programming and
Evolvable Machines, Vol. 14, No. 1, (2013), 95-118,. 
23. M. T. Niemier and P. M. Kogge, “Problems in designing with
qcas: Layout= timing,” International Journal of Circuit Theory
and Applications, Vol. 29, No. 1, (2001), 49-62. 
24. K. Das and D. De, “A novel approach of and-or-inverter (AOI)
gate design for QCA,” 4th International Conference on
Computers and Devices for Communication, Vol. 1, (2009), 1-4. 
25. A. Roohi, B. Menbari, E. Shahbazi, and M. Kamrani, “A genetic
algorithm based logic optimization for majority gate-based qca
circuits in nanoelectronics,” Quantum Matter, Vol. 2, No. 3,
(2013), 219-224.