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

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.

Authors:

• Swanti Satsangi
• Ashish Gulati
• Prem Kumar Kalra
• C. Patvardhan

Keywords:

• Ancillas
• Boolean functions
• Genetic algorithm
• Oracles
• Quantum circuits
• Scratch bit

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