Generalizations of the distributed Deutsch-Jozsa promise
problem

J 2017

Generalizations of the distributed Deutsch-Jozsa promise problem

GRUSKA, Jozef, Daowen QIU a Shenggen ZHENG

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

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í

Odkazy

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

Změněno: 28. 11. 2017 10:08, prof. RNDr. Jozef Gruska, DrSc.

Anotace

V originále

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

Citovat

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.

@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 a Shenggen ZHENG. Generalizations of the distributed Deutsch-Jozsa promise problem. \textit{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.

Podrobný výpis o publikaci