Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States

Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States | 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 Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States Minglong Qin, Penghui Yao This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4802933/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 13 Aug, 2025 Read the published version in Algorithmica → Version 1 posted 10 You are reading this latest preprint version Abstract This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. Fully quantum nonlocal games are a generalization of nonlocal games, where both questions and answers are quantum and the referee performs a binary POVM measurement to decide whether they win the game after receiving the quantum answers from the players. The quantum value of a fully quantum nonlocal game is the supremum of the probability that they win the game, where the supremum is taken over all the possible entangled states shared between the players and all the valid quantum operations performed by the players. The seminal work $\mathrm{MIP}^*=\mathrm{RE}$~\cite{JNVWY'20,JNVWYuen'20} implies that it is undecidable to approximate the quantum value of a fully nonlocal game. This still holds even if the players are only allowed to share (arbitrarily many copies of) maximally entangled states. This paper investigates the case that the shared maximally entangled states are noisy. We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value. This implies that it is decidable to approximate the quantum values of these games. Hence, the hardness of approximating the quantum value of a fully quantum nonlocal game is not robust against the noise in the shared states. This paper is built on the framework for the decidability of non-interactive simulations of joint distributions~\cite{7782969,doi:10.1137/1.9781611975031.174,Ghazi:2018:DRP:3235586.3235614} and generalizes the analogous result for nonlocal games in~\cite{qin2021nonlocal}. We extend the theory of Fourier analysis to the space of super-operators and prove several key results including an invariance principle and a dimension reduction for super-operators. These results are interesting in their own right and are believed to have further applications. Nonlocal games Fourier analysis invariance principle dimension reduction Full Text Additional Declarations No competing interests reported. Supplementary Files reviewofICALP.docx Cite Share Download PDF Status: Published Journal Publication published 13 Aug, 2025 Read the published version in Algorithmica → Version 1 posted Editorial decision: Revision requested 22 May, 2025 Reviews received at journal 14 May, 2025 Reviews received at journal 12 May, 2025 Reviewers agreed at journal 02 Apr, 2025 Reviewers agreed at journal 30 Mar, 2025 Reviewers agreed at journal 30 Nov, 2024 Reviewers invited by journal 28 Nov, 2024 Editor assigned by journal 29 Jul, 2024 Submission checks completed at journal 26 Jul, 2024 First submitted to journal 25 Jul, 2024 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-4802933","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":336898144,"identity":"46a2cf72-ddf1-4885-9919-de21e4e3a24c","order_by":0,"name":"Minglong Qin","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAtElEQVRIiWNgGAWjYDACdgaGAwwVNkAWY+MB4rQwg7ScSQNpaSBeCwNjy2Ewmzgtus3MGw8XNpy3W9t+GGhLjU00QS1mh9kKDs/ccTt525lEoJZjabkNhLXwGBzmPXM72ewAUAtjw2FitbSdSzY7/5A0LQfszG4QbwvQLzxnkhPMbgBtSSDKL8ebN3/mqbCzNzuf/vDBhxobwlqAwABEJIJVJhChHK7FnkjFo2AUjIJRMBIBALrfSfzV2PlQAAAAAElFTkSuQmCC","orcid":"","institution":"Nanjing University","correspondingAuthor":true,"prefix":"","firstName":"Minglong","middleName":"","lastName":"Qin","suffix":""},{"id":336898145,"identity":"842ce7df-131a-4537-9c5a-5834a1694d9e","order_by":1,"name":"Penghui Yao","email":"","orcid":"","institution":"Nanjing University","correspondingAuthor":false,"prefix":"","firstName":"Penghui","middleName":"","lastName":"Yao","suffix":""}],"badges":[],"createdAt":"2024-07-25 15:29:24","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4802933/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4802933/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s00453-025-01339-3","type":"published","date":"2025-08-13T15:57:41+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":89311054,"identity":"cd0390b8-9749-4f75-8450-010289492039","added_by":"auto","created_at":"2025-08-18 16:10:15","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":715082,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4802933/v1_covered_45001092-9c2a-497a-993f-15d8c82e3cfb.pdf"},{"id":63013356,"identity":"55e0ee49-50a0-49b3-8111-cf4572e7a6e7","added_by":"auto","created_at":"2024-08-22 06:12:54","extension":"docx","order_by":0,"title":"","display":"","copyAsset":false,"role":"supplement","size":20700,"visible":true,"origin":"","legend":"","description":"","filename":"reviewofICALP.docx","url":"https://assets-eu.researchsquare.com/files/rs-4802933/v1/e8bacf714dc33e50a40a992e.docx"}],"financialInterests":"No competing interests reported.","formattedTitle":"Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"algorithmica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"algo","sideBox":"Learn more about [Algorithmica](http://link.springer.com/journal/453)","snPcode":"453","submissionUrl":"https://submission.nature.com/new-submission/453/3","title":"Algorithmica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Nonlocal games, Fourier analysis, invariance principle, dimension reduction","lastPublishedDoi":"10.21203/rs.3.rs-4802933/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4802933/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. Fully quantum nonlocal games are a generalization of nonlocal games, where both questions and answers are quantum and the referee performs a binary POVM measurement to decide whether they win the game after receiving the quantum answers from the players. The quantum value of a fully quantum nonlocal game is the supremum of the probability that they win the game, where the supremum is taken over all the possible entangled states shared between the players and all the valid quantum operations performed by the players. The seminal work $\\mathrm{MIP}^*=\\mathrm{RE}$~\\cite{JNVWY'20,JNVWYuen'20} implies that it is undecidable to approximate the quantum value of a fully nonlocal game. This still holds even if the players are only allowed to share (arbitrarily many copies of) maximally entangled states. This paper investigates the case that the shared maximally entangled states are noisy. We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value. This implies that it is decidable to approximate the quantum values of these games. Hence, the hardness of approximating the quantum value of a fully quantum nonlocal game is not robust against the noise in the shared states.\n\nThis paper is built on the framework for the decidability of non-interactive simulations of joint distributions~\\cite{7782969,doi:10.1137/1.9781611975031.174,Ghazi:2018:DRP:3235586.3235614} and generalizes the analogous result for nonlocal games in~\\cite{qin2021nonlocal}. We extend the theory of Fourier analysis to the space of super-operators and prove several key results including an invariance principle and a dimension reduction for super-operators. These results are interesting in their own right and are believed to have further applications.","manuscriptTitle":"Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-08-22 06:12:49","doi":"10.21203/rs.3.rs-4802933/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-05-23T02:51:04+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-05-14T14:13:49+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-05-13T00:16:04+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"90985390947160280787893907580881987225","date":"2025-04-02T18:05:09+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"13934022347307973768216090358418596020","date":"2025-03-30T13:33:05+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"324255127892681120741636896559072511708","date":"2024-11-30T20:31:15+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-11-28T16:52:07+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-07-29T22:29:26+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-07-26T07:46:09+00:00","index":"","fulltext":""},{"type":"submitted","content":"Algorithmica","date":"2024-07-25T15:27:55+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"algorithmica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"algo","sideBox":"Learn more about [Algorithmica](http://link.springer.com/journal/453)","snPcode":"453","submissionUrl":"https://submission.nature.com/new-submission/453/3","title":"Algorithmica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"d364e4f9-6039-479f-b249-dd92e7908157","owner":[],"postedDate":"August 22nd, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2025-08-18T16:07:43+00:00","versionOfRecord":{"articleIdentity":"rs-4802933","link":"https://doi.org/10.1007/s00453-025-01339-3","journal":{"identity":"algorithmica","isVorOnly":false,"title":"Algorithmica"},"publishedOn":"2025-08-13 15:57:41","publishedOnDateReadable":"August 13th, 2025"},"versionCreatedAt":"2024-08-22 06:12:49","video":"","vorDoi":"10.1007/s00453-025-01339-3","vorDoiUrl":"https://doi.org/10.1007/s00453-025-01339-3","workflowStages":[]},"version":"v1","identity":"rs-4802933","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4802933","identity":"rs-4802933","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}