|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Round elimination in exact communication complexity | | Jop Briët
; Harry Buhrman
; Debbie Leung
; Teresa Piovesan
; Florian Speelman
; | | Date: |
21 Dec 2018 | | Abstract: | We study two basic graph parameters, the chromatic number and the orthogonal
rank, in the context of classical and quantum exact communication complexity.
In particular, we consider two types of communication problems that we call
promise equality and list problems. For both of these, it was already known
that the one-round classical and one-round quantum complexities are
characterized by the chromatic number and orthogonal rank of a certain graph,
respectively.
In a promise equality problem, Alice and Bob must decide if their inputs are
equal or not. We prove that classical protocols for such problems can always be
reduced to one-round protocols with no extra communication. In contrast, we
give an explicit instance of a promise equality problem that exhibits an
exponential gap between the one- and two-round exact quantum communication
complexities. Whereas the chromatic number thus fully captures the complexity
of promise equality problems, the hierarchy of "quantum chromatic numbers"
(starting with the orthogonal rank) giving the quantum communication complexity
for every fixed number of communication rounds turns out to enjoy a much richer
structure.
In a list problem, Bob gets a subset of some finite universe, Alice gets an
element from Bob’s subset, and their goal is for Bob to learn which element
Alice was given. The best general lower bound (due to Orlitsky) and upper bound
(due to Naor, Orlitsky, and Shor) on the classical communication complexity of
such problems differ only by a constant factor. We exhibit an example showing
that, somewhat surprisingly, the four-round protocol used in the bound of Naor
et al. can in fact be optimal. Finally, we pose a conjecture on the
orthogonality rank of a certain graph whose truth would imply an intriguing
impossibility of round elimination in quantum protocols for list problems,
something that works trivially in the classical case. | | Source: | arXiv, 1812.9290 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER