Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence

Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence | 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 Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence Toru Fujii, Koshi Komuro, Kaito Tomari This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6298629/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract NP problems are closely related to practical optimization problems but often face exponential increases in computation time as problem sizes grow, prompting numerous attempts to accelerate calculations. Quantum annealing has been explored as a promising approach to solve NP problems faster than classical computers. However, it requires expressing cost functions and constraints as an energy function in QUBO format. Parameter settings for QUBO coefficients are often empirical, especially in scheduling problems, where large values may be required, demanding experience and intuition. In this study, we analyzed QUBO generation formulas for three problems classified as coloring problems in Lucas's paper: the graph coloring problem, the clique vertex cover problem, and the integer-length job scheduling problem. We identified the necessity of independent parameters for complex problems. By analyzing QUBO states and eigenvalues from modified formulas, we derived relationships between formula characteristics and optimal QUBO parameter values, along with their calculation methods. Using the quantum annealing machine D-Wave, we validated the derived parameters. Additionally, we visualized the impact of parameter changes on states and eigenvalues using small spin problems. We also demonstrated the existence of independent Ising coefficients that enhance convergence to correct states, depending on optimal parameter changes for ground-state and non-ground-state problems. Quantum annealing Quadratic unconstrained binary optimization NP problems Ising formulation Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version 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-6298629","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":472310520,"identity":"41246b29-8e0c-4181-8626-86d7c5463d1b","order_by":0,"name":"Toru Fujii","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAxklEQVRIie3QPQrCMBiA4S8EkiU6x8krdCqCRa+SUIibixfI1E16FSe7FoJ16QEyduqsi3QSGxHc2nQTzDN8U978AQTBD9qW/UBPwATjEkTpkRA3kHYJEdOSHosAvBJ6bDnShs4pezRNneyBmstpMGHXmKPO9BebFZGw6gBMKTuYcEXcKS45c3EzUnMW+yasnZ4QLqxPwiq8knrnPjnmolYyG30LzZC963W6zE276KpE5tRUg8mbAEi/m4wu/9j4LgyCIPhDL1bBQASC7rXWAAAAAElFTkSuQmCC","orcid":"","institution":"Nikon (Japan)","correspondingAuthor":true,"prefix":"","firstName":"Toru","middleName":"","lastName":"Fujii","suffix":""},{"id":472310521,"identity":"c9d42275-acab-4233-8a2f-c176c295fbe6","order_by":1,"name":"Koshi Komuro","email":"","orcid":"","institution":"Nikon (Japan)","correspondingAuthor":false,"prefix":"","firstName":"Koshi","middleName":"","lastName":"Komuro","suffix":""},{"id":472310522,"identity":"9f053ddc-cc13-42be-87ce-b15f9ff7c865","order_by":2,"name":"Kaito Tomari","email":"","orcid":"","institution":"Nikon (Japan)","correspondingAuthor":false,"prefix":"","firstName":"Kaito","middleName":"","lastName":"Tomari","suffix":""}],"badges":[],"createdAt":"2025-03-24 23:23:04","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6298629/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6298629/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":89330500,"identity":"926d0f53-a1fa-4cc1-b694-06ae8c2b732c","added_by":"auto","created_at":"2025-08-18 22:46:25","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":3003003,"visible":true,"origin":"","legend":"","description":"","filename":"QuantumannealingQIPToruFujiiNikon.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6298629/v1_covered_34128f0f-a8b0-4107-9be2-9d75bced869f.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"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 annealing, Quadratic unconstrained binary optimization, NP problems, Ising formulation","lastPublishedDoi":"10.21203/rs.3.rs-6298629/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6298629/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eNP problems are closely related to practical optimization problems but often face exponential increases in computation time as problem sizes grow, prompting numerous attempts to accelerate calculations. Quantum annealing has been explored as a promising approach to solve NP problems faster than classical computers. However, it requires expressing cost functions and constraints as an energy function in QUBO format. Parameter settings for QUBO coefficients are often empirical, especially in scheduling problems, where large values may be required, demanding experience and intuition. In this study, we analyzed QUBO generation formulas for three problems classified as coloring problems in Lucas's paper: the graph coloring problem, the clique vertex cover problem, and the integer-length job scheduling problem. We identified the necessity of independent parameters for complex problems. By analyzing QUBO states and eigenvalues from modified formulas, we derived relationships between formula characteristics and optimal QUBO parameter values, along with their calculation methods. Using the quantum annealing machine D-Wave, we validated the derived parameters. Additionally, we visualized the impact of parameter changes on states and eigenvalues using small spin problems. We also demonstrated the existence of independent Ising coefficients that enhance convergence to correct states, depending on optimal parameter changes for ground-state and non-ground-state problems.\u003c/p\u003e","manuscriptTitle":"Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-06-18 12:53:36","doi":"10.21203/rs.3.rs-6298629/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":"26ffaa25-9dac-40b0-ac8e-44a518df592b","owner":[],"postedDate":"June 18th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-08-18T22:38:14+00:00","versionOfRecord":[],"versionCreatedAt":"2025-06-18 12:53:36","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-6298629","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6298629","identity":"rs-6298629","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}