A Quantum Global Optimization Algorithm: Application to the Knapsack Problem

A Quantum Global Optimization Algorithm: Application to the Knapsack Problem | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article A Quantum Global Optimization Algorithm: Application to the Knapsack Problem Mohamed Yassine Cherif, Wided Lejouad Chaari, Olfa Belkahla Driss This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8555103/v2 This work is licensed under a CC BY 4.0 License Status: Posted Version 2 posted You are reading this latest preprint version Show more versions Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm to solve combinatorial optimization problems intended to provide an improved performance. The proposed algorithm aims to amplify the probability of selecting the global optimum of the objective function defining the addressed problem using a specific variant of Grover’s search based on simultaneously exploring all comparison cases of possible solutions to recognize the global optimum. The paper also includes the study of precision and runtime of the presented concept and introduces a version of the proposed algorithm addressing the knapsack problem, along with its execution results and a comparison with other competing algorithms Quantum Computing Grover’s Algorithm Combinatorial Optimization NP-Complete Problems Full Text Additional Declarations The authors declare no competing interests. Cite Share Download PDF Status: Posted Version 2 posted You are reading this latest preprint version Show more versions Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8555103","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":572962466,"identity":"488272a7-5a33-4651-8bfe-e651591afddc","order_by":0,"name":"Mohamed Yassine Cherif","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABSElEQVRIie2RP0vDQBiHXwnEJaVrNEg/gXCl0CIpit+kR6FdLiK4ZAhyIKRLa9cO0n6FuBTcLhwky2nXQActgrN/oIsQzYm1NFZxdLhneHn53T333nEACsW/xJBF+2iZLEg2rvsV/lURYqmYvymwUODaXwZ5ZbfTC58T18b9fjzjxy6Uapu9GQuH9aNSB/TtxIPT2qpSFTdNi4g2HiQE8YGA8lU3Riwct04QB90iEZh7dFXJdlqOzzFNDOAFHxooaQF/GnMcaMW5RXQwEcsrlVcn5Xg0ie94Ic2U2wdg4cUbHp3JKek6pWo5NDuTNRAvUDlFzxTKMJUXc/zvihBVm0TtyqV8ixGZ5UC0gLGoiQMOmu2cm1tBTom7lSnx7J3hJL5/Mbx6CcWR9si8fTzqs40pmdeLuSkLDun6T1iXfHLw04JCoVAo4B1S4YDA7QCw4AAAAABJRU5ErkJggg==","orcid":"https://orcid.org/0009-0008-0233-8378","institution":"Research Unit in Artificial Intelligence LARIA UR22ES01, National School of Computer Sciences ENSI, University of Manouba, Manouba, Tunisia.","correspondingAuthor":true,"prefix":"","firstName":"Mohamed","middleName":"Yassine","lastName":"Cherif","suffix":""},{"id":572962467,"identity":"775c7ea2-7d52-4c0e-99ab-8bd5fe842c8f","order_by":1,"name":"Wided Lejouad Chaari","email":"","orcid":"https://orcid.org/0000-0002-0721-1930","institution":"Department of Computer Sciences, Faculty of Computer and Information Sciences, Princess Nourah University, Riyadh, KSA.","correspondingAuthor":false,"prefix":"","firstName":"Wided","middleName":"Lejouad","lastName":"Chaari","suffix":""},{"id":572962468,"identity":"e10f87b4-9d4b-4dcb-850b-b7c0b509a9d2","order_by":2,"name":"Olfa Belkahla Driss","email":"","orcid":"https://orcid.org/0000-0003-3077-6240","institution":"Higher School of Commerce of Tunis ESCT, University of Manouba, Manouba, Tunisia.","correspondingAuthor":false,"prefix":"","firstName":"Olfa","middleName":"Belkahla","lastName":"Driss","suffix":""}],"badges":[],"createdAt":"2026-01-08 21:36:10","currentVersionCode":2,"declarations":{"humanSubjects":false,"vertebrateSubjects":false,"conflictsOfInterestStatement":false,"humanSubjectEthicalGuidelines":false,"humanSubjectConsent":false,"humanSubjectClinicalTrial":false,"humanSubjectCaseReport":false,"vertebrateSubjectEthicalGuidelines":false},"doi":"10.21203/rs.3.rs-8555103/v2","doiUrl":"https://doi.org/10.21203/rs.3.rs-8555103/v2","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":105564661,"identity":"a5ce24cf-08b8-41e1-906b-3dce854d9f97","added_by":"auto","created_at":"2026-03-27 12:50:24","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":8210229,"visible":true,"origin":"","legend":"","description":"","filename":"Manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8555103/v2_covered_57101420-8d3d-4fd8-88b8-d19b86700d9f.pdf"}],"financialInterests":"The authors declare no competing interests.","formattedTitle":"A Quantum Global Optimization Algorithm: Application to the Knapsack Problem","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Quantum Computing, Grover’s Algorithm, Combinatorial Optimization, NP-Complete Problems","lastPublishedDoi":"10.21203/rs.3.rs-8555103/v2","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8555103/v2","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eSolving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm to solve combinatorial optimization problems intended to provide an improved performance. The proposed algorithm aims to amplify the probability of selecting the global optimum of the objective function defining the addressed problem using a specific variant of Grover’s search based on simultaneously exploring all comparison cases of possible solutions to recognize the global optimum. The paper also includes the study of precision and runtime of the presented concept and introduces a version of the proposed algorithm addressing the knapsack problem, along with its execution results and a comparison with other competing algorithms\u003c/p\u003e","manuscriptTitle":"A Quantum Global Optimization Algorithm: Application to the Knapsack Problem","msid":"","msnumber":"","nonDraftVersions":[{"code":2,"date":"2026-03-23 19:50:02","doi":"10.21203/rs.3.rs-8555103/v2","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}},{"code":1,"date":"2026-01-12 04:55:43","doi":"10.21203/rs.3.rs-8555103/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"395b3aa3-1fc1-4262-b51b-729740c476f5","owner":[],"postedDate":"March 23rd, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2026-01-12T04:55:43+00:00","versionOfRecord":[],"versionCreatedAt":"2026-03-23 19:50:02","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v2","identity":"rs-8555103","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8555103","identity":"rs-8555103","version":["v2"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}