Application of Genetic Algorithms for Evolution of Quantum Equivalents of Boolean Circuits

Authors: Swanti Satsangi, Ashish Gulati, Prem Kumar Kalra, C. Patvardhan

Abstract:

Due to the non- intuitive nature of Quantum algorithms, it becomes difficult for a classically trained person to efficiently construct new ones. So rather than designing new algorithms manually, lately, Genetic algorithms (GA) are being implemented for this purpose. GA is a technique to automatically solve a problem using principles of Darwinian evolution. This has been implemented to explore the possibility of evolving an n-qubit circuit when the circuit matrix has been provided using a set of single, two and three qubit gates. Using a variable length population and universal stochastic selection procedure, a number of possible solution circuits, with different number of gates can be obtained for the same input matrix during different runs of GA. The given algorithm has also been successfully implemented to obtain two and three qubit Boolean circuits using Quantum gates. The results demonstrate the effectiveness of the GA procedure even when the search spaces are large.

Keywords: Ancillas, Boolean functions, Genetic algorithm, Oracles, Quantum circuits, Scratch bit

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332460

References:

[1] E. Fredkin and T. Toffoli, "Conservative Logic", International Journal of Theoretical Physics, No. 21, pp. 219-253, 1982
[2] G. Brassard, S.L. Braunstein, and R. Cleve, "Teleportation as a quantum computation", Physica D: Nonlinear Phenomena, 120(1- 2):43{47, 1998.
[3] C. P. Williams and S. H. Clearwater, "Explorations in quantum computing". Springer- Verlag, TELNOS, 1997.
[4] C. Veiri, A. Josephine and M. Frank, "A fully Reversible Asymptotically Zero Energy Microprocessor", MIT AI Laboratory, 1998
[5] C. P. Williams and S. H. Clearwater, "Exploration in Quantum Computing", Springer-Verlag, 1998.
[6] L. Spector, H. Barnum, H. J. Bernstein, and N. Swamy, "Quantum computing applications of genetic programming". Advances in Genetic Programming, 1999.
[7] C. P. Williams and G. G. Alexander, "Automated design of quantum circuits", QCQC'98, LNCS, 1999.
[8] M. Nielsen and I. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, (2000)
[9] T. Yabuki and H. Iba, "Genetic algorithms for quantum circuit design - Evolving a simpler teleportation circuit". In Late Breaking Papers at GECCO 2000.
[10] B.I.P. Rubinstein, "Evolving quantum circuits using genetic programming", Proceedings of the 2001 Congress on Evolutionary Computation, 2001
[11] M. Lukac and M. Perkowski, "Evolving quantum circuits using genetic algorithm", Proceedings of th1e 2002 NASA/DOD Conference on Evolvable Hardware, 2002.
[12] M. Lukac, M. Perkowski, H. Goi, M. Pivtoraiko, C. H. Yu, K. Chung, H. Jee, B. G. Kim and Y. D. Kim, "Evolutionary Approach To Quantum And Reversible Circuits Synthesis", 2003
[13] V.V. Shende, S. S. Bullock, I. L. Markov, "Synthesis of Quantum Logic Circuits", Quantum Physics, quant-ph/0406176, 2004
[14] A. Younes and J. Miller, "Representation of Boolean Quantum Circuits as Reed-Muller Expansions", International Journal of Electronics, Vol. 91, No. 7, 2004
[15] A. Chakrabarti and S. S. Kolay, "Rules for Synthesizing Quantum Boolean Circuits Using Minimized Nearest Neighbor Templates", 15th International Conference on Advanced Computing and Communication, 2007
[16] A. Younes and J. Miller, "Automated Method for Building CNOT based Quantum Circuits for Boolean Functions"
[17] D. Mukherjee, A. Chakrabarti, D. Bhattacherjee, "Synthesis of Quantum Circuits Using Genetic Algorithm", International Journal of Recent Trends in Engineering, Vol 2, No. 1, November 2009
[18] D. Mukhopadhyay and A. Si, "Quantum Multiplexer Desigining and Optimization applying Genetic Algorithm", International Journal of Computer Science, Vol. 7, Issue 5, 2010