Communication complexity of entanglement assisted multi-party computation

• URL: http://arxiv.org/abs/2305.04435v4
• Date: Mon, 5 Feb 2024 15:11:48 GMT
• Title: Communication complexity of entanglement assisted multi-party computation
• Authors: Ruoyu Meng, Aditya Ramamoorthy
• Abstract summary: 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.
• Score: 11.820804392113294
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a quantum and classical version multi-party function computation problem with $n$ players, where players $2, \dots, n$ need to communicate appropriate information to player 1, so that a "generalized" inner product function with an appropriate promise can be calculated. The communication complexity of a protocol is the total number of bits that need to be communicated. When $n$ is prime and for our chosen function, we exhibit a quantum protocol (with complexity $(n-1) \log n$ bits) and a classical protocol (with complexity $(n-1)^2 (\log n^2$) bits). In the quantum protocol, the players have access to entangled qudits but the communication is still classical. Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.

Related papers

• One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
  We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer.
  arXiv  Detail & Related papers  (2023-10-03T19:58:08Z)
• Trade-offs between Entanglement and Communication [5.88864611435337]
  We show that quantum simultaneous protocols with $tildeTheta(k5 log3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement. Prior to our work, only a relational separation was known.
  arXiv  Detail & Related papers  (2023-06-02T01:49:39Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Non-local computation of quantum circuits with small light cones [0.0]
  Port-based teleportation costs much less entanglement when done only on a small number of qubits at a time. We give an explicit class of unitaries for which our protocol's entanglement cost scales better than any known protocol.
  arXiv  Detail & Related papers  (2022-03-18T18:00:06Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Communication Complexity of Private Simultaneous Quantum Messages Protocols [0.609170287691728]
  We study the advantages of quantum communication and prior entanglement of the private simultaneous quantum messages model. We show that the privacy condition inevitably increases the communication cost in the two-party PSQM model. We also show an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings.
  arXiv  Detail & Related papers  (2021-05-15T03:08:01Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• Succinct Blind Quantum Computation Using a Random Oracle [0.8702432681310399]
  We give a new universal blind quantum computation protocol. The protocol's first phase is succinct, that is, its complexity is independent of circuit size.
  arXiv  Detail & Related papers  (2020-04-27T07:47:11Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)

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.