Quantum and Classical Communication Complexity of Permutation-Invariant Functions

• URL: http://arxiv.org/abs/2401.00454v1
• Date: Sun, 31 Dec 2023 11:07:49 GMT
• Title: Quantum and Classical Communication Complexity of Permutation-Invariant Functions
• Authors: Ziyi Guan, Yunqi Huang, Penghui Yao, Zekun Ye
• Abstract summary: 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 citeAA14, Cha19, BCG+20 to communication complexity.
• Score: 4.410515368583671
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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).

Related papers

• A Meta-Complexity Characterization of Quantum Cryptography [2.8311451575532156]
  We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity.
  arXiv  Detail & Related papers  (2024-10-07T12:29:27Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Approximate traces on groups and the quantum complexity class $\operatorname{MIP}^{co,s}$ [0.0]
  We introduce the notion of a qc-modulus, which encodes approximations to quantum commuting correlations. We show that the existence of a computable qc-modulus gives a negative answer to a natural variant of the aforementioned question.
  arXiv  Detail & Related papers  (2022-09-16T15:45:49Z)
• On query complexity measures and their relations for symmetric functions [0.0]
  We show how to give lower bounds on quantum query complexity using Boolean and adversary methods. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. We show how large certificate complexity and block sensitivity can be as compared to sensitivity for symmetric functions.
  arXiv  Detail & Related papers  (2021-10-25T02:55:39Z)
• Interactive Proofs for Synthesizing Quantum States and Unitaries [0.15229257192293197]
  We study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. We define models of interactive proofs for quantum states and unitaries. We obtain analogous results in the setting with multiple entangled provers as well.
  arXiv  Detail & Related papers  (2021-08-16T15:59:33Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. We introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography.
  arXiv  Detail & Related papers  (2021-03-16T11:05:48Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Representation matching for delegated quantum computing [64.67104066707309]
  representation matching is a generic probabilistic protocol for reducing the cost of quantum computation in a quantum network. We show that the representation matching protocol is capable of reducing the communication or memory cost to almost minimum in various tasks.
  arXiv  Detail & Related papers  (2020-09-14T18:07:43Z)
• Relevant OTOC operators: footprints of the classical dynamics [68.8204255655161]
  The OTOC-RE theorem relates the OTOCs summed over a complete base of operators to the second Renyi entropy. We show that the sum over a small set of relevant operators, is enough in order to obtain a very good approximation for the entropy. In turn, this provides with an alternative natural indicator of complexity, i.e. the scaling of the number of relevant operators with time.
  arXiv  Detail & Related papers  (2020-07-31T19:23:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.