{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:23:24Z","timestamp":1772119404893,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T00:00:00Z","timestamp":1755043200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T00:00:00Z","timestamp":1755043200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62332009, 12347104"],"award-info":[{"award-number":["62332009, 12347104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62332009, 12347104"],"award-info":[{"award-number":["62332009, 12347104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Innovation Program for Quantum Science and Technology","award":["2021ZD0302901"],"award-info":[{"award-number":["2021ZD0302901"]}]},{"name":"Innovation Program for Quantum Science and Technology","award":["2021ZD0302901"],"award-info":[{"award-number":["2021ZD0302901"]}]},{"name":"NSFC\/RGC Joint Research Scheme","award":["12461160276"],"award-info":[{"award-number":["12461160276"]}]},{"name":"NSFC\/RGC Joint Research Scheme","award":["12461160276"],"award-info":[{"award-number":["12461160276"]}]},{"DOI":"10.13039\/501100004608","name":"Natural Science Foundation of Jiangsu Province","doi-asserted-by":"publisher","award":["BK20243060"],"award-info":[{"award-number":["BK20243060"]}],"id":[{"id":"10.13039\/501100004608","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004608","name":"Natural Science Foundation of Jiangsu Province","doi-asserted-by":"publisher","award":["BK20243060"],"award-info":[{"award-number":["BK20243060"]}],"id":[{"id":"10.13039\/501100004608","id-type":"DOI","asserted-by":"publisher"}]},{"name":"the New Cornerstone Science Foundation"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00453-025-01339-3","type":"journal-article","created":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T04:32:54Z","timestamp":1755059574000},"page":"1732-1803","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States"],"prefix":"10.1007","volume":"87","author":[{"given":"Minglong","family":"Qin","sequence":"first","affiliation":[]},{"given":"Penghui","family":"Yao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,13]]},"reference":[{"key":"1339_CR1","unstructured":"Ji, Z., Natarajan, A., Vidick, T., Wright, J., Yuen, H.: [CDATA[\\text{MIP}^*=\\text{ RE }]]$$\\text{MIP}^*=\\text{ RE }$$. arXiv:2001.04383 (2020)"},{"key":"1339_CR2","unstructured":"Ji, Z., Natarajan, A., Vidick, T., Wright, J., Yuen, H.: Quantum soundness of the classical low individual degree test. arXiv:2009.12982 (2020)"},{"key":"1339_CR3","doi-asserted-by":"crossref","unstructured":"Ghazi, B., Kamath, P., Sudan, M.: Decidability of non-interactive simulation of joint distributions. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 545\u2013554. IEEE Computer Society, Los Alamitos, CA, USA (2016). https:\/\/doi.ieeecomputersociety.org\/10.1109\/FOCS.2016.65","DOI":"10.1109\/FOCS.2016.65"},{"key":"1339_CR4","doi-asserted-by":"crossref","unstructured":"De, A., Mossel, E., Neeman, J.: Non interactive simulation of correlated distributions is decidable. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201918, pp. 2728\u20132746. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2018). http:\/\/dl.acm.org\/citation.cfm?id=3174304.3175478","DOI":"10.1137\/1.9781611975031.174"},{"key":"1339_CR5","doi-asserted-by":"publisher","unstructured":"Ghazi, B., Kamath, P., Raghavendra, P.: Dimension reduction for polynomials over gaussian space and applications. In: Proceedings of the 33rd Computational Complexity Conference. CCC \u201918, pp. 28\u201312837. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2018.28","DOI":"10.4230\/LIPIcs.CCC.2018.28"},{"issue":"6","key":"1339_CR6","doi-asserted-by":"publisher","first-page":"1800","DOI":"10.1137\/20M134592X","volume":"50","author":"M Qin","year":"2021","unstructured":"Qin, M., Yao, P.: Nonlocal games with noisy maximally entangled states are decidable. SIAM J. Comput. 50(6), 1800\u20131891 (2021)","journal-title":"SIAM J. Comput."},{"key":"1339_CR7","doi-asserted-by":"publisher","unstructured":"Cleve, R., Hoyer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. In: Proceedings of the 19th IEEE Annual Conference on Computational Complexity. CCC \u201904, pp. 236\u2013249. IEEE Computer Society, Washington, DC, USA (2004). https:\/\/doi.org\/10.1109\/CCC.2004.9","DOI":"10.1109\/CCC.2004.9"},{"key":"1339_CR8","doi-asserted-by":"publisher","unstructured":"Kempe, J., Kobayashi, H., Matsumoto, K., Toner, B., Vidick, T.: Entangled games are hard to approximate. In: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science. FOCS \u201908, pp. 447\u2013456. IEEE Computer Society, Washington, DC, USA (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.8","DOI":"10.1109\/FOCS.2008.8"},{"issue":"7","key":"1339_CR9","doi-asserted-by":"publisher","first-page":"3207","DOI":"10.1137\/090772885","volume":"39","author":"J Kempe","year":"2010","unstructured":"Kempe, J., Regev, O., Toner, B.: Unique games with entangled provers are easy. SIAM J. Comput. 39(7), 3207\u20133229 (2010). https:\/\/doi.org\/10.1137\/090772885","journal-title":"SIAM J. Comput."},{"key":"1339_CR10","doi-asserted-by":"publisher","unstructured":"Ito, T., Vidick, T.: A multi-prover interactive proof for NEXP sound against entangled provers. In: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. FOCS \u201912, pp. 243\u2013252. IEEE Computer Society, Washington, DC, USA (2012). https:\/\/doi.org\/10.1109\/FOCS.2012.11","DOI":"10.1109\/FOCS.2012.11"},{"key":"1339_CR11","doi-asserted-by":"publisher","unstructured":"Ji, Z.: Classical verification of quantum proofs. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing. STOC \u201916, pp. 885\u2013898. ACM, New York, NY, USA (2016). https:\/\/doi.org\/10.1145\/2897518.2897634","DOI":"10.1145\/2897518.2897634"},{"key":"1339_CR12","doi-asserted-by":"crossref","unstructured":"Natarajan, A., Wright, J.: NEEXP is contained in MIP. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 510\u2013518. IEEE Computer Society, Los Alamitos, CA, USA (2019). https:\/\/doi.ieeecomputersociety.org\/10.1109\/FOCS.2019.00039","DOI":"10.1109\/FOCS.2019.00039"},{"key":"1339_CR13","doi-asserted-by":"crossref","unstructured":"Fitzsimons, J., Ji, Z., Vidick, T., Yuen, H.: Quantum proof systems for iterated exponential time, and beyond. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC 2019. ACM, New York, NY, USA (2019)","DOI":"10.1145\/3313276.3316343"},{"key":"1339_CR14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.108.200401","volume":"108","author":"F Buscemi","year":"2012","unstructured":"Buscemi, F.: All entangled quantum states are nonlocal. Phys. Rev. Lett. 108, 200401 (2012). https:\/\/doi.org\/10.1103\/PhysRevLett.108.200401","journal-title":"Phys. Rev. Lett."},{"key":"1339_CR15","unstructured":"Leung, D., Toner, B., Watrous, J.: Coherent state exchange in multi-prover quantum interactive proof systems. Chicago Journal of Theoretical Computer Science 2013(11) (2013)"},{"key":"1339_CR16","doi-asserted-by":"publisher","DOI":"10.1145\/2799560","author":"O Regev","year":"2015","unstructured":"Regev, O., Vidick, T.: Quantum XOR games. ACM Trans. Comput. Theory (2015). https:\/\/doi.org\/10.1145\/2799560","journal-title":"ACM Trans. Comput. Theory"},{"key":"1339_CR17","unstructured":"Chung, K.-M., Wu, X., Yuen, H.: Parallel Repetition for Entangled k-player Games via Fast Quantum Search. In: Zuckerman, D. (ed.) 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 33, pp. 512\u2013536. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2015). http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2015\/5072"},{"key":"1339_CR18","doi-asserted-by":"publisher","unstructured":"Fitzsimons, J., Vidick, T.: A multiprover interactive proof system for the local hamiltonian problem. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science. ITCS \u201915, pp. 103\u2013112. Association for Computing Machinery, New York, NY, USA (2015). https:\/\/doi.org\/10.1145\/2688073.2688094","DOI":"10.1145\/2688073.2688094"},{"key":"1339_CR19","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.032306","volume":"87","author":"EG Cavalcanti","year":"2013","unstructured":"Cavalcanti, E.G., Hall, M.J.W., Wiseman, H.M.: Entanglement verification and steering when alice and bob cannot be trusted. Phys. Rev. A 87, 032306 (2013). https:\/\/doi.org\/10.1103\/PhysRevA.87.032306","journal-title":"Phys. Rev. A"},{"key":"1339_CR20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.110.060405","volume":"110","author":"C Branciard","year":"2013","unstructured":"Branciard, C., Rosset, D., Liang, Y.-C., Gisin, N.: Measurement-device-independent entanglement witnesses for all entangled quantum states. Phys. Rev. Lett. 110, 060405 (2013). https:\/\/doi.org\/10.1103\/PhysRevLett.110.060405","journal-title":"Phys. Rev. Lett."},{"issue":"2189","key":"1339_CR21","doi-asserted-by":"publisher","first-page":"20160003","DOI":"10.1098\/rspa.2016.0003","volume":"472","author":"N Johnston","year":"2016","unstructured":"Johnston, N., Mittal, R., Russo, V., Watrous, J.: Extended non-local games and monogamy-of-entanglement games. Proc. Soc. A: Math. Phys. Eng. Sci. 472(2189), 20160003 (2016). https:\/\/doi.org\/10.1098\/rspa.2016.0003","journal-title":"Proc. Soc. A: Math. Phys. Eng. Sci."},{"issue":"6","key":"1339_CR22","doi-asserted-by":"publisher","first-page":"3419","DOI":"10.1109\/TIT.2016.2553672","volume":"62","author":"S Kamath","year":"2016","unstructured":"Kamath, S., Anantharam, V.: On non-interactive simulation of joint distributions. IEEE Trans. Inf. Theory 62(6), 3419\u20133435 (2016). https:\/\/doi.org\/10.1109\/TIT.2016.2553672","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1339_CR23","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s00220-014-2105-y","volume":"332","author":"P Delgosha","year":"2014","unstructured":"Delgosha, P., Beigi, S.: Impossibility of local state transformation via hypercontractivity. Commun. Math. Phys. 332(1), 449\u2013476 (2014). https:\/\/doi.org\/10.1007\/s00220-014-2105-y","journal-title":"Commun. Math. Phys."},{"key":"1339_CR24","doi-asserted-by":"publisher","first-page":"295","DOI":"10.4007\/annals.2010.171.295","volume":"171","author":"E Mossel","year":"2010","unstructured":"Mossel, E., O\u2019Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences: invariance and optimality. Ann. Math. 171, 295\u2013341 (2010)","journal-title":"Ann. Math."},{"key":"1339_CR25","doi-asserted-by":"crossref","unstructured":"Harrow, A.W., Montanaro, A., Short, A.J.: Limitations on quantum dimensionality reduction. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Automata, Languages and Programming, pp. 86\u201397. Springer, Berlin, Heidelberg (2011)","DOI":"10.1007\/978-3-642-22006-7_8"},{"issue":"5","key":"1339_CR26","doi-asserted-by":"publisher","first-page":"2867","DOI":"10.1109\/TIT.2016.2538278","volume":"62","author":"CJ Stark","year":"2016","unstructured":"Stark, C.J., Harrow, A.W.: Compressibility of positive semidefinite factorizations and quantum models. IEEE Trans. Inf. Theory 62(5), 2867\u20132880 (2016). https:\/\/doi.org\/10.1109\/TIT.2016.2538278","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1339_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/9781316848142","volume-title":"Theory of Quantum Information","author":"J Watrous","year":"2018","unstructured":"Watrous, J.: Theory of Quantum Information. Cambridge University Press, Cambridge, UK (2018)"},{"issue":"8","key":"1339_CR28","doi-asserted-by":"publisher","DOI":"10.1063\/1.4818985","volume":"54","author":"S Beigi","year":"2013","unstructured":"Beigi, S.: A new quantum data processing inequality. J. Math. Phys. 54(8), 082202 (2013). https:\/\/doi.org\/10.1063\/1.4818985","journal-title":"J. Math. Phys."},{"key":"1339_CR29","doi-asserted-by":"publisher","first-page":"2046","DOI":"10.1103\/PhysRevA.53.2046","volume":"53","author":"CH Bennett","year":"1996","unstructured":"Bennett, C.H., Bernstein, H.J., Popescu, S., Schumacher, B.: Concentrating partial entanglement by local operations. Phys. Rev. A 53, 2046\u20132052 (1996). https:\/\/doi.org\/10.1103\/PhysRevA.53.2046","journal-title":"Phys. Rev. A"},{"issue":"2","key":"1339_CR30","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1109\/COMST.2017.2786748","volume":"20","author":"L Gyongyosi","year":"2018","unstructured":"Gyongyosi, L., Imre, S., Nguyen, H.V.: A survey on quantum channel capacities. IEEE Commun. Surv. Tutorials 20(2), 1149\u20131205 (2018). https:\/\/doi.org\/10.1109\/COMST.2017.2786748","journal-title":"IEEE Commun. Surv. Tutorials"},{"key":"1339_CR31","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1103\/RevModPhys.81.865","volume":"81","author":"R Horodecki","year":"2009","unstructured":"Horodecki, R., Horodecki, P., Horodecki, M., Horodecki, K.: Quantum entanglement. Rev. Mod. Phys. 81, 865\u2013942 (2009). https:\/\/doi.org\/10.1103\/RevModPhys.81.865","journal-title":"Rev. Mod. Phys."},{"key":"1339_CR32","doi-asserted-by":"publisher","unstructured":"Touchette, D.: Quantum information complexity. In: Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing. STOC \u201915, pp. 317\u2013326. ACM, New York, NY, USA (2015). https:\/\/doi.org\/10.1145\/2746539.2746613","DOI":"10.1145\/2746539.2746613"},{"issue":"7","key":"1339_CR33","doi-asserted-by":"publisher","first-page":"4689","DOI":"10.1109\/TIT.2017.2776907","volume":"64","author":"F Leditzky","year":"2018","unstructured":"Leditzky, F., Datta, N., Smith, G.: Useful states and entanglement distillation. IEEE Trans. Inf. Theory 64(7), 4689\u20134708 (2018). https:\/\/doi.org\/10.1109\/TIT.2017.2776907","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1339_CR34","unstructured":"Montanaro, A., Osborne, T.J.: Quantum boolean functions. Chicago Journal of Theoretical Computer Science 2010(1) (2010)"},{"key":"1339_CR35","unstructured":"Rou\u00e9, C., Wirth, M., Zhang, H.: Quantum talagrand, kkl and friedgut\u2019s theorems and the learnability of quantum boolean functions. arXiv preprint arXiv:2209.07279 (2209.07279)"},{"key":"1339_CR36","doi-asserted-by":"publisher","unstructured":"Ben-Aroya, A., Regev, O., Wolf, R.: A hypercontractive inequality for matrix-valued functions with applications to quantum computing and ldcs. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 477\u2013486 (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.45","DOI":"10.1109\/FOCS.2008.45"},{"key":"1339_CR37","unstructured":"Bu, K., Garcia, R.J., Jaffe, A., Koh, D.E., Li, L.: Complexity of quantum circuits via sensitivity, magic, and coherence. arXiv preprint arXiv:2204.12051 (2022)"},{"key":"1339_CR38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.84.052328","volume":"84","author":"G Wang","year":"2011","unstructured":"Wang, G.: Property testing of unitary operators. Phys. Rev. A 84, 052328 (2011). https:\/\/doi.org\/10.1103\/PhysRevA.84.052328","journal-title":"Phys. Rev. A"},{"key":"1339_CR39","unstructured":"Chen, T., Nadimpalli, S., Yuen, H.: Testing and learning quantum juntas nearly optimally. arXiv:2207.05898 (2207.05898)"},{"key":"1339_CR40","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, UK (2000)"},{"key":"1339_CR41","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2013","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge, UK (2013)"},{"key":"1339_CR42","unstructured":"Bertsekas, D.P.: Convex Optimization Algorithms. Athena Scientific Belmont, ??? (2015)"},{"key":"1339_CR43","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.laa.2018.10.017","volume":"576","author":"P Zhang","year":"2019","unstructured":"Zhang, P.: On some inequalities related to positive block matrices. Linear Algebra Appl. 576, 258\u2013267 (2019)","journal-title":"Linear Algebra Appl."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01339-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01339-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01339-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T19:09:09Z","timestamp":1759777749000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01339-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,13]]},"references-count":43,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["1339"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01339-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-4802933\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,13]]},"assertion":[{"value":"25 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}