Scaling advantage in approximate optimization with quantum annealing

Scaling advantage in approximate optimization with quantum annealing | 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 Physical Sciences - Article Scaling advantage in approximate optimization with quantum annealing Daniel Lidar, Humberto Munoz Bauza This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3860892/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 Quantum annealing is a heuristic optimization algorithm that exploits quantum evolution to approximately find lowest energy states [1, 2]. Quantum annealers have scaled up in recent years to tackle increasingly larger and more highly connected discrete optimization and quantum simulation problems [3–7]. Nevertheless, despite numerous attempts, a computational quantum advantage in exact optimization using quantum annealing hardware has so far remained elusive [8– 16]. Here, we present evidence for a quantum annealing scaling advantage in approximate optimization. The advantage is relative to the top classical heuristic algorithm: parallel tempering with isoenergetic cluster moves (PT-ICM) [17]. The setting is a family of 2D spin-glass problems with high-precision spin-spin interactions. To achieve this advantage, we implement quantum annealing correction (QAC) [18]: an embedding of a bit-flip error-correcting code with energy penalties that leverages the properties of the D-Wave Advantage quantum annealer to yield over 1,300 error-suppressed logical qubits on a degree-5 interaction graph. We generate random spin-glass instances on this graph and benchmark their time-to-epsilon, a generalization of the time-to-solution metric [8] for low-energy states. We demonstrate that with QAC, quantum annealing exhibits a scaling advantage over PT-ICM at sampling low energy states with an optimality gap [19] of at least 1.0%. This amounts to the first demonstration of an algorithmic quantum speedup in approximate optimization. Physical sciences/Physics/Quantum physics/Quantum information Physical sciences/Physics/Information theory and computation Full Text Additional Declarations There is NO Competing Interest. 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-3860892","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Physical Sciences - Article","associatedPublications":[],"authors":[{"id":266890345,"identity":"117b09d9-56a7-4db0-a960-6a91b18178d5","order_by":0,"name":"Daniel Lidar","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAoklEQVRIiWNgGAWjYBACPmYGAwaGCghHgigtbGAtZ0jSwgDUwthGkhZ25o2fK+cdtudvYD54m4c4h7EVS57ddjhxxgG2ZGsitfAYSDZuO5xgwMBjJk2sFuOfjXMO2xsw8H8jWouZZGPDYcYNDDxsxGphK7NsOJaeOOMwm7HlHGK08PMf3nyzocbanr+9+eGNN8RoQQBm0pSPglEwCkbBKMAHAISoJg2KskQVAAAAAElFTkSuQmCC","orcid":"https://orcid.org/0000-0002-1671-1515","institution":"University of Southern California","correspondingAuthor":true,"prefix":"","firstName":"Daniel","middleName":"","lastName":"Lidar","suffix":""},{"id":266890346,"identity":"e840a491-0a8d-47f7-ae43-e2da615634ee","order_by":1,"name":"Humberto Munoz Bauza","email":"","orcid":"","institution":"University of Southern California","correspondingAuthor":false,"prefix":"","firstName":"Humberto","middleName":"Munoz","lastName":"Bauza","suffix":""}],"badges":[],"createdAt":"2024-01-13 18:05:07","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-3860892/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-3860892/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":50324106,"identity":"af4a0358-4d55-4a55-a4af-0ccceb2bff2b","added_by":"auto","created_at":"2024-01-29 18:38:23","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":886019,"visible":true,"origin":"","legend":"Article File","description":"","filename":"MunozLidarpqac.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3860892/v1_covered_add7fa5b-ff29-43fc-9165-964ac10e4f98.pdf"}],"financialInterests":"There is \u003cb\u003eNO\u003c/b\u003e Competing Interest.","formattedTitle":"Scaling advantage in approximate optimization with quantum annealing","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":"","lastPublishedDoi":"10.21203/rs.3.rs-3860892/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3860892/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Quantum annealing is a heuristic optimization algorithm that exploits quantum evolution to approximately find lowest energy states [1, 2]. Quantum annealers have scaled up in recent years to tackle increasingly larger and more highly connected discrete optimization and quantum simulation problems [3–7]. Nevertheless, despite numerous attempts, a computational quantum advantage in exact optimization using quantum annealing hardware has so far remained elusive [8– 16]. Here, we present evidence for a quantum annealing scaling advantage in approximate optimization. The advantage is relative to the top classical heuristic algorithm: parallel tempering with isoenergetic cluster moves (PT-ICM) [17]. The setting is a family of 2D spin-glass problems with high-precision spin-spin interactions. To achieve this advantage, we implement quantum annealing correction (QAC) [18]: an embedding of a bit-flip error-correcting code with energy penalties that leverages the properties of the D-Wave Advantage quantum annealer to yield over 1,300 error-suppressed logical qubits on a degree-5 interaction graph. We generate random spin-glass instances on this graph and benchmark their time-to-epsilon, a generalization of the time-to-solution metric [8] for low-energy states. We demonstrate that with QAC, quantum annealing exhibits a scaling advantage over PT-ICM at sampling low energy states with an optimality gap [19] of at least 1.0%. This amounts to the first demonstration of an algorithmic quantum speedup in approximate optimization.","manuscriptTitle":"Scaling advantage in approximate optimization with quantum annealing","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-01-16 02:10:44","doi":"10.21203/rs.3.rs-3860892/v1","editorialEvents":[],"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":"85756585-b6bf-4ae4-bfc6-4fd874d5d344","owner":[],"postedDate":"January 16th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[{"id":28124529,"name":"Physical sciences/Physics/Quantum physics/Quantum information"},{"id":28124530,"name":"Physical sciences/Physics/Information theory and computation"}],"tags":[],"updatedAt":"2024-01-29T20:05:22+00:00","versionOfRecord":[],"versionCreatedAt":"2024-01-16 02:10:44","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-3860892","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3860892","identity":"rs-3860892","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}