{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T07:23:41Z","timestamp":1786433021768,"version":"build-2736575974"},"reference-count":41,"publisher":"PeerJ","license":[{"start":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T00:00:00Z","timestamp":1722816000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Quantum genetic algorithms (QGA) integrate genetic programming and quantum computing to address search and optimization problems. The standard strategy of the hybrid QGA approach is to add quantum resources to classical genetic algorithms (GA), thus improving their efficacy (<jats:italic>i.e.<\/jats:italic>, quantum optimization of a classical algorithm). However, the extent of such improvements is still unclear. Conversely, Reduced Quantum Genetic Algorithm (RQGA) is a fully quantum algorithm that reduces the GA search for the best fitness in a population of potential solutions to running Grover\u2019s algorithm. Unfortunately, RQGA finds the best fitness value and its corresponding chromosome (<jats:italic>i.e.<\/jats:italic>, the solution or one of the solutions of the problem) in exponential runtime, O(2<jats:sup>n\/2<\/jats:sup>), where <jats:italic>n<\/jats:italic> is the number of qubits in the individuals\u2019 quantum register. This article introduces a novel QGA optimization strategy, namely a classical optimization of a fully quantum algorithm, to address the RQGA complexity problem. Accordingly, we control the complexity of the RQGA algorithm by selecting a limited number of qubits in the individuals\u2019 register and fixing the remaining ones as classical values of \u20180\u2019 and \u20181\u2019 with a genetic algorithm. We also improve the performance of RQGA by discarding unfit solutions and bounding the search only in the area of valid individuals. As a result, our Hybrid Quantum Algorithm with Genetic Optimization (HQAGO) solves search problems in O(2<jats:sup>(n\u2212k)\/2<\/jats:sup>) oracle queries, where <jats:italic>k<\/jats:italic> is the number of fixed classical bits in the individuals\u2019 register.<\/jats:p>","DOI":"10.7717\/peerj-cs.2210","type":"journal-article","created":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T07:07:07Z","timestamp":1722841627000},"page":"e2210","source":"Crossref","is-referenced-by-count":15,"title":["Hybrid quantum search with genetic algorithm optimization"],"prefix":"10.7717","volume":"10","author":[{"given":"Sebastian Mihai","family":"Ardelean","sequence":"first","affiliation":[{"name":"Department of Computer and Information Technology, University Politehnica of Timisoara,  Timisoara, Timis, Romania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihai","family":"Udrescu","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Technology, University Politehnica of Timisoara,  Timisoara, Timis, Romania"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"4443","published-online":{"date-parts":[[2024,8,5]]},"reference":[{"key":"10.7717\/peerj-cs.2210\/ref-1","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.ins.2021.06.049","article-title":"Implementing evolutionary optimization on actual quantum processors","volume":"575","author":"Acampora","year":"2021","journal-title":"Information Sciences"},{"key":"10.7717\/peerj-cs.2210\/ref-2","article-title":"A quantum algorithm for finding the maximum","author":"Ahuja","year":"1999","journal-title":"arXiv:quant-ph\/9911082"},{"key":"10.7717\/peerj-cs.2210\/ref-3","first-page":"53","article-title":"An extension to the theory of convergence and a proof of the time complexity of genetic algorithms","volume-title":"Foundations of genetic algorithms","volume":"Vol. 1","author":"Ankenbrandt","year":"1991"},{"key":"10.7717\/peerj-cs.2210\/ref-4","first-page":"000155","article-title":"Circuit level implementation of the reduced quantum genetic algorithm using qiskit","author":"Ardelean","year":"2022"},{"key":"10.7717\/peerj-cs.2210\/ref-5","doi-asserted-by":"publisher","first-page":"e836","DOI":"10.7717\/peerj-cs.836","article-title":"Graph coloring using the reduced quantum genetic algorithm","volume":"8","author":"Ardelean","year":"2022","journal-title":"PeerJ Computer Science"},{"key":"10.7717\/peerj-cs.2210\/ref-6","volume-title":"Knapsack problems; methods, models and applications","author":"Badiru","year":"2009"},{"issue":"3","key":"10.7717\/peerj-cs.2210\/ref-7","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1016\/S0377-2217(01)00179-5","article-title":"The nonlinear knapsack problem\u2014algorithms and applications","volume":"138","author":"Bretthauer","year":"2002","journal-title":"European Journal of Operational Research"},{"key":"10.7717\/peerj-cs.2210\/ref-8","article-title":"Quantum plain and carry look-ahead adders","author":"Cheng","year":"2002","journal-title":"arXiv:quant-ph\/0206028"},{"key":"10.7717\/peerj-cs.2210\/ref-9","article-title":"A new quantum ripple-carry addition circuit","author":"Cuccaro","year":"2004","journal-title":"arXiv:quant-ph\/0410184"},{"issue":"2","key":"10.7717\/peerj-cs.2210\/ref-10","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.ejor.2014.05.011","article-title":"On some applications of the selective graph coloring problem","volume":"240","author":"Demange","year":"2015","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"10.7717\/peerj-cs.2210\/ref-11","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s10462-011-9208-z","article-title":"An optimizing BP neural network algorithm based on genetic algorithm","volume":"36","author":"Ding","year":"2011","journal-title":"Artificial Intelligence Review"},{"issue":"6","key":"10.7717\/peerj-cs.2210\/ref-12","doi-asserted-by":"publisher","first-page":"2633","DOI":"10.1007\/s00521-023-09161-0","article-title":"A novel hybrid search strategy for evolutionary fuzzy optimization approach","volume":"36","author":"Escobar-Cuevas","year":"2024","journal-title":"Neural Computing and Applications"},{"key":"10.7717\/peerj-cs.2210\/ref-13","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1016\/j.matcom.2023.12.027","article-title":"A novel optimization approach based on unstructured evolutionary game theory","volume":"219","author":"Escobar-Cuevas","year":"2024","journal-title":"Mathematics and Computers in Simulation"},{"issue":"2","key":"10.7717\/peerj-cs.2210\/ref-14","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10710-009-9080-7","article-title":"A review of procedures to evolve quantum algorithms","volume":"10","author":"Gepp","year":"2009","journal-title":"Genetic Programming and Evolvable Machines"},{"key":"10.7717\/peerj-cs.2210\/ref-15","article-title":"Genetic algorithms and quantum computation. arXiv:cs\/0403003","author":"Giraldi","year":"2004"},{"key":"10.7717\/peerj-cs.2210\/ref-16","first-page":"212","article-title":"A fast quantum mechanical algorithm for database search","author":"Grover","year":"1996"},{"key":"10.7717\/peerj-cs.2210\/ref-17","volume-title":"Computer architecture: a quantitative approach","author":"Hennessy","year":"2018"},{"key":"10.7717\/peerj-cs.2210\/ref-18","article-title":"Quantum computing with Qiskit","author":"Javadi-Abhari","year":"2024"},{"issue":"4","key":"10.7717\/peerj-cs.2210\/ref-19","doi-asserted-by":"publisher","first-page":"24","DOI":"10.3390\/computers5040024","article-title":"Quantum genetic algorithms for computer scientists","volume":"5","author":"Lahoz-Beltra","year":"2016","journal-title":"Computers"},{"key":"10.7717\/peerj-cs.2210\/ref-20","article-title":"The conquest of quantum genetic algorithms: the adventure to cross the valley of death","author":"Lahoz-Beltra","year":"2023"},{"issue":"1","key":"10.7717\/peerj-cs.2210\/ref-21","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1109\/TNN.2002.804317","article-title":"Tuning of the structure and parameters of a neural network using an improved genetic algorithm","volume":"14","author":"Leung","year":"2003","journal-title":"IEEE Transactions on Neural Networks"},{"key":"10.7717\/peerj-cs.2210\/ref-22","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.asoc.2015.04.020","article-title":"Modified cuckoo optimization algorithm (MCOA) to solve graph coloring problem","volume":"33","author":"Mahmoudi","year":"2015","journal-title":"Applied Soft Computing"},{"issue":"3","key":"10.7717\/peerj-cs.2210\/ref-23","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1080\/002075498193688","article-title":"A genetic algorithm approach to scheduling PCBs on a single machine","volume":"36","author":"Maimon","year":"1998","journal-title":"International Journal of Production Research"},{"issue":"2","key":"10.7717\/peerj-cs.2210\/ref-24","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1109\/TEVC.2007.905006","article-title":"Quantum genetic optimization","volume":"12","author":"Malossini","year":"2008","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"10.7717\/peerj-cs.2210\/ref-25","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-642-03211-0_16","article-title":"Genetic algorithm and advanced tournament selection concept","author":"Matou\u0161ek","year":"2009","journal-title":"Nature Inspired Cooperative Strategies for Optimization (NICSO 2008)"},{"issue":"14","key":"10.7717\/peerj-cs.2210\/ref-26","doi-asserted-by":"publisher","first-page":"1639","DOI":"10.1002\/(SICI)1096-987X(19981115)19:14<1639::AID-JCC10>3.0.CO;2-B","article-title":"Automated docking using a Lamarckian genetic algorithm and an empirical binding free energy function","volume":"19","author":"Morris","year":"1998","journal-title":"Journal of Computational Chemistry"},{"issue":"1","key":"10.7717\/peerj-cs.2210\/ref-27","doi-asserted-by":"crossref","first-page":"71","DOI":"10.2478\/v10175-010-0107-2","article-title":"The Knapsack-lightening problem and its application to scheduling HRT tasks","volume":"57","author":"Nawrocki","year":"2009","journal-title":"Bulletin of the Polish Academy of Sciences Technical Sciences"},{"key":"10.7717\/peerj-cs.2210\/ref-28","volume-title":"Quantum computation and quantum information","author":"Nielsen","year":"2002"},{"issue":"3","key":"10.7717\/peerj-cs.2210\/ref-29","doi-asserted-by":"publisher","first-page":"65","DOI":"10.3390\/sym10030065","article-title":"Spectrum graph coloring and applications to Wi-Fi channel assignment","volume":"10","author":"Orden","year":"2018","journal-title":"Symmetry"},{"key":"10.7717\/peerj-cs.2210\/ref-30","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-540-71618-1_20","article-title":"Automatic synthesis for quantum circuits using genetic algorithms","author":"Ruican","year":"2007"},{"key":"10.7717\/peerj-cs.2210\/ref-31","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/978-3-540-78987-1_38","article-title":"A genetic algorithm framework applied to quantum circuit synthesis","volume-title":"Nature inspired cooperative strategies for optimization (NICSO 2007)","author":"Ruican","year":"2008"},{"issue":"3","key":"10.7717\/peerj-cs.2210\/ref-32","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s11128-013-0686-6","article-title":"A quantum genetic algorithm with quantum crossover and mutation operations","volume":"13","author":"SaiToh","year":"2014","journal-title":"Quantum Information Processing"},{"key":"10.7717\/peerj-cs.2210\/ref-33","first-page":"124","article-title":"Algorithms for quantum computation: discrete logarithms and factoring","author":"Shor","year":"1994"},{"key":"10.7717\/peerj-cs.2210\/ref-34","article-title":"Automatic quantum computer programming: a genetic programming approach","volume":"Vol. 7","author":"Spector","year":"2004"},{"key":"10.7717\/peerj-cs.2210\/ref-35","first-page":"693","article-title":"Optimal mutation and crossover rates for a genetic algorithm operating in a dynamic environment","author":"Stanhope","year":"1998"},{"issue":"1","key":"10.7717\/peerj-cs.2210\/ref-36","doi-asserted-by":"publisher","first-page":"21310","DOI":"10.1038\/s41598-022-25812-z","article-title":"Distribution of controlled unitary quantum gates towards factoring large numbers on today\u2019s small-register devices","volume":"12","author":"T\u0103n\u0103sescu","year":"2022","journal-title":"Scientific Reports"},{"issue":"2","key":"10.7717\/peerj-cs.2210\/ref-37","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/j.disopt.2010.12.001","article-title":"Quantum annealing of the graph coloring problem","volume":"8","author":"Titiloye","year":"2011","journal-title":"Discrete Optimization"},{"key":"10.7717\/peerj-cs.2210\/ref-38","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/1128022.1128034","article-title":"Implementing quantum genetic algorithms: a solution based on Grover\u2019s algorithm","author":"Udrescu","year":"2006"},{"issue":"3","key":"10.7717\/peerj-cs.2210\/ref-39","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1006\/jtbi.1995.0098","article-title":"An APL-programmed genetic algorithm for the prediction of RNA secondary structure","volume":"174","author":"Van\u00a0Batenburg","year":"1995","journal-title":"Journal of Theoretical Biology"},{"issue":"3","key":"10.7717\/peerj-cs.2210\/ref-40","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1023\/A:1007934310264","article-title":"A comparison of heuristic search algorithms for molecular docking","volume":"11","author":"Westhead","year":"1997","journal-title":"Journal of Computer-Aided Molecular Design"},{"key":"10.7717\/peerj-cs.2210\/ref-41","first-page":"1234","article-title":"IBM\u2019s Qiskit tool chain: working with and developing for real quantum computers","author":"Wille","year":"2019"}],"container-title":["PeerJ Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/peerj.com\/articles\/cs-2210.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-2210.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-2210.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-2210.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T07:07:21Z","timestamp":1722841641000},"score":1,"resource":{"primary":{"URL":"https:\/\/peerj.com\/articles\/cs-2210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,5]]},"references-count":41,"alternative-id":["10.7717\/peerj-cs.2210"],"URL":"https:\/\/doi.org\/10.7717\/peerj-cs.2210","archive":["CLOCKSS","LOCKSS","Portico"],"relation":{},"ISSN":["2376-5992"],"issn-type":[{"value":"2376-5992","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,5]]},"article-number":"e2210"}}