{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T00:55:01Z","timestamp":1778547301272,"version":"3.51.4"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T00:00:00Z","timestamp":1430870400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2017,3]]},"abstract":"<jats:p>In the<jats:italic>distributed Deutsch\u2013Jozsa promise problem<\/jats:italic>, two parties are to determine whether their respective strings<jats:italic>x, y<\/jats:italic>\u2208 {0,1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>are at the<jats:italic>Hamming distance<\/jats:italic><jats:italic>H<\/jats:italic>(<jats:italic>x, y<\/jats:italic>) = 0 or<jats:italic>H<\/jats:italic>(<jats:italic>x, y<\/jats:italic>) =<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000158_inline1\"\/><jats:tex-math>$\\frac{n}{2}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Buhrman<jats:italic>et al.<\/jats:italic>(STOC' 98) proved that the exact<jats:italic>quantum communication complexity<\/jats:italic>of this problem is<jats:bold>O<\/jats:bold>(log<jats:italic>n<\/jats:italic>) while the<jats:italic>deterministic communication complexity<\/jats:italic>is<jats:bold>\u03a9<\/jats:bold>(<jats:italic>n<\/jats:italic>). This was the first impressive (exponential) gap between quantum and classical communication complexity. In this paper, we generalize the above distributed Deutsch\u2013Jozsa promise problem to determine, for any fixed<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000158_inline1\"\/><jats:tex-math>$\\frac{n}{2}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>\u2a7d<jats:italic>k<\/jats:italic>\u2a7d<jats:italic>n<\/jats:italic>, whether<jats:italic>H<\/jats:italic>(<jats:italic>x, y<\/jats:italic>) = 0 or<jats:italic>H<\/jats:italic>(<jats:italic>x, y<\/jats:italic>) =<jats:italic>k<\/jats:italic>, and show that an exponential gap between exact quantum and deterministic communication complexity still holds if<jats:italic>k<\/jats:italic>is an even such that<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000158_inline2\"\/><jats:tex-math>$\\frac{1}{2}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:italic>n<\/jats:italic>\u2a7d<jats:italic>k<\/jats:italic>&lt; (1 \u2212 \u03bb)<jats:italic>n<\/jats:italic>, where 0 &lt; \u03bb &lt;<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000158_inline2\"\/><jats:tex-math>$\\frac{1}{2}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is given. We also deal with a promise version of the well-known<jats:italic>disjointness<\/jats:italic>problem and show also that for this promise problem there exists an exponential gap between quantum (and also probabilistic) communication complexity and deterministic communication complexity of the promise version of such a disjointness problem. Finally, some applications to quantum, probabilistic and deterministic finite automata of the results obtained are demonstrated.<\/jats:p>","DOI":"10.1017\/s0960129515000158","type":"journal-article","created":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T13:17:24Z","timestamp":1430918244000},"page":"311-331","source":"Crossref","is-referenced-by-count":19,"title":["Generalizations of the distributed Deutsch\u2013Jozsa promise problem"],"prefix":"10.1017","volume":"27","author":[{"given":"JOZEF","family":"GRUSKA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DAOWEN","family":"QIU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SHENGGEN","family":"ZHENG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2015,5,6]]},"reference":[{"key":"S0960129515000158_ref35","first-page":"19","article-title":"Succinctness of two-way probabilistic and quantum finite automata","volume":"12","author":"Yakary\u0131lmaz","year":"2010","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"S0960129515000158_ref12","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.82.665"},{"key":"S0960129515000158_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"S0960129515000158_ref3","unstructured":"Ambainis A. and Freivalds R. (1998). One-way quantum finite automata: Strengths, weaknesses and generalizations. In: Proceedings of the 39th IEEE FOCS 332\u2013341."},{"key":"S0960129515000158_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00138-X"},{"key":"S0960129515000158_ref33","first-page":"159","article-title":"Quantum communication complexity of symmetric predicates","volume":"67","author":"Razborov","year":"2003","journal-title":"Izvestiya of the Russian Academy of Sciences, Mathematics"},{"key":"S0960129515000158_ref15","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1992.0167"},{"key":"S0960129515000158_ref34","unstructured":"Yao A. C. (1979). Some complexity questions related to distributed computing. In: Proceedings of 11th ACM STOC 209\u2013213."},{"key":"S0960129515000158_ref11","doi-asserted-by":"crossref","unstructured":"Buhrman H. , Cleve R. and Wigderson A. (1998). Quantum vs. classical communication and computation. In: Proceedings of 30th ACM STOC 63\u201368.","DOI":"10.1145\/276698.276713"},{"key":"S0960129515000158_ref17","first-page":"254","article-title":"On promise problems: A survey","volume":"3895","author":"Goldreich","year":"2006","journal-title":"LNCS"},{"key":"S0960129515000158_ref37","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2014003"},{"key":"S0960129515000158_ref25","doi-asserted-by":"crossref","unstructured":"Klauck H. (2000). On quantum and probabilistic communication: Las Vegas and one-way protocols. In: Proceedings of the 32th ACM STOC 644\u2013651.","DOI":"10.1145\/335305.335396"},{"key":"S0960129515000158_ref18","volume-title":"Quantum Computing","author":"Gruska","year":"1999"},{"key":"S0960129515000158_ref40","first-page":"273","article-title":"One-way finite automata with quantum and classical states","volume":"7300","author":"Zheng","year":"2012","journal-title":"LNCS"},{"key":"S0960129515000158_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"S0960129515000158_ref5","unstructured":"Ambainis A. , Iraids A. and Smotrovs J. (2013). Exact quantum query complexity of EXACT and THRESHOLD. In: Proceedings of 8th TQC 263\u2013269. Also arXiv:1302.1235."},{"key":"S0960129515000158_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"S0960129515000158_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.06.005"},{"key":"S0960129515000158_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.01.001"},{"key":"S0960129515000158_ref36","first-page":"471","article-title":"State complexity: Recent results and open problems","volume":"64","author":"Yu","year":"2005","journal-title":"Fundamenta Informaticae"},{"key":"S0960129515000158_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"S0960129515000158_ref2","doi-asserted-by":"crossref","unstructured":"Ambainis A. (2013). Superlinear advantage for exact quantum algorithms. In: Proceedings of 45th ACM STOC 891\u2013900.","DOI":"10.1145\/2488608.2488721"},{"key":"S0960129515000158_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.06.008"},{"key":"S0960129515000158_ref9","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026009100467"},{"key":"S0960129515000158_ref4","doi-asserted-by":"crossref","first-page":"0435","DOI":"10.26421\/QIC15.5-6-5","article-title":"Exact quantum algorithms have advantage for almost all Boolean functions","volume":"15","author":"Ambainis","year":"2015","journal-title":"Quantum Information and Computation"},{"key":"S0960129515000158_ref1","doi-asserted-by":"crossref","unstructured":"Aaronson S. and Ambainis A. (2003). Quantum search of spatial regions. In: Proceedings of 44th IEEE FOCS 200\u2013209.","DOI":"10.1109\/SFCS.2003.1238194"},{"key":"S0960129515000158_ref10","doi-asserted-by":"crossref","unstructured":"Brassard G. and H\u00f8yer P. (1997) An exact quantum polynomial-time algorithm for Simon's problem. In: Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems 12\u201323.","DOI":"10.1109\/ISTCS.1997.595153"},{"key":"S0960129515000158_ref38","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2015.02.003","article-title":"Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata","author":"Zheng","year":"2015","journal-title":"Information and Computation"},{"key":"S0960129515000158_ref19","first-page":"191","article-title":"Descriptional complexity issues in quantum computing","volume":"5","author":"Gruska","year":"2000","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0960129515000158_ref29","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen","year":"2000"},{"key":"S0960129515000158_ref23","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3040"},{"key":"S0960129515000158_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9826-8"},{"key":"S0960129515000158_ref13","unstructured":"Buhrman H. and de Wolf R. (2001). Communication complexity lower bounds by polynomials. In: Proceedings of 16th IEEE Conference on Computational Complexity 120\u2013130."},{"key":"S0960129515000158_ref20","unstructured":"Gruska J. , Qiu D. W. and Zheng S. G. (2014). Potential of quantum finite automata with exact acceptance. International Journal of Foundation of Computer Science, accepted. Also arXiv:1404.1689."},{"key":"S0960129515000158_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.01.001"},{"key":"S0960129515000158_ref21","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"key":"S0960129515000158_ref30","doi-asserted-by":"publisher","DOI":"10.1201\/b13055-7"},{"key":"S0960129515000158_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03442-2"},{"key":"S0960129515000158_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"S0960129515000158_ref16","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1987-0871675-6"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129515000158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,7]],"date-time":"2022-05-07T10:19:59Z","timestamp":1651918799000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129515000158\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,6]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["S0960129515000158"],"URL":"https:\/\/doi.org\/10.1017\/s0960129515000158","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,6]]}}}