Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs

Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs | 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 Article Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs Tongyang Li, Yuexin Su, Ziyi Yang, Shengyu Zhang This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-5986621/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 Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem. Its guarantee on cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs being outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. This formula also extends to the quantum MaxCut problem. On the other hand, we conduct numerical experiments to compare between best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms the best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases that ma-QAOA exhibits superiority over best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs such as tiling grid graphs, where QAOA also demonstrates an advantage. Physical sciences/Physics/Quantum physics/Quantum information Physical sciences/Mathematics and computing/Computer science 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-5986621","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Article","associatedPublications":[],"authors":[{"id":413524011,"identity":"64e7d77d-8baa-4465-88c8-a3067df9ee5d","order_by":0,"name":"Tongyang Li","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA60lEQVRIiWNgGAWjYDADPmbmA4wNINYBAip5YAw2ZrYEUrUw8BgQp8Wevffwa56aO3Zt7DzfHs5sY5Dju5HA+LkAny0859KseY49S25j5t1uuLGNwVjyRgKz9Ax8WiRyzIx52A4nszHzbpN82MaQuOFGAhszD0Et/0BaeJ6BtNQTo8X4MW/bYTugMjZJoMMSDAhqOXPGjHFu32GgMjZzwxnnJAxnnnnYLI1PC3t7j/GHN98O2/PzH372sKfMRp7vePLBz/i0AAGbFFBBYgMoahgYJIAYEj34APPHH8D4YYBoGQWjYBSMglGACQBqNEcjrhimSwAAAABJRU5ErkJggg==","orcid":"","institution":"Peking University","correspondingAuthor":true,"prefix":"","firstName":"Tongyang","middleName":"","lastName":"Li","suffix":""},{"id":413524013,"identity":"af8de826-904e-49eb-bcf2-56b6036e0cfa","order_by":1,"name":"Yuexin Su","email":"","orcid":"","institution":"Peking University","correspondingAuthor":false,"prefix":"","firstName":"Yuexin","middleName":"","lastName":"Su","suffix":""},{"id":413524015,"identity":"20adc922-d84a-4048-8abd-d02cb0a87672","order_by":2,"name":"Ziyi Yang","email":"","orcid":"","institution":"Peking University","correspondingAuthor":false,"prefix":"","firstName":"Ziyi","middleName":"","lastName":"Yang","suffix":""},{"id":413524016,"identity":"417a9630-4ee3-41e6-aa6e-7901e66fb326","order_by":3,"name":"Shengyu Zhang","email":"","orcid":"","institution":"Tencent Quantum Laboratory","correspondingAuthor":false,"prefix":"","firstName":"Shengyu","middleName":"","lastName":"Zhang","suffix":""}],"badges":[],"createdAt":"2025-02-08 09:08:30","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-5986621/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-5986621/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":76662730,"identity":"d555b1aa-d025-4d8e-a821-51afb92d8872","added_by":"auto","created_at":"2025-02-19 12:08:57","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":607507,"visible":true,"origin":"","legend":"","description":"","filename":"upload.pdf","url":"https://assets-eu.researchsquare.com/files/rs-5986621/v1_covered_d92b067c-4f00-463b-b134-9a69a3ed4cf5.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs","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":"","lastPublishedDoi":"10.21203/rs.3.rs-5986621/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-5986621/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem. Its guarantee on cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs being outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. This formula also extends to the quantum MaxCut problem. On the other hand, we conduct numerical experiments to compare between best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms the best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases that ma-QAOA exhibits superiority over best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs such as tiling grid graphs, where QAOA also demonstrates an advantage.","manuscriptTitle":"Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-02-12 10:05:59","doi":"10.21203/rs.3.rs-5986621/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":"0960a850-11fe-4343-af5f-3133cc324293","owner":[],"postedDate":"February 12th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[{"id":44091954,"name":"Physical sciences/Physics/Quantum physics/Quantum information"},{"id":44091955,"name":"Physical sciences/Mathematics and computing/Computer science"}],"tags":[],"updatedAt":"2025-02-19T12:08:44+00:00","versionOfRecord":[],"versionCreatedAt":"2025-02-12 10:05:59","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-5986621","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-5986621","identity":"rs-5986621","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}