Quantum Communication Advantage for Leader Election and Agreement

• URL: http://arxiv.org/abs/2502.07416v1
• Date: Tue, 11 Feb 2025 09:52:20 GMT
• Title: Quantum Communication Advantage for Leader Election and Agreement
• Authors: Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan,
• Abstract summary: We present and show how quantum algorithmic techniques such as Grover search, quantum counting, and quantum walks can make distributed algorithms significantly message-efficient. In particular, our leader election protocol for diameter-2 networks uses quantum walks to achieve the improved message complexity.
• Score: 0.6937243101289334
• License:
• Abstract: This work focuses on understanding the quantum message complexity of two central problems in distributed computing, namely, leader election and agreement in synchronous message-passing communication networks. We show that quantum communication gives an advantage for both problems by presenting quantum distributed algorithms that significantly outperform their respective classical counterparts under various network topologies. While prior works have studied and analyzed quantum distributed algorithms in the context of (improving) round complexity, a key conceptual contribution of our work is positing a framework to design and analyze the message complexity of quantum distributed algorithms. We present and show how quantum algorithmic techniques such as Grover search, quantum counting, and quantum walks can make distributed algorithms significantly message-efficient. In particular, our leader election protocol for diameter-2 networks uses quantum walks to achieve the improved message complexity. To the best of our knowledge, this is the first such application of quantum walks in distributed computing.

Related papers

• A Brief Introduction to Quantum Network Control [7.952919774651851]
  Quantum networking is an emerging area with the potential to transform information processing and communications. We present a brief introduction to quantum network control, an area dedicated to designing algorithms for distributing entanglement (i.e., entangled qubits) We present a model for distributing entanglement in a multi-hop quantum network to enable applications such as quantum key distribution and distributed quantum computing.
  arXiv  Detail & Related papers  (2024-07-29T11:21:45Z)
• Quantum computing topological invariants of two-dimensional quantum matter [0.0]
  We present two quantum circuits for calculating Chern numbers of two-dimensional quantum matter on quantum computers. First algorithm uses many qubits, and we analyze it using a tensor-network simulator of quantum circuits. Second circuit uses fewer qubits, and we implement it experimentally on a quantum computer based on superconducting qubits.
  arXiv  Detail & Related papers  (2024-04-09T06:22:50Z)
• 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)
• Quantum Semantic Communications for Resource-Efficient Quantum Networking [52.3355619190963]
  This letter proposes a novel quantum semantic communications (QSC) framework exploiting advancements in quantum machine learning and quantum semantic representations. The proposed framework achieves approximately 50-75% reduction in quantum communication resources needed, while achieving a higher quantum semantic fidelity.
  arXiv  Detail & Related papers  (2022-05-05T03:49:19Z)
• On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
  We devise three effective QAE-based learning protocols to address three classically computational hard learning problems. Our work sheds new light on developing advanced quantum learning algorithms to accomplish hard quantum physics and quantum information processing tasks.
  arXiv  Detail & Related papers  (2021-06-29T14:01:40Z)
• 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)
• Quantum Federated Learning with Quantum Data [87.49715898878858]
  Quantum machine learning (QML) has emerged as a promising field that leans on the developments in quantum computing to explore large complex machine learning problems. This paper proposes the first fully quantum federated learning framework that can operate over quantum data and, thus, share the learning of quantum circuit parameters in a decentralized manner.
  arXiv  Detail & Related papers  (2021-05-30T12:19:27Z)
• Verification of Distributed Quantum Programs [6.266176871677275]
  We propose a CSP-like distributed programming language to facilitate the specification and verification of distributed quantum systems. The effectiveness of the logic is demonstrated by its applications in the verification of quantum teleportation and local implementation of non-local CNOT gates.
  arXiv  Detail & Related papers  (2021-04-30T07:23:55Z)
• Distributing Multipartite Entanglement over Noisy Quantum Networks [0.0]
  A quantum internet aims at harnessing networked quantum technologies, namely by distributing bipartite entanglement between distant nodes. We present an algorithm for generating multipartite entanglement between different nodes of a quantum network with noisy quantum repeaters and imperfect quantum memories.
  arXiv  Detail & Related papers  (2021-03-26T22:48:05Z)
• 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)
• Distributed Quantum Computing and Network Control for Accelerated VQE [0.0]
  We consider an approach for distributing the accelerated variational quantum eigensolver (AVQE) algorithm over arbitrary sized - in terms of number of qubits - distributed quantum computers. We propose an architecture for a distributed quantum control system in the settings of centralized and decentralized network control.
  arXiv  Detail & Related papers  (2021-01-07T11:50:24Z)

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.