Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Quantum Information Processing
Published in: Quantum Information Processing 3/2014

01-03-2014

A quantum genetic algorithm with quantum crossover and mutation operations

Authors: Akira SaiToh, Robabeh Rahimi, Mikio Nakahara

Published in: Quantum Information Processing | Issue 3/2014

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the context of evolutionary quantum computing in the literal meaning, a quantum crossover operation has not been introduced so far. Here, we introduce a novel quantum genetic algorithm that has a quantum crossover procedure performing crossovers among all chromosomes in parallel for each generation. A complexity analysis shows that a quadratic speedup is achieved over its classical counterpart in the dominant factor of the run time to handle each generation.
previous article An alternate quantum adiabatic evolution for the Deutsch–Jozsa problem
next article Quantum decision tree classifier

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
There is another drawback in the use of a quantum fixed-point search. It requires phase shift operations \(\widetilde{U}_\mathrm{s}=1-(1-e^{i\pi /3})\sum _l|\varsigma _l\rangle \langle \varsigma _l|\) and \(\widetilde{U}_\mathrm{t}=1-(1-e^{i\pi /3})|\tau _m\rangle \langle \tau _m|\) with source states \(|\varsigma _l\rangle \) and target states \(|\tau _m\rangle \) (\(l\) and \(m\) are labels) in addition to another appropriate unitary operation [14]. One may alternatively use \({\hat{U}_\mathrm{s}}=1-(1-e^{i\pi /3})|\mathcal {S}\rangle \langle \mathcal {S}|\) and \({\hat{U}_\mathrm{t}}=1-(1-e^{i\pi /3})|\mathcal {T}\rangle \langle \mathcal {T}|\) where \(|\mathcal {S}\rangle \) is an equally weighted superposition of \(|\varsigma _l\rangle \) and \(|\mathcal {T}\rangle \) is an equally weighted superposition of \(|\tau _m\rangle \). (This kind of alternative operation for a quantum search was used in Ref. [47].) The problem is that \(\varsigma _l\)’s are highly random nonconsecutive chromosomes in the context of evolutionary computing. There is no known way to construct \(\widetilde{U}_\mathrm{s}\) or \(\hat{U}_\mathrm{s}\) within \(\mathrm{poly}(\log \widetilde{N})\) cost in such a case, where \(\widetilde{N}\) is the number of \(\varsigma _l\)’s.
 
Literature
1.
Ahuja, A., Kapoor, S.: A Quantum Algorithm for Finding the Maximum (1999). arXiv:quant-ph/9911082
2.
Barnum, H., Bernstein, H.J., Spector, L.: A Quantum Circuit for OR (1999). arXiv:quant-ph/9907056
3.
Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys. 46, 493–505 (1998)CrossRef
4.
Brassard, G., Høyer, P., Tapp, A.: Quantum counting. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) Proceedings of Automata, Languages and Programming, 25th International Colloquium (ICALP’98) (LNCS 1443), pp. 820–831. Aalborg, Denmark, 13–17 July 1998, Springer, Berlin (1998). arXiv:quant-ph/9805082
5.
Chakraborty, S., Radhakrishnan, J., Raghunathan, N.: Bounds for error reduction with few quantum queries. In: Chekuri, C., Jansen, K., Rolim, J., Trevisan, L. (eds.) Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM 2005) (LNCS 3624), pp. 245–256. Berkeley, CA, 22–24 August 2005. Springer, Berlin (2005)
6.
Chen, M., Quan, H.: Quantum-inspired evolutionary algorithm based on estimation of distribution. In: Proceedings of the 2nd International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2007), pp. 17–19. Zhengzhou, China, 14–17 September 2007. IEEE Press, Piscataway, NJ (2007)
7.
Ding, S., Jin, Z., Yang, Q.: Evolving Quantum Oracles with Hybrid Quantum-Inspired Evolutionary Algorithm (2006). arXiv:quant-ph/0610105
8.
Dürr, C., Høyer, P.: A Quantum Algorithm for Finding the Minimum (1996). arXiv:quant-ph/9607014
9.
Gepp, A., Stocks, P.: A Review of Procedures to Evolve Quantum Algorithms (2007). arXiv:0708.3278
10.
Giraldi, G.A., Portugal, R., Thess, R.N.: Genetic Algorithms and Quantum Computation (2004). arXiv:cs/0403003
11.
Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA (1989)MATH
12.
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 212–219. Philadelphia, PA, 22–24 May 1996. ACM Press, New York, NY (1996)
13.
Grover, L.K.: Quantum Search on Structured Problems (1998). arXiv:quant-ph/9802035
14.
Grover, L.K.: Fixed-point quantum search. Phys. Rev. Lett. 95, 150501-1–150501-4 (2005)
15.
Gruska, J.: Quantum Computing. McGraw-Hill, London (1999)
16.
Han, K.H., Kim, J.H.: Genetic quantum algorithm and its application to combinatorial optimization problem. In: Proceedings of the 2000 Congress on Evolutionary Computation (CEC2000), pp. 1354–1360. La Jolla, CA, 16–19 July 2000. IEEE Press, Piscataway, NJ (2000)
17.
Han, K.H., Kim, J.H.: Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE Trans. Evol. Comput. 6(6), 580–593 (2002)CrossRef
18.
Han, K.H., Kim, J.H.: Quantum-inspired evolutionary algorithms with a new termination criterion, \(h_{\epsilon }\) gate, and two-phase scheme. IEEE Trans. Evol. Comput. 8(2), 156–169 (2004)CrossRef
19.
Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. The University of Michigan Press, Ann Arbor, MI (1975)
20.
Johannsen, D., Kuru, P.P., Lengler, J.: Can quantum search accelerate evolutionary algorithms? In: Pelikan, M., Branke, J. (eds.) Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference (GECCO-2010), pp. 1433–1440. Portland, OR, 7–11 July 2010. ACM, New York, NY (2010)
21.
Knuth, D.E.: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed, Chap. 3. Addison-Wesley, Reading, MA (1997)
22.
Leier, A., Banzhaf, W.: Evolving Hogg’s quantum algorithm using linear-tree GP. In: Cantú-Paz, E., Foster, J.A., Deb, K., Davis, L.D., Roy, R., O’Reilly, U.M., Beyer, H.G., Standish, R., Kendall, G., Wilson, S., Harman, M., Wegener, J., Dasgupta, D., Potter, M.A., Schultz, A.C., Dowsland, K.A., Jonoska, N., Miller, J. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference 2003 (GECCO-2003), Part I (LNCS 2723), pp. 390–400. Chicago, IL, 12–16 July 2003. Springer, Berlin (2003)
23.
Leier, A., Banzhaf, W.: Comparison of selection strategies for evolutionary quantum circuit design. In: Deb, K. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference 2004 (GECCO-2004), Part II (LNCS 3103), pp. 557–568. Seattle, WA, 26–30 June 2004. Springer, Berlin (2004)
24.
Liao, R., Wang, X., Qin, Z.: A novel quantum-inspired genetic algorithm with expanded solution space. In: Proceedings of the 2010 Second International Conference on Intelligent Human–Machine Systems and Cybernetics (IHMSC 2010), pp. 192–195. Nanjing, China, 26–28 August 2010. IEEE Computer Society, Los Alamitos, CA (2010)
25.
Lukac, M., Perkowski, M.: Evolving quantum circuits using genetic algorithm. In: Stoica, A., Keymeulen, D., Lohn, J. (eds.) Proceedings of the 2002 NASA/DoD Conference on Evolvable Hardware, pp. 177–181. Alexandria, VA, 15–18 July 2002. IEEE Computer Society, Los Alamitos, CA (2002)
26.
Lukac, M., Perkowski, M., Goi, H., Pivtoraiko, M., Yu, C.H., Chung, K., Jee, H., Kim, B.G., Kim, Y.D.: Evolutionary approach to quantum and reversible circuits synthesis. In: Yanushkevich, S.N. (ed.) Artificial Intelligence in Logic Design, pp. 201–257. Kluwer, Dordrecht (2004)CrossRef
27.
28.
Malossini, A., Blanzieri, E., Calarco, T.: Quantum genetic optimization. IEEE Trans. Evol. Comput. 12(2), 231–241 (2008)CrossRef
29.
Massey, P., Clark, J.A., Stepney, S.: Evolving quantum circuits and programs through genetic programming. In: Deb, K. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference 2004 (GECCO-2004), Part II (LNCS 3103), pp. 569–580, Seattle, WA, 26–30 June 2004. Springer, Berlin (2004)
30.
Massey, P., Clark, J.A., Stepney, S.: Human-competitive evolution of quantum computing artefacts by genetic programming. Evol. Comput. 14(1), 21–40 (2006)CrossRef
31.
32.
Mitchell, M.: An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA (1996)
33.
Mohammed, A.M., Elhefnawy, N.A., El-Sherbiny, M.M., Hadhoud, M.M.: Quantum crossover based quantum genetic algorithm for solving non-linear programming. In: Proceedings of the 8th International Conference on INFOrmatics and Systems (INFOS2012), pp. BIO-145-153. Cairo, Egypt, 14–16 May 2012. IEEE, Piscataway, NJ (2012)
34.
Nakayama, S., Imabeppu, T., Ono, S.: Pair swap strategy in quantum-inspired evolutionary algorithm (2006). In: The Late-breaking papers of the 2006 Genetic and Evolutionary Computation Conference (GECCO-2006), Seattle, WA, 8–12 July 2006
35.
Nakayama, S., Imabeppu, T., Ono, S., Iimura, I.: Consideration on pair swap strategy in quantum-inspired evolutionary algorithm. IEICE Trans. Inf. Sys. J89-D(9), 2134–2139 (2006) (in Japanese)
36.
Narayanan, A., Moore, M.: Quantum-inspired genetic algorithms. In: Proceedings of the IEEE 3rd International Conference on Evolutionary Computation (ICEC96), pp. 61–66. Nagoya, Japan, 20–22 May 1996. IEEE Press, Piscataway, NJ (1996)
37.
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH
38.
Rubinstein, B.I.P.: Evolving quantum circuits using genetic programming. In: Proceedings of the 2001 Congress on Evolutionary Computation (CEC2001), pp. 144–151. Seoul, Korea, 27–30 May 2001. IEEE Press, Piscataway, NJ (2001)
39.
40.
Rylander, B., Soule, T., Foster, J., Alves-Foss, J.: Quantum evolutionary programming. In: Spector, L., Goodman, E.D., Wu, A., Langdon, W.B., Voigt, H.M., Gen, M., Sen, S., Dorigo, M., Pezeshk, S., Garzon, M.H., Burke, E. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 1005–1011. San Francisco, CA, 7–11 July 2001. Morgan Kaufmann, San Francisco (2001)
41.
Sofge, D.A.: Prospective algorithms for quantum evolutionary computation. In: Bruza, P.D., Lawless, W., van Rijsbergen, K., Sofge, D.A., Coecke, B., Clark, S. (eds.) Proceedings of the 2nd Quantum Interaction Symposium (QI-2008), pp. 98–105. Oxford, UK, 26–28 March 2008. College Publications, London (2008). arXiv:0804.1133
42.
Soklakov, A.N., Schack, R.: Efficient state preparation for a register of quantum bits. Phys. Rev. A 73, 012307-1–012307-13 (2006)
43.
Spector, L.: Automatic Quantum Computer Programming: A Genetic Programming Approach. Springer, New York (2004, Paperback Ed. 2007)
44.
Spector, L., Barnum, H., Bernstein, H.: Genetic programming for quantum computers. In: Koza, J.R. (eds.) Genetic Programming 1998: Proceedings of the Third Annual Conference (GP-98), pp. 365–374. Madison, WI, 22–25 July 1998. Morgan Kaufmann, San Francisco (1998)
45.
Spector, L., Barnum, H., Bernstein, H., Swamy, N.: Finding a better-than-classical quantum AND/OR algorithm using genetic programming. In: Proceedings of the 1999 Congress on Evolutionary Computation (CEC1999), pp. 2239–2246. Washington, D.C., 6–9 July 1999. IEEE Press, Piscataway, NJ (1999)
46.
Spector, L., Klein, J.: Machine invention of quantum computing circuits by means of genetic programming. AI EDAM 22, 275–283 (2008)
47.
Tanaka, Y., Ichikawa, T., Tada-Umezaki, M., Ota, Y., Nakahara, M.: Quantum oracles in terms of universal gate set. Int. J. Quant. Inf. 9, 1363–1381 (2011)MathSciNetCrossRefMATH
48.
Tulsi, T., Grover, L.K., Patel, A.: A new algorithm for fixed point quantum search. Quant. Inf. Comput. 6, 483–494 (2006)MathSciNetMATH
49.
50.
Udrescu, M., Prodan, L., Vlăduţiu, M.: Implementing quantum genetic algorithms: a solution based on Grover’s algorithm. In: Proceedings of the 3rd Conference on Computing Frontiers, pp. 71–81. Ischia, Italy, 3–5 May 2006. ACM Press, New York (2006)
51.
Ventura, D., Martinez, T.: Initializing the amplitude distribution of a quantum state. Found. Phys. Lett. 12, 547–559 (1999)MathSciNetCrossRef
52.
Williams, C.P., Gray, A.G.: Automated design of quantum circuits. In: Williams, C.P. (eds.) Quantum Computing and Quantum Communications: First NASA International Conference (LNCS 1509), pp. 113–125. Palm Springs, CA, 17–20 February 1998. Springer, Berlin (1999)
53.
Yabuki, T., Iba, H.: Genetic algorithms for quantum circuit design-evolving a simpler teleportation circuit. In: Whitley, L.D., Goldberg, D.E., Cantú-Paz, E., Spector, L., Parmee, I.C., Beyer, H.G. (eds.) Proceedings of the 2000 Genetic and Evolutionary Computation Conference (GECCO-2000), pp. 425–430. Las Vegas, NV, 8–12 July 2000. Morgan Kaufmann, San Francisco (2000)
54.
Zhang, G.: Quantum-inspired evolutionary algorithms: a survey and empirical study. J. Heuristics 17, 303–351 (2011)CrossRefMATH
Metadata
Title
A quantum genetic algorithm with quantum crossover and mutation operations
Authors
Akira SaiToh
Robabeh Rahimi
Mikio Nakahara
Publication date
01-03-2014
Publisher
Springer US
Published in
Quantum Information Processing / Issue 3/2014
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-013-0686-6

Other articles of this Issue 3/2014

Quantum Information Processing 3/2014 Go to the issue

OriginalPaper

Trojan horse attack free fault-tolerant quantum key distribution protocols

OriginalPaper

Perfect state transfer on spin-1 chains

OriginalPaper

A quantum approach to play asymmetric coordination games

OriginalPaper

Quantum coding in non-inertial frames

OriginalPaper

Minimal resources identifiability and estimation of quantum channels

OriginalPaper

Entangled spin states in geodesic motion around massive body