Contributions to the study of probabilistic communication complexity classes

Equality and disjointness are two of the most studied problems in communication complexity. They have been studied for both classical and also quantum communication and for various models and modes of communication. Buhrman et al. [Buh98] proved that the exact quantum communication complexity for a promise version of the equality problem is ${\bf O}(\log {n})$ while the classical deterministic communication complexity is $n+1$ for two-way communication, which was the first impressively large (exponential) gap between quantum and classical (deterministic and probabilistic) communication complexity. If an error is tolerated, both quantum and probabilistic communication complexities for equality are ${\bf O}(\log {n})$ . However, even if an error is tolerated, the gaps between quantum (probabilistic) and deterministic complexity are not larger than quadratic for the disjointness problem. It is therefore interesting to ask whether there are some promise versions of the disjointness problem for which bigger gaps can be shown. We give a positive answer to such a question. Namely, we prove that there exists an exponential gap between quantum (even probabilistic) communication complexity and classical deterministic communication complexity of some specific versions of the disjointness problem. Klauck [Kla00] proved, for any language, that the state complexity of exact quantum/classical finite automata, which is a general model of one-way quantum finite automata, is not less than the state complexity of an equivalent one-way deterministic finite automata (1DFA). In this paper we show, using a communication complexity result, that situation may be different for some promise problems. Namely, we show for certain promise problem that the gap between the state complexity of exact one-way quantum finite automata and 1DFA can be exponential.Equality and disjointness are two of the most studied problems in communication complexity. They have been studied for both classical and also quantum communication and for various models and modes of communication. Buhrman et al. [Buh98] proved that the exact quantum communication complexity for a promise version of the equality problem is ${\bf O}(\log {n})$ while the classical deterministic communication complexity is $n+1$ for two-way communication, which was the first impressively large (exponential) gap between quantum and classical (deterministic and probabilistic) communication complexity. If an error is tolerated, both quantum and probabilistic communication complexities for equality are ${\bf O}(\log {n})$. However, even if an error is tolerated, the gaps between quantum (probabilistic) and deterministic complexity are not larger than quadratic for the disjointness problem. It is therefore interesting to ask whether there are some promise versions of the disjointness problem for which bigger gaps can be shown. We give a positive answer to such a question. Namely, we prove that there exists an exponential gap between quantum (even probabilistic) communication complexity and classical deterministic communication complexity of some specific versions of the disjointness problem. Klauck [Kla00] proved, for any language, that the state complexity of exact quantum/classical finite automata, which is a general model of one-way quantum finite automata, is not less than the state complexity of an equivalent one-way deterministic finite automata (1DFA). In this paper we show, using a communication complexity result, that situation may be different for some promise problems. Namely, we show for certain promise problem that the gap between the state complexity of exact one-way quantum finite automata and 1DFA can be exponential.

arXiv:1309.7739Sep 30, 20133 citations

Lower bounds for one-way probabilistic communication complexity

Farid Mansurovich Ablayev

Lecture notes in computer scienceJan 1, 199315 citations

Quantum Communication Cannot Simulate a Public Coin

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf

We study the simultaneous message passing model of communication complexity. Building on the quantum fingerprinting protocol of Buhrman et al., Yao recently showed that a large class of efficient classical public-coin protocols can be turned into efficient quantum protocols without public coin. This raises the question whether this can be done always, i.e. whether quantum communication can always replace a public coin in the SMP model. We answer this question in the negative, exhibiting a communication problem where classical communication with public coin is exponentially more efficient than quantum communication. Together with a separation in the other direction due to Bar-Yossef et al., this shows that the quantum SMP model is incomparable with the classical public-coin SMP model. In addition we give a characterization of the power of quantum fingerprinting by means of a connection to geometrical tools from machine learning, a quadratic improvement of Yao's simulation, and a nearly tight analysis of the Hamming distance problem from Yao's paper.We study the simultaneous message passing model of communication complexity. Building on the quantum fingerprinting protocol of Buhrman et al., Yao recently showed that a large class of efficient classical public-coin protocols can be turned into efficient quantum protocols without public coin. This raises the question whether this can be done always, i.e. whether quantum communication can always replace a public coin in the SMP model. We answer this question in the negative, exhibiting a communication problem where classical communication with public coin is exponentially more efficient than quantum communication. Together with a separation in the other direction due to Bar-Yossef et al., this shows that the quantum SMP model is incomparable with the classical public-coin SMP model. In addition we give a characterization of the power of quantum fingerprinting by means of a connection to geometrical tools from machine learning, a quadratic improvement of Yao's simulation, and a nearly tight analysis of the Hamming distance problem from Yao's paper.

arXiv:quant-ph/0411051Nov 8, 200421 citations

Generalizations of the distributed Deutsch–Jozsa promise problem

Jozef Gruska, Daowen Qiu, Shenggen Zheng

In thedistributed Deutsch–Jozsa promise problem, two parties are to determine whether their respective stringsx, y∈ {0,1}nare at theHamming distanceH(x, y) = 0 orH(x, y) = $\frac{n}{2}$ . Buhrmanet al.(STOC' 98) proved that the exactquantum communication complexityof this problem isO(logn) while thedeterministic communication complexityisΩ(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, whetherH(x, y) = 0 orH(x, y) =k, and show that an exponential gap between exact quantum and deterministic communication complexity still holds ifkis an even such that $\frac{1}{2}$ n⩽k< (1 − λ)n, where 0 < λ < $\frac{1}{2}$ is given. We also deal with a promise version of the well-knowndisjointnessproblem 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.In thedistributed Deutsch–Jozsa promise problem, two parties are to determine whether their respective stringsx, y∈ {0,1}nare at theHamming distanceH(x, y) = 0 orH(x, y) = $\frac{n}{2}$ . Buhrmanet al.(STOC' 98) proved that the exactquantum communication complexityof this problem isO(logn) while thedeterministic communication complexityisΩ(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, whetherH(x, y) = 0 orH(x, y) =k, and show that an exponential gap between exact quantum and deterministic communication complexity still holds ifkis an even such that $\frac{1}{2}$ n⩽k< (1 − λ)n, where 0 < λ < $\frac{1}{2}$ is given. We also deal with a promise version of the well-knowndisjointnessproblem 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.

arXiv:1402.7254Mathematical Structures in Computer ScienceMay 6, 201539 citations

{\bf O}(\log {n})

while the classical deterministic communication complexity is

n+1

for two-way communication, which was the first impressively large (exponential) gap between quantum and classical (deterministic and probabilistic) communication complexity. If an error is tolerated, both quantum and probabilistic communication complexities for equality are

{\bf O}(\log {n})

. However, even if an error is tolerated, the gaps between quantum (probabilistic) and deterministic complexity are not larger than quadratic for the disjointness problem. It is therefore interesting to ask whether there are some promise versions of the disjointness problem for which bigger gaps can be shown. We give a positive answer to such a question. Namely, we prove that there exists an exponential gap between quantum (even probabilistic) communication complexity and classical deterministic communication complexity of some specific versions of the disjointness problem. Klauck [Kla00] proved, for any language, that the state complexity of exact quantum/classical finite automata, which is a general model of one-way quantum finite automata, is not less than the state complexity of an equivalent one-way deterministic finite automata (1DFA). In this paper we show, using a communication complexity result, that situation may be different for some promise problems. Namely, we show for certain promise problem that the gap between the state complexity of exact one-way quantum finite automata and 1DFA can be exponential.

In thedistributed Deutsch–Jozsa promise problem, two parties are to determine whether their respective stringsx, y∈ {0,1}nare at theHamming distanceH(x, y) = 0 orH(x, y) =

\frac{n}{2}

. Buhrmanet al.(STOC' 98) proved that the exactquantum communication complexityof this problem isO(logn) while thedeterministic communication complexityisΩ(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, whetherH(x, y) = 0 orH(x, y) =k, and show that an exponential gap between exact quantum and deterministic communication complexity still holds ifkis an even such that

\frac{1}{2}

n⩽k< (1 − λ)n, where 0 < λ <

\frac{1}{2}

is given. We also deal with a promise version of the well-knowndisjointnessproblem 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.