|
| | | | |
| | | |
| Stat |
Members: 3665
Articles: 2'599'751
Articles rated: 2609
25 January 2025 |
|
| | | | |
|
Article overview
| |
|
|
Matching upper bounds on symmetric predicates in quantum communication complexity | | Daiki Suruga
; | | Date: |
1 Jan 2023 | | Abstract: | In this paper, we focus on the quantum communication complexity of functions
of the form $f circ G = f(G(X_1, Y_1), ldots, G(X_n, Y_n))$ where $f: {0,
1}^n o {0, 1}$ is a symmetric function, $G: {0, 1}^j imes {0, 1}^k
o {0, 1}$ is any function and Alice (resp. Bob) is given $(X_i)_{i leq n}$
(resp. $(Y_i)_{i leq n}$). Recently, Chakraborty et al. [STACS 2022] showed
that the quantum communication complexity of $f circ G$ is
$O(Q(f)mathrm{QCC}_mathrm{E}(G))$ when the parties are allowed to use shared
entanglement, where $Q(f)$ is the query complexity of $f$ and
$mathrm{QCC}_mathrm{E}(G)$ is the exact communication complexity of $G$. In
this paper, we first show that the same statement holds emph{without shared
entanglement}, which generalizes their result. Based on the improved result, we
next show tight upper bounds on $f circ mathrm{AND}_2$ for any symmetric
function $f$ (where $ extrm{AND}_2 : {0, 1} imes {0, 1} o {0, 1}$
denotes the 2-bit AND function) in both models: with shared entanglement and
without shared entanglement. This matches the well-known lower bound by
Razborov~[Izv. Math. 67(1) 145, 2003] when shared entanglement is allowed and
improves Razborov’s bound when shared entanglement is not allowed. | | Source: | arXiv, 2301.00370 | | 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.
|
| |
|
|
|
REGISTER