1. the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result;
a) Size-Efficient Sparse Population for Strictly Structured Quantum Genetic Algorithm
b) Quantum Strategy of Population Initialization in Genetic Algorithm
2. the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s);
a) Jun Suk Kim; EECS Building A #514, Gwangju Institute of Science and Technology, Bukgu 123 Cheomdangwagiro, South Korea; junsuk89@gmail.com; +82-627152664
Chang Wook Ahn; EECS Building A #502, Gwangju Institute of Science and Technology, Bukgu 123 Cheomdangwagiro, South Korea; cwan@gist.ac.kr;+82-627153169
b) Jun Suk Kim; EECS Building A #514, Gwangju Institute of Science and Technology, Bukgu 123 Cheomdangwagiro, South Korea; junsuk89@gmail.com; +82-627152664
Chang Wook Ahn; EECS Building A #502, Gwangju Institute of Science and Technology, Bukgu 123 Cheomdangwagiro, South Korea; cwan@gist.ac.kr; +82-627153169
3. the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition);
Chang Wook Ahn
4. the abstract of the paper(s);
a)Quantum genetic algorithm is a field of research to discover a potential structure to realize an effective heuristic, evolutionary optimization technique powered by quantum computation. Apart from contemporary efforts to look for a novel quantum evolutionary design, some studies suggest the idea of strictly structured quantum genetic algorithm, which rigorously imitates the classical practice via a sparse population to sample a few individuals from the given problem's domain, as opposed to the conventional quantum practice that transforms the entire domain into a population itself. Albeit having its own advantages, the algorithm requires to periodically measure and reinitialize the quantum system over generations. It therefore leads to several computational inefficiency issues including the wasteful population initialization, during which individuals that rather marginally contribute to the overall optimization are iteratively generated. This paper proposes that the algorithmic inefficiency from the mentioned problem can be alleviated by preemptively eliminating a large portion of undesirable individuals and still maintain the tasked optimization result to an acceptable degree. The main idea is to deliberately reduce the amount of randomness among the quantum population, thereby discarding individuals that do not contain any fitted genes. A number of tests were conducted on continuous optimization problems to validate the theory of the proposed method, resulting that it can effectively reduce the size of the involved population while minimizing the loss in the original algorithm's performance.
b)Quantum computing's main features include quantum superposition and entanglement, which enable parallel computation and thus the anticipated speedup over classical computers. It is therefore not surprising to see that quantum optimization is currently one of the most highlighted fields in quantum computing. For example, quantum approximate optimization algorithm (QAOA) is actively studied by multiple researchers who are looking for solving combinatorial optimization problems with near-term, intermediate scale quantum computers. Similarly, efforts to solve quantum optimization problems with evolutionary processes via Quantum Genetic Algorithm (QGA) have also been made for nearly two decades.
5. a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies;
a) B
b) D, G
6. a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission);
a) In this entry paper, we introduced an improved version of the semi-classical quantum genetic algorithm, which was first proposed by Saitoh et al. in 2014. The original algorithm had a problem of excessively generating relatively unnecessary individuals with low fitness values in each generation, requiring a high number of the Grover iterations to perform the quantum selection operator. Our suggestion alleviates the issue by deliberately removing the XOR-gate-connections between the quantum registers, thereby getting rid of purely random individuals from the population. Compared to the original semi-classical quantum genetic algorithm, such alteration reduces the required number of the Grover iterations and thus the overall time complexity of the whole optimization procedure.
b) This entry paper suggests a strategy that applies the quantum counting algorithm to genetic algorithms, which was never proposed or implied in precedent studies. The quantum counting algorithm counts the number of items from a list that satisfy the given criteria quadratically faster than any known classical counterparts, and we discovered that the ability can be adopted to genetic algorithms to detect the number of individuals in the initial population that do not violate the given constraints, providing a chance to discard and pass generations in which the population does not possess any eligible individuals. We also provide the proper adjustment of the number of interation for the quantum counting algorithm to not exceed the computational complexity of the original genetic algorithm, so the overall algorithmic efficiency remains roughly the same. We believe that this study contributes to resolving the issue of appropriately setting the initial population for genetic algorithm, which has been an intrinstic problem in the field.
7. a full citation of the paper (that is, author names; title, publication date; name of journal, conference, or book in which article appeared; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable);
a) Jun Suk Kim, Chang Wook Ahn; Size-Efficient Sparse Population for Strictly Stuctured Quantum Genetic Algorithm; Future Generation Computer Systems; Michela Taufer, Ph.D.; Amsterdam, Netherlands
b) Jun Suk Kim, Chang Wook Ahn; Quantum Strategy of Population Initialization in Genetic Algorithm; GECCO 2022; Jonathan Fieldsend, Ph.D.
8. a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors;
Any prize money, if any, is to be divided equally among the co-authors.
9. a statement stating why the authors expect that their entry would be the "best," and
Quantum computing is still in the initial stage, and no one is yet to predict its full potential in terms of the future of computer and information science. In the perspective of regarding genetic algorithm as an automated procedure to surpass the human ability to accomplish an equaivalent task, we deem that quantum computing can provide an important breakthrough to genetic algorithm with respect to its ability to considerably enhance the algorithm's computational efficiency.
10. An indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GI (genetic improvement), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc.
a) GA
b) GA
11. The date of publication of each paper. If the date of publication is not on or before the deadline for submission, but instead, the paper has been unconditionally accepted for publication and is “in press” by the deadline for this competition, the entry must include a copy of the documentation establishing that the paper meets the "in press" requirement.
a) In press
b) In press