Quantum and Classical Communication Complexity of Permutation-Invariant Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914089966501888 |
|---|---|
| author | Guan, Ziyi Huang, Yunqi Yao, Penghui Ye, Zekun |
| author_facet | Guan, Ziyi Huang, Yunqi Yao, Penghui Ye, Zekun |
| contents | This paper gives a nearly tight characterization of the quantum communication complexity of the permutation-invariant Boolean functions. With such a characterization, we show that the quantum and randomized communication complexity of the permutation-invariant Boolean functions are quadratically equivalent (up to a logarithmic factor). Our results extend a recent line of research regarding query complexity \cite{AA14, Cha19, BCG+20} to communication complexity, showing symmetry prevents exponential quantum speedups.
Furthermore, we show the Log-rank Conjecture holds for any non-trivial total permutation-invariant Boolean function. Moreover, we establish a relationship between the quantum/classical communication complexity and the approximate rank of permutation-invariant Boolean functions. This implies the correctness of the Log-approximate-rank Conjecture for permutation-invariant Boolean functions in both randomized and quantum settings (up to a logarithmic factor). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00454 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Quantum and Classical Communication Complexity of Permutation-Invariant Functions Guan, Ziyi Huang, Yunqi Yao, Penghui Ye, Zekun Computational Complexity Quantum Physics This paper gives a nearly tight characterization of the quantum communication complexity of the permutation-invariant Boolean functions. With such a characterization, we show that the quantum and randomized communication complexity of the permutation-invariant Boolean functions are quadratically equivalent (up to a logarithmic factor). Our results extend a recent line of research regarding query complexity \cite{AA14, Cha19, BCG+20} to communication complexity, showing symmetry prevents exponential quantum speedups. Furthermore, we show the Log-rank Conjecture holds for any non-trivial total permutation-invariant Boolean function. Moreover, we establish a relationship between the quantum/classical communication complexity and the approximate rank of permutation-invariant Boolean functions. This implies the correctness of the Log-approximate-rank Conjecture for permutation-invariant Boolean functions in both randomized and quantum settings (up to a logarithmic factor). |
| title | Quantum and Classical Communication Complexity of Permutation-Invariant Functions |
| topic | Computational Complexity Quantum Physics |
| url | https://arxiv.org/abs/2401.00454 |