Generalizations of the distributed Deutsch-Jozsa promise problem

GRUSKA, Jozef, Daowen QIU a Shenggen ZHENG. Generalizations of the distributed Deutsch-Jozsa promise problem. Mathematical Structures in Computer Science. Cambridge University Press, 2017, roč. 27, č. 3, s. 311-331. ISSN 0960-1295. Dostupné z: https://dx.doi.org/10.1017/S0960129515000158.

Základní údaje

• Originální název: Generalizations of the distributed Deutsch-Jozsa promise problem
• Autoři: GRUSKA, Jozef (703 Slovensko, domácí), Daowen QIU (156 Čína) a Shenggen ZHENG (156 Čína, garant, domácí).
• Vydání: Mathematical Structures in Computer Science, Cambridge University Press, 2017, 0960-1295.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Velká Británie a Severní Irsko
• Utajení: není předmětem státního či obchodního tajemství
• WWW: URL
• Impakt faktor: Impact factor: 1.094
• Kód RIV: RIV/00216224:14330/17:00095802
• Organizační jednotka: Fakulta informatiky
• Doi: http://dx.doi.org/10.1017/S0960129515000158
• UT WoS: 000395533500001
• Klíčová slova anglicky: Deutch Jozsa problem; quantum automata
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.

Návaznosti

• EE2.3.30.0009, projekt VaV: Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci