Constant-round quantum advantage in communication complexity for total functions

• URL: http://arxiv.org/abs/2608.19787v1
• Date: Thu, 20 Aug 2026 08:32:27 GMT
• Title: Constant-round quantum advantage in communication complexity for total functions
• Abstract summary: We show that there exists a total function for which there is a gap between the randomized and the constant-round quantum communication complexity.<n>Previously, such separation was known only for quantum protocols usingly many rounds.
• Score: 1.1602089225841632
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

Related papers

• Improved Separations between Quantum and Classical Communication Complexity of Total Functions [1.3706331473063882]
  We refine Gavinsky's framework for exponential separations between quantum and randomized communication complexity of total functions.<n>$ randomized communication with two quantum messages, and versus $(n1-varepsilon)$ for every fixed $0varepsilon1$ with more quantum messages.
  arXiv  Detail & Related papers  (2026-09-15T06:56:34Z)
• On the quantum communication complexity of total functions [0.0]
  We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires communication.
  arXiv  Detail & Related papers  (2026-08-19T10:42:51Z)
• Quantum Channel Polynomial Processing [0.0]
  We introduce a quantum algorithmic framework based on probabilistic mixtures of unitary channels.<n>We show that our framework supports a flexible tradeoff between sample- and query complexity.<n>We argue that our framework can be scaled seamlessly from NISQ to fault-tolerant quantum computing.
  arXiv  Detail & Related papers  (2026-07-07T17:57:48Z)
• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  We establish a continuity relation between the topological space of quantum channels and the quotient of the complex Stiefel manifold. The established relation can be applied to various quantum optimization problems.
  arXiv  Detail & Related papers  (2024-08-19T09:15:54Z)
• Enhanced quantum state transfer: Circumventing quantum chaotic behavior [35.74056021340496]
  We show how to transfer few-particle quantum states in a two-dimensional quantum network. Our approach paves the way to short-distance quantum communication for connecting distributed quantum processors or registers.
  arXiv  Detail & Related papers  (2024-02-01T19:00:03Z)
• On the quantum time complexity of divide and conquer [42.7410400783548]
  We study the time complexity of quantum divide and conquer algorithms for classical problems. We apply these theorems to an array of problems involving strings, integers, and geometric objects.
  arXiv  Detail & Related papers  (2023-11-28T01:06:03Z)
• 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)
• Bounds on oblivious multiparty quantum communication complexity [0.0]
  We show, for a wide class of functions, how to prove strong lower bounds on their oblivious quantum $k$-party communication complexity. In particular, we obtain an optimal $Omega(ksqrtn)$ lower bound on the oblivious quantum $k$-party communication complexity of the $n$-bit Set-Disjointness function.
  arXiv  Detail & Related papers  (2022-10-27T13:09:51Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Post-Quantum Multi-Party Computation [32.75732860329838]
  We study multi-party computation for classical functionalities (in the plain model) with security against malicious-time quantum adversaries. We assume superpolynomial quantum hardness of learning with errors (LWE), and quantum hardness of an LWE-based circular security assumption. Along the way, we develop cryptographic primitives that may be of independent interest.
  arXiv  Detail & Related papers  (2020-05-23T00:42:52Z)

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.