{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:06:00Z","timestamp":1764781560949,"version":"3.46.0"},"reference-count":65,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T00:00:00Z","timestamp":1758067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T00:00:00Z","timestamp":1758067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"abstract":"Abstract<\/jats:title>\n \n The complexity class Quantum Statistical Zero-Knowledge captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, deciding whether\n \n \n $$\\textrm{T}(\\rho_0,\\rho_1)$$<\/jats:tex-math>\n \n \n T<\/mml:mtext>\n (<\/mml:mo>\n \n \u03c1<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \u03c1<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is at least\n \n \n $$\\alpha$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n or at most\n \n \n $$\\beta$$<\/jats:tex-math>\n \n \u03b2<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). \nHowever,\n \n \n $$\\textrm{QSDP}[\\alpha,\\beta]$$<\/jats:tex-math>\n \n \n QSDP<\/mml:mtext>\n [<\/mml:mo>\n \u03b1<\/mml:mi>\n ,<\/mml:mo>\n \u03b2<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is in only within the constant polarizing regime, where\n \n \n $$\\alpha \\, \\textrm{and} \\, \\beta$$<\/jats:tex-math>\n \n \n \u03b1<\/mml:mi>\n \n and<\/mml:mtext>\n \n \u03b2<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n are constants satisfying\n \n \n $$\\alpha^2 > \\beta$$<\/jats:tex-math>\n \n \n \n \u03b1<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n ><\/mml:mo>\n \u03b2<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n (rather than\n \n \n $$\\alpha > \\beta$$<\/jats:tex-math>\n \n \n \u03b1<\/mml:mi>\n ><\/mml:mo>\n \u03b2<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ), similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for SDP). \nRecently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the containment of SDP beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. \nOur work introduces\n proper<\/jats:italic>\n quantum analogs for these problems by defining quantum counterparts for triangular discrimination. We investigate whether the quantum analogs behave similarly to their classical counterparts and examine the limitations of existing approaches to polarization regarding quantum distances. These new -complete problems improve containments of QSDP beyond the polarizing regime and establish a simple -hardness for the quantum entropy difference problem (QEDP) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). \nFurthermore, we prove that QSDP with some exponentially small errors is in , while the same problem without error is in .\n <\/jats:p>","DOI":"10.1007\/s00037-025-00273-8","type":"journal-article","created":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T04:48:24Z","timestamp":1758084504000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantum state testing beyond the polarizing regime and quantum triangular discrimination"],"prefix":"10.1007","volume":"34","author":[{"given":"Yupan","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,17]]},"reference":[{"key":"273_CR1","doi-asserted-by":"crossref","unstructured":"Leonard M Adleman, Jonathan Demarrais & Ming-Deh A Huang (1997). Quantum computability. SIAM Journal on Computing 26(5), 1524\u20131540.","DOI":"10.1137\/S0097539795293639"},{"key":"273_CR2","unstructured":"Dorit Aharonov, Alex B Grilo & Yupan Liu (2020). StoqMA vs. MA: the power of error reduction. arXiv preprint arXiv:2010.02835."},{"key":"273_CR3","doi-asserted-by":"crossref","unstructured":"Guillaume Aubrun & Stanis\u0142aw J Szarek (2017). Alice and Bob\nMeet Banach: The Interface of Asymptotic Geometric Analysis and\nQuantum Information Theory, volume 223 of Mathematical Surveys and\nMonographs. American Mathematical Society.","DOI":"10.1090\/surv\/223"},{"key":"273_CR4","doi-asserted-by":"crossref","unstructured":"Costin B\u0103descu, Ryan O\u2019Donnell & John Wright (2019). Quantum\nstate certification. In Proceedings of the 51st Annual ACM SIGACT\nSymposium on Theory of Computing, 503\u2013514. arXiv:1708.06002.","DOI":"10.1145\/3313276.3316344"},{"key":"273_CR5","doi-asserted-by":"crossref","unstructured":"Avraham Ben-Aroya, Oded Schwartz & Amnon Ta-Shma\n(2010). Quantum Expanders: Motivation and Constructions. Theory of\nComputing 6, 47\u201379. Preliminary version in CCC 2008.","DOI":"10.4086\/toc.2010.v006a003"},{"key":"273_CR6","doi-asserted-by":"crossref","unstructured":"Itay Berman, Akshay Degwekar, Ron D Rothblum &\nPrashant Nalini Vasudevan (2019). Statistical difference beyond\nthe polarizing regime. In Theory of Cryptography Conference, 311\u2013332.\nSpringer. ECCC:TR19-038","DOI":"10.1007\/978-3-030-36033-7_12"},{"key":"273_CR7","unstructured":"Rajendra Bhatia (1996). Matrix Analysis, volume 169. Springer\nScience & Business Media."},{"key":"273_CR8","doi-asserted-by":"crossref","unstructured":"Rajendra Bhatia, Stephane Gaubert & Tanvi Jain (2019). Matrix\nversions of the Hellinger distance. Letters in Mathematical Physics\n109(8), 1777\u20131804. arXiv:1901.01378.","DOI":"10.1007\/s11005-019-01156-0"},{"key":"273_CR9","doi-asserted-by":"crossref","unstructured":"Andrej Bogdanov & Chin Ho Lee (2013). Limits of provable security\nfor homomorphic encryption. In Annual Cryptology Conference,\n111\u2013128. Springer. IACR ePrint:2013\/344.","DOI":"10.1007\/978-3-642-40041-4_7"},{"key":"273_CR10","doi-asserted-by":"crossref","unstructured":"Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler &\nPrashant Nalini Vasudevan (2019). On the power of statistical zero\nknowledge. SIAM Journal on Computing 49(4), FOCS17\u20131. Preliminary\nversion in FOCS 2017. arXiv:1609.02888.","DOI":"10.1137\/17M1161749"},{"key":"273_CR11","doi-asserted-by":"crossref","unstructured":"Gilles Brassard, Peter H\u00f8yer, Michele Mosca & Alain Tapp\n(2002). Quantum amplitude amplification and estimation. Quantum\nComputation and Information 305, 53\u201374. arXiv:quant-ph\/0005055.","DOI":"10.1090\/conm\/305\/05215"},{"key":"273_CR12","doi-asserted-by":"crossref","unstructured":"Jop Bri\u00ebt & Peter Harremo\u00ebs (2009). Properties of classical and\nquantum Jensen-Shannon divergence. Physical review A 79(5), 052 311. arXiv:0806.4472.","DOI":"10.1103\/PhysRevA.79.052311"},{"key":"273_CR13","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Richard Cleve, John Watrous & Ronald\nde Wolf (2001). Quantum fingerprinting. Physical Review Letters\n87(16), 167 902. arXiv:quant-ph\/0102001.","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"273_CR14","doi-asserted-by":"crossref","unstructured":"Cl\u00e9ment L Canonne (2020). A survey on distribution testing: Your\ndata is big. But is it blue? Theory of Computing 1\u2013100. ECCC:TR15-063.","DOI":"10.4086\/toc.gs.2020.009"},{"key":"273_CR15","doi-asserted-by":"crossref","unstructured":"Andr\u00e9 Chailloux, Dragos Florin Ciocan, Iordanis Kerenidis\n& Salil Vadhan (2008). Interactive and noninteractive zero knowledge\nare equivalent in the help model. In Theory of Cryptography Conference,\n501\u2013534. Springer. IACR ePrint:2007\/467.","DOI":"10.1007\/978-3-540-78524-8_28"},{"key":"273_CR16","doi-asserted-by":"crossref","unstructured":"Krzysztof J Ciosmak (2021). Matrix H\u00f6lder\u2019s Inequality\nand Divergence Formulation of Optimal Transport of Vector Measures.\nSIAM Journal on Mathematical Analysis 53(6), 6932\u20136958. arXiv:2109.06588.","DOI":"10.1137\/20M1367520"},{"key":"273_CR17","doi-asserted-by":"crossref","unstructured":"Richard Cleve, Wim van Dam, Michael Nielsen & Alain\nTapp (2013). Quantum entanglement and the communication complexity\nof the inner product function. Theoretical Computer Science\n486, 11\u201319. Preliminary version in Quantum computing and quantum\ncommunication: First NASA International Conference (1998). arXiv:quant-ph\/9708019.","DOI":"10.1016\/j.tcs.2012.12.012"},{"key":"273_CR18","doi-asserted-by":"crossref","unstructured":"Patrick J Coles, M Cerezo & Lukasz Cincio (2019). Strong\nbound between trace distance and Hilbert\u2013Schmidt distance for lowrank\nstates. Physical Review A 100(2), 022 103. arXiv:1903.11738.","DOI":"10.1103\/PhysRevA.100.022103"},{"key":"273_CR19","unstructured":"Sam Cree & Jamie Sikora (2020). A fidelity measure for quantum\nstates based on the matrix geometric mean. arXiv preprint arXiv:2006.06918."},{"key":"273_CR20","doi-asserted-by":"crossref","unstructured":"Stephen Fenner, Frederic Green, Steven Homer & Randall\nPruim (1999). Determining acceptance possibility for a quantum computation\nis hard for the polynomial hierarchy. Proceedings of the Royal\nSociety of London. Series A: Mathematical, Physical and Engineering\nSciences 455(1991), 3953\u20133966. arXiv:quant-ph\/9812056.","DOI":"10.1098\/rspa.1999.0485"},{"key":"273_CR21","doi-asserted-by":"crossref","unstructured":"Steven T Flammia & Ryan O\u2019Donnell (2024). Quantum chisquared\ntomography and mutual information testing. Quantum 8, 1381. arXiv:2305.18519","DOI":"10.22331\/q-2024-06-20-1381"},{"key":"273_CR22","doi-asserted-by":"crossref","unstructured":"Christopher A Fuchs & Carlton M Caves (1994). Ensembledependent\nbounds for accessible information in quantum mechanics.\nPhysical Review Letters 73(23), 3047.","DOI":"10.1103\/PhysRevLett.73.3047"},{"key":"273_CR23","doi-asserted-by":"crossref","unstructured":"Christopher A Fuchs & Jeroen van de Graaf (1999).\nCryptographic distinguishability measures for quantum-mechanical\nstates. IEEE Transactions on Information Theory 45(4), 1216\u20131227. arXiv:quant-ph\/9712042.","DOI":"10.1109\/18.761271"},{"key":"273_CR24","doi-asserted-by":"crossref","unstructured":"Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram\n& Justin Yirka (2022). Quantum generalizations of the polynomial\nhierarchy with applications to QMA(2). computational complexity\n31(2), 1\u201352. Preliminary version in MFCS 2018. arXiv:1805.11139.","DOI":"10.1007\/s00037-022-00231-8"},{"key":"273_CR25","unstructured":"Oded Goldreich (2019). Errata (3-Feb-2019). http:\/\/www.wisdom.weizmann.ac.il\/~\/oded\/entropy.html."},{"key":"273_CR26","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Salil Vadhan (1999). Comparing Entropies in\nStatistical Zero Knowledge with Applications to the Structure of SZK.\nIn Proceedings of the 14th Annual IEEE Conference on Computational\nComplexity, 54\u201373. ECCC:TR98-063.","DOI":"10.1109\/CCC.1999.766262"},{"key":"273_CR27","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Salil P Vadhan (2011). On the Complexity of\nComputational Problems Regarding Distributions. Studies in Complexity\nand Cryptography 6650, 390\u2013405. ECCC:TR11-004.","DOI":"10.1007\/978-3-642-22670-0_27"},{"key":"273_CR28","doi-asserted-by":"crossref","unstructured":"Gus Gutoski, Patrick Hayden, Kevin Milner & Mark M Wilde\n(2015). Quantum Interactive Proofs and the Complexity of Separability\nTesting. Theory of Computing 11(3), 59\u2013103. arXiv:1308.5788.","DOI":"10.4086\/toc.2015.v011a003"},{"key":"273_CR29","doi-asserted-by":"crossref","unstructured":"Fumio Hiai (2021). Quantum f-divergences in von Neumann Algebras.\nSpringer.","DOI":"10.1007\/978-981-33-4199-9"},{"key":"273_CR30","unstructured":"Alexander S Holevo (1973). Bounds for the quantity of information\ntransmitted by a quantum communication channel. Problemy Peredachi\nInformatsii 9(3), 3\u201311."},{"key":"273_CR31","doi-asserted-by":"crossref","unstructured":"Roger A Horn & Charles R Johnson (2012). Matrix analysis.\nCambridge University Press.","DOI":"10.1017\/CBO9781139020411"},{"key":"273_CR32","doi-asserted-by":"crossref","unstructured":"Rahul Jain, Sarvagya Upadhyay & John Watrous (2009). Two-message\nquantum interactive proofs are in PSPACE. In Proceedings of\nthe 50th Annual IEEE Symposium on Foundations of Computer Science,\n534\u2013543. IEEE. arXiv:0905.1300.","DOI":"10.1109\/FOCS.2009.30"},{"key":"273_CR33","doi-asserted-by":"crossref","unstructured":"Thomas Kailath (1967). The divergence and Bhattacharyya distance\nmeasures in signal selection. IEEE Transactions on Communication\nTechnology 15(1), 52\u201360.","DOI":"10.1109\/TCOM.1967.1089532"},{"key":"273_CR34","unstructured":"Alastair Kay (2018). Tutorial on the quantikz package. arXiv preprint arXiv:1809.03842."},{"key":"273_CR35","doi-asserted-by":"crossref","unstructured":"Hirotada Kobayashi (2003). Non-interactive quantum perfect\nand statistical zero-knowledge. In Proceedings of the 14th International\nSymposium on Algorithms and Computation, 178\u2013188. Springer. arXiv:quant-ph\/0207158.","DOI":"10.1007\/978-3-540-24587-2_20"},{"key":"273_CR36","doi-asserted-by":"crossref","unstructured":"Hirotada Kobayashi, Fran\u00e7ois Le Gall & Harumichi\nNishimura (2019). Generalized Quantum Arthur\u2013Merlin Games. SIAM\nJournal on Computing 48(3), 865\u2013902. Preliminary version in CCC\n2015. arXiv:1312.4673.","DOI":"10.1137\/17M1160173"},{"key":"273_CR37","doi-asserted-by":"crossref","unstructured":"Hirotada Kobayashi, Keiji Matsumoto & Tomoyuki Yamakami\n(2009). Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins\nMore Helpful to Arthur? Chicago Journal of Theoretical\nComputer Science 2009, 3. Preliminary version in ISACC 2003.arXiv:quant-ph\/0306051.","DOI":"10.1007\/978-3-540-24587-2_21"},{"key":"273_CR38","unstructured":"Lucien Le Cam (1986). Asymptotic methods in statistical decision\ntheory. Springer Science & Business Media."},{"key":"273_CR39","unstructured":"Fran\u00e7ois Le Gall, Yupan Liu & Qisheng Wang (2023). Spacebounded\nquantum state testing via space-efficient quantum singular\nvalue transformation. arXiv preprint arXiv:2308.05079v2."},{"key":"273_CR40","unstructured":"Yupan Liu (2021). StoqMA Meets Distribution Testing. In 16th Conference\non the Theory of Quantum Computation, Communication and\nCryptography (TQC 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. arXiv:2011.05733."},{"key":"273_CR41","unstructured":"Yupan Liu (2025). Complexity-theoretic perspectives on quantum state\ntesting. Ph.D. thesis, Nagoya University."},{"key":"273_CR42","unstructured":"Yupan Liu & Qisheng Wang (2025a). On Estimating the Quantum\n$$\\ell_{\\alpha}$$ Distance. In Proceedings of the 33rd Annual European Symposium\non Algorithms (ESA 2025), volume 351 of LIPIcs, 105:1\u2013105:20. Schloss\nDagstuhl - Leibniz-Zentrum f\u00fcr Informatik. arXiv:2505.00457."},{"key":"273_CR43","doi-asserted-by":"crossref","unstructured":"Yupan Liu & Qisheng Wang (2025b). On Estimating the Trace\nof Quantum State Powers. In Proceedings of the 2025 Annual ACMSIAM\nSymposium on Discrete Algorithms (SODA), 947\u2013993. SIAM. arXiv:2410.13559.","DOI":"10.1137\/1.9781611978322.28"},{"key":"273_CR44","doi-asserted-by":"crossref","unstructured":"Ana P Majtey, Pedro W Lamberti & Domingo P Prato\n(2005). Jensen-Shannon divergence as a measure of distinguishability\nbetween mixed quantum states. Physical Review A 72(5), 052 310. arXiv:quant-ph\/0508138.","DOI":"10.1103\/PhysRevA.72.052310"},{"key":"273_CR45","doi-asserted-by":"crossref","unstructured":"Chris Marriott & John Watrous (2005). Quantum Arthur\u2013Merlin\ngames. Computational Complexity 14(2), 122\u2013152. Preliminary version\nin CCC 2004. arXiv:cs\/0506068.","DOI":"10.1007\/s00037-005-0194-x"},{"key":"273_CR46","doi-asserted-by":"crossref","unstructured":"Ashley Montanaro & Ronald de Wolf (2016). A Survey of Quantum\nProperty Testing. Theory of Computing 1\u201381. arXiv:1310.2035","DOI":"10.4086\/toc.gs.2016.007"},{"key":"273_CR47","doi-asserted-by":"crossref","unstructured":"Ashwin Nayak & Julia Salzman (2002). On communication\nover an entanglement-assisted quantum channel. In Proceedings of\nthe 34th Annual ACM Symposium on Theory of computing, 698\u2013704. arXiv:quant-ph\/0206122.","DOI":"10.1145\/509907.510007"},{"key":"273_CR48","unstructured":"Michael A Nielsen & Isaac L Chuang (2010). Quantum computation\nand quantum information. Cambridge university press."},{"key":"273_CR49","unstructured":"D\u00e9nes Petz (2007). Quantum information theory and quantum statistics.\nSpringer Science & Business Media."},{"key":"273_CR50","doi-asserted-by":"crossref","unstructured":"Bill Rosgen & John Watrous (2005). On the hardness of distinguishing\nmixed-state quantum computations. In Proceedings of the\n20th Annual IEEE Conference on Computational Complexity, 344\u2013354.\nIEEE. arXiv:cs\/0407056.","DOI":"10.1109\/CCC.2005.21"},{"key":"273_CR51","doi-asserted-by":"crossref","unstructured":"Mary B Ruskai & Frank H Stillinger (1990). Convexity inequalities\nfor estimating free energy and relative entropy. Journal of Physics\nA: Mathematical and General 23(12), 2421.","DOI":"10.1088\/0305-4470\/23\/12\/023"},{"key":"273_CR52","doi-asserted-by":"crossref","unstructured":"Amit Sahai & Salil Vadhan (2003). A complete problem for statistical\nzero knowledge. Journal of the ACM 50(2), 196\u2013249. Preliminary\nversion in FOCS 1997. ECCC:TR00-084.","DOI":"10.1145\/636865.636868"},{"key":"273_CR53","doi-asserted-by":"crossref","unstructured":"Suvrit Sra (2021). Metrics induced by Jensen-Shannon and related\ndivergences on positive definite matrices. Linear Algebra and its Applications\n616, 125\u2013138. arXiv:1911.02643.","DOI":"10.1016\/j.laa.2020.12.023"},{"key":"273_CR54","doi-asserted-by":"crossref","unstructured":"Kristan Temme, Michael James Kastoryano, Mary Beth\nRuskai, Michael Marc Wolf & Frank Verstraete (2010). The\n$$\\chi^2$$-divergence and mixing times of quantum Markov processes. Journal\nof Mathematical Physics 51(12), 122 201. arXiv:1005.2358.","DOI":"10.1063\/1.3511335"},{"key":"273_CR55","doi-asserted-by":"crossref","unstructured":"Kristan Temme & Frank Verstraete (2015). Quantum chisquared\nand goodness of fit testing. Journal of Mathematical Physics\n56(1), 012 202. arXiv:1112.6343","DOI":"10.1063\/1.4905843"},{"key":"273_CR56","doi-asserted-by":"crossref","unstructured":"Flemming Tops\u00f8e (2000). Some inequalities for information divergence\nand related measures of discrimination. IEEE Transactions on\nInformation Theory 46(4), 1602\u20131609.","DOI":"10.1109\/18.850703"},{"key":"273_CR57","unstructured":"Salil P Vadhan (1999). A study of statistical zero-knowledge proofs.\nPh.D. thesis, Massachusetts Institute of Technology."},{"key":"273_CR58","doi-asserted-by":"crossref","unstructured":"Thomas Vidick & John Watrous (2016). Quantum proofs. Foundations\nand Trends\u00ae in Theoretical Computer Science 11(1-2), 1\u2013215. arXiv:1610.01664","DOI":"10.1561\/0400000068"},{"key":"273_CR59","doi-asserted-by":"crossref","unstructured":"D\u00e1niel Virosztek (2021). The metric property of the quantum\nJensen-Shannon divergence. Advances in Mathematics 380, 107 595. arXiv:1910.10447.","DOI":"10.1016\/j.aim.2021.107595"},{"key":"273_CR60","doi-asserted-by":"crossref","unstructured":"Qisheng Wang & Zhicheng Zhang (2024). Fast quantum algorithms\nfor trace distance estimation. IEEE Transactions on Information Theory\n70(4), 2720\u20132733. arXiv:2301.06783.","DOI":"10.1109\/TIT.2023.3321121"},{"key":"273_CR61","doi-asserted-by":"crossref","unstructured":"John Watrous (2002). Limits on the power of quantum statistical\nzero-knowledge. In Proceedings of the 43rd Annual IEEE\nSymposium on Foundations of Computer Science, 459\u2013468. IEEE. arXiv:quant-ph\/0202111.","DOI":"10.1109\/SFCS.2002.1181970"},{"key":"273_CR62","doi-asserted-by":"crossref","unstructured":"John Watrous (2009). Zero-Knowledge against Quantum Attacks.\nSIAM Journal on Computing 39(1), 25\u201358. Preliminary version in\nSTOC 2006. arXiv:quant-ph\/0511020.","DOI":"10.1137\/060670997"},{"key":"273_CR63","unstructured":"Ronald de Wolf (2019). Quantum Computing: Lecture Notes. arXiv\npreprint arXiv:1907.09415."},{"key":"273_CR64","doi-asserted-by":"crossref","unstructured":"Tomoyuki Yamakami & Andrew C Yao (1999). $$\\mathsf{NQP}_{C}$$=$$\\mathsf{coC_{=}P}$$. Information\nProcessing Letters 71(2), 63\u201369. arXiv:quant-ph\/9812032.","DOI":"10.1016\/S0020-0190(99)00084-8"},{"key":"273_CR65","doi-asserted-by":"crossref","unstructured":"Amir Yehudayoff (2020). Pointer chasing via triangular discrimination.\nCombinatorics, Probability and Computing 29(4), 485\u2013494. ECCC:TR16-151.","DOI":"10.1017\/S0963548320000085"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00273-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00273-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00273-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:26Z","timestamp":1764781226000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00273-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,17]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["273"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00273-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,9,17]]},"assertion":[{"value":"6 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"11"}}