Unbounded quantum advantage in communication complexity measured by distinguishability

• URL: http://arxiv.org/abs/2401.12903v1
• Date: Tue, 23 Jan 2024 16:48:59 GMT
• Title: Unbounded quantum advantage in communication complexity measured by distinguishability
• Authors: Satyaki Manna, Anubhav Chaturvedi, and Debashis Saha
• Abstract summary: In this study, we adopt a novel perspective, measuring the complexity of the communication by the distinguishability of the sender's input. We focus on two important categories of communication complexity tasks - the general version of random access codes and equality problems defined by graphs. We show that the ratio between the distinguishability in classical and quantum communication to achieve the same success metric escalates with the complexity of these tasks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Communication complexity is a pivotal element in information science, with quantum theory presenting a significant edge over classical approaches. The standard quantification of one-way communication complexity relies on the minimal dimension of the systems that the sender communicates to accomplish the designated task. In this study, we adopt a novel perspective, measuring the complexity of the communication by the distinguishability of the sender's input without constraining the dimension of the communicated systems. This measure becomes especially pertinent when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on two important categories of communication complexity tasks - the general version of random access codes and equality problems defined by graphs. We derive lower bounds on the distinguishability of the sender's input as a function of the success metric of these tasks in classical communication. Notably, we show that the ratio between the distinguishability in classical and quantum communication to achieve the same success metric escalates with the complexity of these tasks, reaching arbitrarily large values. Besides, we demonstrate the quantum advantage by employing qubits in solving equality problems associated with odd-cycle graphs. Furthermore, we derive lower bounds on distinguishability for another class of communication tasks, namely, pair-distinguishability tasks, and present several instances of the quantum advantage.

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)
• Physical Layer Aspects of Quantum Communications: A Survey [31.406787669796184]
  Quantum communication systems support unique applications in the form of distributed quantum computing, distributed quantum sensing, and several cryptographic protocols. Main enabler in these communication systems is an efficient infrastructure that is capable to transport unknown quantum states with high rate and fidelity. Despite the fundamental differences between the classic and quantum worlds, there exist universal communication concepts that may proven beneficial in quantum communication systems as well.
  arXiv  Detail & Related papers  (2024-07-12T13:16:47Z)
• Multimodal deep representation learning for quantum cross-platform verification [60.01590250213637]
  Cross-platform verification, a critical undertaking in the realm of early-stage quantum computing, endeavors to characterize the similarity of two imperfect quantum devices executing identical algorithms. We introduce an innovative multimodal learning approach, recognizing that the formalism of data in this task embodies two distinct modalities. We devise a multimodal neural network to independently extract knowledge from these modalities, followed by a fusion operation to create a comprehensive data representation.
  arXiv  Detail & Related papers  (2023-11-07T04:35:03Z)
• 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)
• 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)
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system [0.0]
  We show that a qubit communication without any assistance of classical shared randomness can achieve the goal. We also study communication utility of a class of non-classical toy systems described by symmetric polygonal state spaces.
  arXiv  Detail & Related papers  (2022-02-14T15:29:59Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems. Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
  arXiv  Detail & Related papers  (2021-09-06T14:35:15Z)
• 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)
• Genuine quantum networks: superposed tasks and addressing [68.8204255655161]
  We show how to make quantum networks, both standard and entanglement-based, genuine quantum. We provide them with the possibility of handling superposed tasks and superposed addressing.
  arXiv  Detail & Related papers  (2020-04-30T18:00:06Z)

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.