Implementing quantum genetic algorithms: a solution based on Grover's algorithm

ABSTRACT

This paper presents a new methodology for running Genetic Algorithms on a Quantum Computer. To the best of our knowledge and according to reference [6]there are no feasible solutions for the implementation of the Quantum Genetic Algorithms (QGAs). We present a new perspective on how to build the corresponding QGA architecture. It turns out that the genetic strategy is not particularly helpful in our quantum computation approach; therefore our solution consists of designing a special-purpose oracle that will work with a modified version of an already known algorithm (maximum finding [1]), in order to reduce the QGAs to a Grover search. Quantum computation offers incentives for this approach, due to the fact that the qubit representation of the chromosome can encode the entire population as a superposition of basis-state values.

REFERENCES

• 1: A. Ahuja and S. Kapoor. A quantum algorithm for finding the maximum. ArXiv:quant-ph/9911082 1999.
• 2: A. Barenco, C. H. Bennett, R. Cleve, D. P. Vincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Phys. Rev. A(52): 3457--3467, 1995.
• 3: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 4: M. Boyer, G. Brassard, P. Hoyer, and A. Tapp. Tight bounds on quantum searching. Fort sch. Phys - Prog. Phys. 46(4-5):493--505, 1998.
• 5: C. Durr and P. Hoyer. A quantum algorithm for finding the minimum. ArXiv: quant-ph/9607014 1996.
• 6: G. Giraldi, R. Portugal, and R. Thess. Genetic algorithms and quantum computation. ArXiv:cs.NE/0403003 2004.
• 7: P. Gossett. Quantum carry-save arithmetic. quant-ph/9808061 1998.
• 8: L. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett.79: 325--328, 1997.
• 9: K.-H. Han and J.-H. Kim. Genetic quantum algorithm and its application to combinatorial optimization problem. In Proc. of the 2000 Congress on Evolutionary Computation citeseer.nj.nec.com/han00genetic.html, 2000.
• 10: K.-H. Han and J.-H. Kim. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization.IEEE Transactions on Evolutionary Computation 6(6):580--593, 2002.
• 11: T. Hogg. Highly structured searches with quantum computers. Phys. Rev. Lett.80:2473--2476,1998.
• 12: A. Leier and W. Banzhaf. Evolving hogg's quantum algorithm using linear-tree gp. In Proc. Genetic and Evolutionary Computation Conference (GECCO) pages 390--400, 2003.
• 13: Martin Lukac , Marek Perkowski , Hilton Goi , Mikhail Pivtoraiko , Chung Hyo Yu , Kyusik Chung , Hyunkoo Jeech , Byung-Guk Kim , Yong-Duk Kim, Evolutionary Approach to Quantum andReversible Circuits Synthesis, Artificial Intelligence Review, v.20 n.3-4, p.361-417, December 2003 [doi>10.1023/B:AIRE.0000006605.86111.79]
• 14: D. Mange, M. Sipper, A. Stauffer, and G. Tempesti. Toward robust integrated circuits:The embryonics approach. Proc. IEEE 88(4): 516--541,2000.
• 15: A. Narayanan and M. Moore. Quantum-inspired genetic algorithms.In Proc. International Conference on Evolutionary Computation (ICEC-96)pages 61--66. IEEE,1 996.
• 16: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 17: B. Omer. Quantum programming in QCL Technical Report,Institute of Information Systems, Technical of Vienna, Vienna,2000.
• 18: Mark Oskin , Frederic T. Chong , Isaac L. Chuang, A Practical Architecture for Reliable Quantum Computers, Computer, v.35 n.1, p.79-87, January 2002 [doi>10.1109/2.976922]
• 19: Behrooz Parhami, Computer arithmetic: algorithms and hardware designs, Oxford University Press, Oxford, 1999
• 20: L. Prodan, M. Udrescu, and M. Vlăţdutiu. Self-repairing embryonic memory arrays.In Proc. IEEE NASA/DoD Conference on Evolvable Hardware, Seattle pages 130--137, 2004.
• 21: Survivability of Embryonic Memories: Analysis and Design Principles, Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware, p.280-289, June 29-July 01, 2005 [doi>10.1109/EH.2005.44]
• 22: Bart Rylander , Terence Soule , James A. Foster, Computational Complexity, Genetic Programming, and Implications, Proceedings of the 4th European Conference on Genetic Programming, p.348-360, April 18-20, 2001
• 23: B. Rylander, T. Soule, J. Foster, and J. Alves-Foss. Quantum evolutionary programming. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)pages 1005--1011, 2001.
• 24: P. W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proc. 35th Symposium on Foundations of Computer Science pages 124--134,1994.
• 25: L. Spector. Automatic Quantum Computer Programming: A Genetic Programming Approach Kluwer Academic Publishers, Boston, 2004.
• 26: L. Spector, H. Barnum, and H. Bernstein. Genetic programming for quantum computers. In Genetic Programming 1998: Proceedings of the Third Annual Conference, Madison, Wisconsin pages 365--373,1998.
• 27: L. Spector, H. Barnum, H. Bernstein, and N. Swamy. Quantum computing applications of genetic programming. Advances in Genetic Programming 3(7):135--160,1998.
• 28: L. Spector, H. Barnum, H. Bernstein, and N. Swamy. Finding a better-than-classical quantum and/or algorithm using genetic programming. In Proceedings of 1999 Congress of Evolutionary Computation, Piscataway, NJ pages 2239--2246.IEEE,1999.
• 29: Mihai Udrescu , Lucian Prodan , Mircea Vlǎduţiu, Improving quantum circuit dependability with reconfigurable quantum gate arrays, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy [doi>10.1145/1062261.1062286]
• 30: V. Vedral, A. Barenco, and A. Ekert.uantum networks for elementary arithmetic operations. quant-ph/9511018 1996.
• 31: G. Viamontes, I. Markov, and J. P. Hayes.I s quantum search practical?In International Workshop on Logic and Synthesis pages 478--485,2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Theory

Keywords:
genetic algorithms, quantum computing