Application of Quantum Approximate Optimization Algorithm in Three- Dimensional Matching Problem

Application of Quantum Approximate Optimization Algorithm in Three- Dimensional Matching 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 Application of Quantum Approximate Optimization Algorithm in Three- Dimensional Matching Problem Jinyuan Dong, yao zhao, Zhiqiang Li, Tao Wang, Guangsheng Peng, and 1 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6477874/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 The three-dimensional matching problem is a classic NP-complete problem in combinatorial optimization, with wide applications in resource allocation, task scheduling, and many other practical scenarios. Traditional algorithms for solving the three-dimensional matching problem face the challenge of high time complexity, making it difficult to solve large-scale problems within a reasonable time frame. To improve the solution efficiency, a quantum circuit solution based on the Quantum Approximate Optimization Algorithm (QAOA) is proposed. By constructing a mathematical model of the three-dimensional matching problem, the corresponding Hamiltonian expression is derived. A QAOA-based quantum circuit is designed and the parameters of the parameterized quantum gates are optimized using the classical optimization algorithm COBYLA. Simulation experiments are performed using IBM's quantum development framework Qiskit. The experimental results show that the solution to the three-dimensional matching problem can be obtained with 84% probability in polynomial time, verifying the feasibility and effectiveness of solving the three-dimensional matching problem based on the Quantum Approximate Optimization Algorithm. Quantum Approximate Optimization Algorithm Quantum Circuit Hamiltonian Three-Dimensional Matching 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-6477874","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":460735670,"identity":"86ccab25-5b1a-4928-bbf5-695e23ca6e2c","order_by":0,"name":"Jinyuan Dong","email":"","orcid":"","institution":"Yangzhou University","correspondingAuthor":false,"prefix":"","firstName":"Jinyuan","middleName":"","lastName":"Dong","suffix":""},{"id":460735671,"identity":"cd56e923-f436-40fb-9f48-712091e64933","order_by":1,"name":"yao zhao","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA2UlEQVRIiWNgGAWjYDACCQglB6HYSNBiTLqWxAaitcjPbn74mKfGJn3D+TMGDB/KDjPwz27Ar4VxzjFjY55jabkbDpwxYJxx7jCDxJ0D+LUwSySYSfOwHc7dcLDHgJm37TCDgUQCfi1sEunfpHn+HU43OMxjwPyXGC08Ejlm0kDDEwyOAbUwEqNFQiKn2HBuX5rhzDNsBQd7zqXzSNwgoEV+RvrGB2++2cjznT+88cGPMms5/hkEtIAAEw+QUDjAwHAA5FLC6oGA8QfIugai1I6CUTAKRsFIBABZNkAbchRTgwAAAABJRU5ErkJggg==","orcid":"","institution":"Yangzhou University","correspondingAuthor":true,"prefix":"","firstName":"yao","middleName":"","lastName":"zhao","suffix":""},{"id":460735672,"identity":"3fc9e5b9-89aa-4daf-a249-0740dde6cea6","order_by":2,"name":"Zhiqiang Li","email":"","orcid":"","institution":"Yangzhou University","correspondingAuthor":false,"prefix":"","firstName":"Zhiqiang","middleName":"","lastName":"Li","suffix":""},{"id":460735673,"identity":"f9b95d6d-414b-4739-b09b-a2719ce111f8","order_by":3,"name":"Tao Wang","email":"","orcid":"","institution":"Yangzhou University","correspondingAuthor":false,"prefix":"","firstName":"Tao","middleName":"","lastName":"Wang","suffix":""},{"id":460735674,"identity":"a602e0bc-ba2b-4f4c-ae30-21a887ba2401","order_by":4,"name":"Guangsheng Peng","email":"","orcid":"","institution":"Yangzhou University","correspondingAuthor":false,"prefix":"","firstName":"Guangsheng","middleName":"","lastName":"Peng","suffix":""},{"id":460735675,"identity":"b4ac7823-43fb-42ca-95fb-50b879797ff2","order_by":5,"name":"Xiaoxiao Wang","email":"","orcid":"","institution":"Yangzhou University","correspondingAuthor":false,"prefix":"","firstName":"Xiaoxiao","middleName":"","lastName":"Wang","suffix":""}],"badges":[],"createdAt":"2025-04-18 09:23:24","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6477874/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6477874/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":87691347,"identity":"942c5078-ff08-4da7-b9f3-8eeab9219eff","added_by":"auto","created_at":"2025-07-28 04:31:52","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":479276,"visible":true,"origin":"","legend":"","description":"","filename":"ApplicationofQuantumApproximateOptimizationAlgorithminThreeDimensionalMatchingProblem.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6477874/v1_covered_64cc8d08-d0f5-43a3-885b-71d3240a9889.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Application of Quantum Approximate Optimization Algorithm in Three- Dimensional Matching Problem","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 Approximate Optimization Algorithm, Quantum Circuit, Hamiltonian, Three-Dimensional Matching","lastPublishedDoi":"10.21203/rs.3.rs-6477874/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6477874/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eThe three-dimensional matching problem is a classic NP-complete problem in combinatorial optimization, with wide applications in resource allocation, task scheduling, and many other practical scenarios. Traditional algorithms for solving the three-dimensional matching problem face the challenge of high time complexity, making it difficult to solve large-scale problems within a reasonable time frame. To improve the solution efficiency, a quantum circuit solution based on the Quantum Approximate Optimization Algorithm (QAOA) is proposed. By constructing a mathematical model of the three-dimensional matching problem, the corresponding Hamiltonian expression is derived. A QAOA-based quantum circuit is designed and the parameters of the parameterized quantum gates are optimized using the classical optimization algorithm COBYLA. Simulation experiments are performed using IBM's quantum development framework Qiskit. The experimental results show that the solution to the three-dimensional matching problem can be obtained with 84% probability in polynomial time, verifying the feasibility and effectiveness of solving the three-dimensional matching problem based on the Quantum Approximate Optimization Algorithm.\u003c/p\u003e","manuscriptTitle":"Application of Quantum Approximate Optimization Algorithm in Three- Dimensional Matching Problem","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-05-26 08:12:11","doi":"10.21203/rs.3.rs-6477874/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":"173f1aff-60e8-4cd2-a874-6f2f05151733","owner":[],"postedDate":"May 26th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-07-28T04:23:40+00:00","versionOfRecord":[],"versionCreatedAt":"2025-05-26 08:12:11","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-6477874","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6477874","identity":"rs-6477874","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}