Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Quantum Information Processing
Erschienen in: Quantum Information Processing 3/2014

01.03.2014

A quantum genetic algorithm with quantum crossover and mutation operations

verfasst von: Akira SaiToh, Robabeh Rahimi, Mikio Nakahara

Erschienen in: Quantum Information Processing | Ausgabe 3/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel An alternate quantum adiabatic evolution for the Deutsch–Jozsa problem
Nächster Artikel Quantum decision tree classifier

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
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.
 
Literatur
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
Metadaten
Titel
A quantum genetic algorithm with quantum crossover and mutation operations
verfasst von
Akira SaiToh
Robabeh Rahimi
Mikio Nakahara
Publikationsdatum
01.03.2014
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 3/2014
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-013-0686-6

Weitere Artikel der Ausgabe 3/2014

Quantum Information Processing 3/2014 Zur Ausgabe

BriefCommunication

An alternate quantum adiabatic evolution for the Deutsch–Jozsa problem

OriginalPaper

Trojan horse attack free fault-tolerant quantum key distribution protocols

OriginalPaper

Flexible protocol for quantum private query based on B92 protocol

OriginalPaper

Efficient joint remote preparation of an arbitrary two-qubit state via cluster and cluster-type states

OriginalPaper

Decoherence effects in the quantum qubit flip game using Markovian approximation

OriginalPaper

Quantum coding in non-inertial frames

Neuer Inhalt

    Bildnachweise