Article

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

Authors:

Mircea VlăduţiuAuthors Info & Claims

CF '06: Proceedings of the 3rd conference on Computing frontiers

Pages 71 - 82

https://doi.org/10.1145/1128022.1128034

Published: 03 May 2006 Publication History

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]

E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Computing 26(5): 141173, 1997.

Digital Library

[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.

Digital Library

[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.

Digital Library

[13]

M. Lukac, M. Perkowski, H. Goi, M. Pivtoraiko, H.-Y. Chung, K. Chung, H. Jeech, K. Byung-Guk, and K. Yong-Duk. Evolutionary approach to quantum and reversible circuits synthesis.Artificial Intelligence Review 20(3-4): 361--417, 2003.

Digital Library

[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]

M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information Cambridge University Press, Cambridge, 2000.

Digital Library

[17]

B. Omer. Quantum programming in QCL Technical Report,Institute of Information Systems, Technical of Vienna, Vienna,2000.

[18]

M. Oskin, F. Chong, and I. Chuang. A practical architecture for reliable quantum computers. IEEE Computer 35(1):79--87, 2002.

Digital Library

[19]

B. Parhami. Computer Arithmetic. Algorithms and Hardware Designs Oxford University Press, Oxford, 2000.

Digital Library

[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]

L. Prodan, M. Udrescu, and M. Vlăţdutiu. Survivability of embryonic memories:Analysis and design principles.In Proc. IEEE NASA/DoD Conference on Evolvable Hardware (EH'05)pages 280--289, 2005.

Digital Library

[22]

B. Rylander, T. Soule, and J. Foster. Computational complexity, genetic programming, and implications. In Proc. 4th EuroGP pages 348--360,2001.

Digital Library

[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.

Digital Library

[25]

L. Spector. Automatic Quantum Computer Programming: A Genetic Programming Approach Kluwer Academic Publishers, Boston, 2004.

Digital Library

[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.

Digital Library

[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]

M. Udrescu, L. Prodan, and M. Vlăţdutiu. Improving quantum circuit dependability with recon.gurable quantum gate arrays.In Proceedings 2nd ACM Conference on Computing Frontiers pages 133--144. Ischia,Italy,May 2005.

Digital Library

[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.

Cited By

Ardelean SUdrescu M(2024)Hybrid quantum search with genetic algorithm optimizationPeerJ Computer Science10.7717/peerj-cs.221010(e2210)Online publication date: 5-Aug-2024
https://doi.org/10.7717/peerj-cs.2210
Ibarrondo RGatti GSanz M(2024)Quantum Genetic Algorithm With Individuals in Multiple RegistersIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.329678028:3(788-797)Online publication date: Jun-2024
https://doi.org/10.1109/TEVC.2023.3296780
Acampora GVitiello A(2024)Improving Quantum Genetic Algorithms through Recursive Search Space Exploration2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612000(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612000
Show More Cited By

Index Terms

Implementing quantum genetic algorithms: a solution based on Grover's algorithm
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Spin---orbit hybrid entangled channel for spin state quantum teleportation using genetic algorithms

We present a physical model of spin quantum teleportation protocol (QTP) in a triple quantum dot array using a genetic algorithm approach. The information to teleport is spin-coded in one electron confined in a single quantum dot (SQD). The remaining ...
Evolution of a human-competitive quantum fourier transform algorithm using genetic programming
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

In this paper, we show how genetic programming (GP) can be used to evolve system-size-independent quantum algorithms, and present a human-competitive Quantum Fourier Transform (QFT) algorithm evolved by GP.
Neural network crossover in genetic algorithms using genetic programming
Abstract
The use of genetic algorithms (GAs) to evolve neural network (NN) weights has risen in popularity in recent years, particularly when used together with gradient descent as a mutation operator. However, crossover operators are often omitted from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CF '06: Proceedings of the 3rd conference on Computing frontiers

May 2006

430 pages

ISBN:1595933026

DOI:10.1145/1128022

General Chairs:
Monica Alderighi
IASF - INAF
,
Valentina Salapura
IBM
,
Program Chair:
Sally A. McKee
Cornell University

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CF06

Sponsor:

CF06: Computing Frontiers Conference

May 3 - 5, 2006

Ischia, Italy

Acceptance Rates

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
1,285
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)11

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ardelean SUdrescu M(2024)Hybrid quantum search with genetic algorithm optimizationPeerJ Computer Science10.7717/peerj-cs.221010(e2210)Online publication date: 5-Aug-2024
https://doi.org/10.7717/peerj-cs.2210
Ibarrondo RGatti GSanz M(2024)Quantum Genetic Algorithm With Individuals in Multiple RegistersIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.329678028:3(788-797)Online publication date: Jun-2024
https://doi.org/10.1109/TEVC.2023.3296780
Acampora GVitiello A(2024)Improving Quantum Genetic Algorithms through Recursive Search Space Exploration2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612000(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612000
Tandeitnik DGuerreiro T(2024)Evolving quantum circuitsQuantum Information Processing10.1007/s11128-024-04317-w23:3Online publication date: 15-Mar-2024
https://doi.org/10.1007/s11128-024-04317-w
Khelfa CDrias HKhennak I(2024)Quantum Slime Mould Algorithm and Application to Urgent TransportationQuantum Computing: Applications and Challenges10.1007/978-3-031-59318-5_7(77-90)Online publication date: 1-Jun-2024
https://doi.org/10.1007/978-3-031-59318-5_7
Altares-López SGarcía-Ripoll JRibeiro A(2023)AutoQML: Automatic generation and training of robust quantum-inspired classifiers by using evolutionary algorithms on grayscale imagesExpert Systems with Applications10.1016/j.eswa.2023.122984(122984)Online publication date: Dec-2023
https://doi.org/10.1016/j.eswa.2023.122984
Letia TDurla-Pasca EAl-Janabi DCuibus O(2022)Development of Evolutionary Systems Based on Quantum Petri NetsMathematics10.3390/math1023440410:23(4404)Online publication date: 22-Nov-2022
https://doi.org/10.3390/math10234404
Ibarrondo RGatti GSanz M(2022)Quantum vs classical genetic algorithms: A numerical comparison shows faster convergence2022 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI51031.2022.10022159(947-954)Online publication date: 4-Dec-2022
https://doi.org/10.1109/SSCI51031.2022.10022159
Kim JAhn C(2022)Size-efficient sparse population for strictly structured quantum genetic algorithmFuture Generation Computer Systems10.1016/j.future.2022.04.030135:C(159-171)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.future.2022.04.030
Singh JBhangu K(2022)Contemporary Quantum Computing Use Cases: Taxonomy, Review and ChallengesArchives of Computational Methods in Engineering10.1007/s11831-022-09809-530:1(615-638)Online publication date: 26-Sep-2022
https://doi.org/10.1007/s11831-022-09809-5
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents