Generalizations of the distributed Deutsch-Jozsa promise problem

Abstract

In the {\em distributed Deutsch-Jozsa promise problem}, two parties are to determine whether their respective strings $x,y\in \{0,1{\}}^n$ are at the {\em Hamming distance} $H(x,y)=0$ or $H(x,y)=\frac{n}{2}$. Buhrman et al. (STOC' 98) proved that the exact {\em quantum communication complexity} of this problem is $\mathbf{O}(\log n)$ while the {\em deterministic communication complexity} is $\mathbf{\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}\le k\le 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\le k<(1-\lambda )n$, where $0<\lambda <\frac{1}{2}$ is given. We also deal with a promise version of the well-known {\em 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.

we correct some errors of and improve the presentation the previous version. arXiv admin note: substantial text overlap with arXiv:1309.7739

References in corpus (9)

• Non-locality and Communication Complexity
• Superiority of exact quantum automata for promise problems
• On exact quantum query complexity
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• On the state complexity of semi-quantum finite automata
• Exact quantum query complexity of EXACT and THRESHOLD
• On hybrid models of quantum finite automata
• Potential of quantum finite automata with exact acceptance
• Exponentially more concise quantum recognition of non-RMM regular languages

Cited by in corpus (9)

• On hybrid models of quantum finite automata
• Round elimination in exact communication complexity
• Characterizations of symmetrically partial Boolean functions with exact quantum query complexity
• Quantum Query as a State Decomposition
• Quantum finite automata: A modern introduction
• Exact quantum algorithms have advantage for almost all Boolean functions
• Unary probabilistic and quantum automata on promise problems
• Time-space tradeoffs for two-way finite automata
• Promise problems solved by quantum and classical finite automata