On the quantum communication complexity of total functions

• URL: http://arxiv.org/abs/2608.18784v1
• Date: Wed, 19 Aug 2026 10:42:51 GMT
• Title: On the quantum communication complexity of total functions
• Abstract summary: We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires communication.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

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)
• Constant-round quantum advantage in communication complexity for total functions [1.1602089225841632]
  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.
  arXiv  Detail & Related papers  (2026-08-20T08:32:27Z)
• Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography [0.5862480696321741]
  We show that a shared Greenberger-Horne-Zeilinger state enables completion of a task using only logarithmically many bits of classical communication from each sender.<n>Without preshared entanglement, any protocol achieving high success probability requires communication from at least one sender.<n>As a cryptographic application, we construct a seeded two-source extractor and establish an exponential separation between entangled and unentangled quantum side-information.
  arXiv  Detail & Related papers  (2026-07-30T10:04:53Z)
• Towards efficient and secure quantum-classical communication networks [47.27205216718476]
  There are two primary approaches to achieving quantum-resistant security: quantum key distribution (QKD) and post-quantum cryptography (PQC) We introduce the pros and cons of these protocols and explore how they can be combined to achieve a higher level of security and/or improved performance in key distribution. We hope our discussion inspires further research into the design of hybrid cryptographic protocols for quantum-classical communication networks.
  arXiv  Detail & Related papers  (2024-11-01T23:36:19Z)
• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement [0.0]
  Quantum resources offer advantages over classical methods in addressing this challenge. We show that when the receiver and the senders share a multi-qubit Greenberger-Horne-Zeilinger (GHZ) state, certain global functions of the distributed inputs can be computed with only one bit of classical communication from each sender. We also show that the entanglement-based protocol exhibits significant robustness under white noise.
  arXiv  Detail & Related papers  (2024-09-20T05:17:09Z)
• Communication complexity of entanglement assisted multi-party computation [11.820804392113294]
  We consider a multi-party computation problem with $n$ players, where players $2, dots, n$ need to communicate appropriate information to player 1. We exhibit a quantum protocol (with complexity $(n-1) log n$ bits) and a classical protocol (with complexity $(n-1)2 (log n2$) bits) This demonstrates that our quantum protocol is strictly better than classical protocols.
  arXiv  Detail & Related papers  (2023-05-08T03:10:08Z)
• 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)
• Oblivious Quantum Computation and Delegated Multiparty Quantum Computation [61.12008553173672]
  We propose a new concept, oblivious computation quantum computation, where secrecy of the input qubits and the program to identify the quantum gates are required. Exploiting quantum teleportation, we propose a two-server protocol for this task. Also, we discuss delegated multiparty quantum computation, in which, several users ask multiparty quantum computation to server(s) only using classical communications.
  arXiv  Detail & Related papers  (2022-11-02T09:01:33Z)
• 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)
• 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)

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.