Generalizations of the distributed Deutsch-Jozsa promise problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F17%3A00095802" target="_blank" >RIV/00216224:14330/17:00095802 - isvavai.cz</a>

Výsledek na webu

<a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=9690749&fileId=S0960129515000158" target="_blank" >http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=9690749&fileId=S0960129515000158</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1017/S0960129515000158" target="_blank" >10.1017/S0960129515000158</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Generalizations of the distributed Deutsch-Jozsa promise problem

Popis výsledku v původním jazyce

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}$ &lt;= k &lt;= 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 &lt;= k &lt; (1 - lambda)n, where 0 &lt; lambda &lt; $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ázev v anglickém jazyce

Generalizations of the distributed Deutsch-Jozsa promise problem

Popis výsledku anglicky

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}$ &lt;= k &lt;= 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 &lt;= k &lt; (1 - lambda)n, where 0 &lt; lambda &lt; $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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Mathematical Structures in Computer Science

ISSN

0960-1295

e-ISSN

—

Svazek periodika

27

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

21

Strana od-do

311-331

Kód UT WoS článku

000395533500001

EID výsledku v databázi Scopus

2-s2.0-84929008498