Other formats:
BibTeX
LaTeX
RIS
@article{1315551, author = {Gruska, Jozef and QIU, Daowen and Zheng, Shenggen}, article_number = {3}, doi = {http://dx.doi.org/10.1017/S0960129515000158}, keywords = {Deutch Jozsa problem; quantum automata}, language = {eng}, issn = {0960-1295}, journal = {Mathematical Structures in Computer Science}, title = {Generalizations of the distributed Deutsch-Jozsa promise problem}, url = {http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=9690749&fileId=S0960129515000158}, volume = {27}, year = {2017} }
TY - JOUR ID - 1315551 AU - Gruska, Jozef - QIU, Daowen - Zheng, Shenggen PY - 2017 TI - Generalizations of the distributed Deutsch-Jozsa promise problem JF - Mathematical Structures in Computer Science VL - 27 IS - 3 SP - 311-331 EP - 311-331 PB - Cambridge University Press SN - 09601295 KW - Deutch Jozsa problem KW - quantum automata UR - http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=9690749&fileId=S0960129515000158 L2 - http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=9690749&fileId=S0960129515000158 N2 - In the distributed Deutsch–Jozsa promise problem, two parties are to determine whether their respective strings x, y in {0,1} n are at the Hamming distance H(x, y) = 0 or H(x, y) = $\frac{n}{2}$. Buhrman et al. (STOC' 98) proved that the exact quantum communication complexity of this problem is O(log n) while the deterministic communication complexity is Omega(n). This was the first impressive (exponential) gap between quantum and classical communication complexity. In this paper, we generalize the above distributed Deutsch-Jozsa promise problem to determine, for any fixed $\frac{n}{2}$ <= k <= n, whether H(x, y) = 0 or H(x, y) = k, and show that an exponential gap between exact quantum and deterministic communication complexity still holds if k is an even such that $\frac{1}{2}$n <= k < (1 - lambda)n, where 0 < lambda < $\frac{1}{2}$ is given. We also deal with a promise version of the well-known disjointness 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. ER -
GRUSKA, Jozef, Daowen QIU and Shenggen ZHENG. Generalizations of the distributed Deutsch-Jozsa promise problem. \textit{Mathematical Structures in Computer Science}. Cambridge University Press, 2017, vol.~27, No~3, p.~311-331. ISSN~0960-1295. Available from: https://dx.doi.org/10.1017/S0960129515000158.
|