Unbounded quantum advantage in communication complexity measured by distinguishability

• URL: http://arxiv.org/abs/2401.12903v2
• Date: Tue, 24 Dec 2024 05:09:15 GMT
• Title: Unbounded quantum advantage in communication complexity measured by distinguishability
• Authors: Satyaki Manna, Anubhav Chaturvedi, Debashis Saha,
• Abstract summary: We measure the complexity of a task by the minimal distinguishability required to accomplish it. We show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates exponentially.
• Score: 0.0
• License:
• Abstract: Communication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated systems. In this paper, we measure the communication complexity of a task by the minimal distinguishability required to accomplish it, while leaving the dimension of the communicated systems unconstrained. Distinguishability is defined as the maximum probability of correctly guessing the sender's input from the message, quantifying the message's distinctiveness relative to the sender's input. This measure becomes especially relevant when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on three relevant families of communication complexity tasks -- the random access codes, equality problems defined by graphs and the pair-distinguishability tasks. We derive general lower bounds on the minimal classical distinguishability as a function of the success metric of these tasks. We demonstrate that quantum communication outperforms classical communication, presenting explicit protocols and utilizing semi-definite programming methods. In particular, we demonstrate unbounded quantum advantage for random access codes and Hadamard graph-based equality problems. Specifically, we show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates polynomially and exponentially with the complexity of these tasks, reaching arbitrarily large values.

Related papers

• 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)
• Semantic Communication for Cooperative Perception using HARQ [51.148203799109304]
  We leverage an importance map to distill critical semantic information, introducing a cooperative perception semantic communication framework. To counter the challenges posed by time-varying multipath fading, our approach incorporates the use of frequency-division multiplexing (OFDM) along with channel estimation and equalization strategies. We introduce a novel semantic error detection method that is integrated with our semantic communication framework in the spirit of hybrid automatic repeated request (HARQ)
  arXiv  Detail & Related papers  (2024-08-29T08:53:26Z)
• An operational definition of quantum information scrambling [0.0]
  Quantum information scrambling (QIS) is a characteristic feature of several quantum systems. We propose a novel and computationally efficient QIS quantifier based on a formulation of QIS in terms of quantum state discrimination. We show that the optimal guessing probability, which reflects the degree of QIS induced by an isometric quantum evolution, is directly connected to the accessible min-information.
  arXiv  Detail & Related papers  (2023-12-18T19:00:01Z)
• Cognitive Semantic Communication Systems Driven by Knowledge Graph: Principle, Implementation, and Performance Evaluation [74.38561925376996]
  Two cognitive semantic communication frameworks are proposed for the single-user and multiple-user communication scenarios. An effective semantic correction algorithm is proposed by mining the inference rule from the knowledge graph. For the multi-user cognitive semantic communication system, a message recovery algorithm is proposed to distinguish messages of different users.
  arXiv  Detail & Related papers  (2023-03-15T12:01:43Z)
• Emergent Quantized Communication [34.31732248872158]
  We propose an alternative approach to achieve discrete communication -- quantization of communicated messages. Message quantization allows us to train the model end-to-end, achieving superior performance in multiple setups.
  arXiv  Detail & Related papers  (2022-11-04T12:39:45Z)
• Semantic-Native Communication: A Simplicial Complex Perspective [50.099494681671224]
  We study semantic communication from a topological space perspective. A transmitter first maps its data into a $k$-order simplicial complex and then learns its high-order correlations. The receiver decodes the structure and infers the missing or distorted data.
  arXiv  Detail & Related papers  (2022-10-30T22:33:44Z)
• 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)
• Quantum contextuality provides communication complexity advantage [0.683495465775299]
  We show that for any quantum state and observables of sufficiently small dimension producing contextuality, there exists a communication task with quantum advantage. We show how to convert each of these communication tasks into a semi-device independent protocol for quantum key distribution.
  arXiv  Detail & Related papers  (2022-05-06T15:40:57Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• 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)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  encode and decode circuits to reliably send messages over many uses of a noisy channel. For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable. Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
  arXiv  Detail & Related papers  (2020-09-15T15:10:50Z)

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.