The minimal communication cost for simulating entangled qubits

• URL: http://arxiv.org/abs/2207.12457v2
• Date: Wed, 11 Oct 2023 17:44:04 GMT
• Title: The minimal communication cost for simulating entangled qubits
• Authors: Martin J. Renner, Marco T\'ulio Quintino
• Abstract summary: We analyze the amount of classical communication required to reproduce the statistics of local projective measurements on a general pair of entangled qubits. We construct a protocol that perfectly simulates local projective measurements on all entangled qubit pairs by communicating one classical trit.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyze the amount of classical communication required to reproduce the statistics of local projective measurements on a general pair of entangled qubits, $|\Psi_{AB}>=\sqrt{p}\ |00>+\sqrt{1-p}\ |11>$ (with $1/2\leq p \leq 1$). We construct a classical protocol that perfectly simulates local projective measurements on all entangled qubit pairs by communicating one classical trit. Additionally, when $\frac{2p(1-p)}{2p-1} \log{\left(\frac{p}{1-p}\right)}+2(1-p)\leq1$, approximately $0.835 \leq p \leq 1$, we present a classical protocol that requires only a single bit of communication. The latter model even allows a perfect classical simulation with an average communication cost that approaches zero in the limit where the degree of entanglement approaches zero ($p \to 1$). This proves that the communication cost for simulating weakly entangled qubit pairs is strictly smaller than for the maximally entangled one.

Related papers

• Distributed inner product estimation with limited quantum communication [3.729242965449096]
  We consider the task of distributed inner product estimation when allowed limited quantum communication. We show that $k=Theta(sqrt2n-q)$ copies are essentially necessary and sufficient for this task. We also consider estimating $|langle psi|M|phirangle|2$, for arbitrary Hermitian $M$.
  arXiv  Detail & Related papers  (2024-10-16T15:46:59Z)
• Coupling without Communication and Drafter-Invariant Speculative Decoding [21.19028671377106]
  Communication-free protocols yield a variant of speculative decoding that we call Drafter-Invariant Speculative Decoding. We show that communication-free protocols yield a variant of speculative decoding that we call Drafter-Invariant Speculative Decoding.
  arXiv  Detail & Related papers  (2024-08-15T06:52:24Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v(i) inmathbbRd$. We propose a new multi-message protocol that achieves the optimal error using $tildemathcalOleft(min(nvarepsilon2,d)right)$ messages per user.
  arXiv  Detail & Related papers  (2024-04-16T00:56:36Z)
• 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)
• Efficient classical simulation of cluster state quantum circuits with alternative inputs [0.0]
  In cluster state quantum computation input qubits are initialised in the equator' of the Bloch sphere. Finally the qubits are measured adaptively using $Z$ measurements or measurements of $cos(theta)X + sin(theta)Y$ operators.
  arXiv  Detail & Related papers  (2022-01-19T15:28:48Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets [15.078027648304115]
  We consider the problem of implementing two-party interactive quantum communication over noisy channels. For a noiseless qudit channel over a $mathrmpoly(n)$ size alphabet, our main result is a simulation method that fails with probability less than $2-Theta(nepsilon)$ We conjecture that it is optimal up to a constant factor in the $sqrtepsilon$ term.
  arXiv  Detail & Related papers  (2020-01-09T02:48: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.