Near-optimal entanglement-communication tradeoffs for remote state preparation

This paper establishes nearly matching upper and lower bounds for the entanglement and communication costs of remote state preparation for rank-$k$ projectors, demonstrating a fundamental equivalence between the ability to perform such preparation and the distillation of $\log d$ ebits of entanglement, while also yielding new results on state incompressibility and an efficient equality protocol.

The Gist

Imagine you are trying to send a very specific, complex recipe to a friend who is in a different city. In the world of quantum physics, this "recipe" is a quantum state (a specific configuration of a particle), and the "city" is a different lab.

Usually, sending a quantum recipe is incredibly expensive. You need a special, pre-shared "magic link" (entanglement) and you have to send a lot of text messages (classical communication) to get it right. This is like Quantum Teleportation, where the sender doesn't even know the recipe; they just have to ship the physical ingredient.

But what if the sender does know the recipe? This is called Remote State Preparation (RSP). Since the sender knows what they want to send, they should be able to do it more efficiently.

This paper tackles a specific, tricky version of this problem: sending a "flat" recipe. Imagine a recipe that isn't just one specific dish, but a perfectly balanced mix of $k$ different ingredients out of a possible $d$ ingredients. The authors ask: How much "magic link" (entanglement) and how many "text messages" (communication) do we actually need to send these mixed recipes?

Here is the breakdown of their findings using simple analogies:

1. The "Magic Link" and the "Text Messages"

Think of the entanglement as a shared bank account of "magic currency" (ebits) that Alice and Bob have. Think of communication as the number of text messages Alice sends to Bob.

• The Old Way: Previous methods were like trying to send a mixed salad by shipping the whole garden (using a huge amount of magic currency) or sending a massive list of instructions (using a huge amount of text messages).
• The New Discovery: The authors found a way to do this that is nearly perfect. They proved that you can't do it with too little magic currency or too few text messages. There is a strict "trade-off": if you want to send fewer messages, you need more magic currency, and vice versa.

2. The "Magic Currency" is Real Money

One of the paper's biggest insights is about the quality of the magic link.

• The Analogy: Imagine you have a jar of coins. Some jars have only pennies (low value), and some have gold bars (high value).
• The Finding: The authors proved that if you want to send these recipes efficiently (using very few text messages), the jar of coins you start with must contain a lot of gold. Specifically, the jar must be rich enough to be able to be "melted down" into a large number of pure gold bars (EPR pairs).
• Why it matters: Before this, we didn't know if a "cheap" magic link (one that couldn't be turned into much gold) could still be used to send recipes efficiently. The paper says no. If you can send the recipe efficiently, your magic link must be "rich" enough to distill a lot of gold.

3. The "Damped Rejection Sampling" (The New Protocol)

The authors didn't just prove limits; they built a new machine (protocol) to do the job.

• The Old Machine (Rejection Sampling): Imagine you are trying to pick a specific card from a deck. The old way was to keep drawing cards until you got the right one. If you were unlucky, you might draw thousands of cards, wasting a lot of time and effort.
• The New Machine (Damped Rejection Sampling): The authors invented a "dampener." Imagine you are still drawing cards, but you put a "speed bump" on the table. If you draw the wrong card, the speed bump slows you down just a tiny bit, so you don't get frustrated and ruin the whole deck. This allows you to try many times without destroying the magic link.
• The Result: This new method uses almost the minimum amount of magic currency possible and sends very few text messages. It's like finding a way to pick the right card with almost zero waste.

4. Real-World Applications Mentioned

The paper shows two specific ways this new "recipe-sending" machine helps:

• The "Uncompressible" Salad: They proved that a specific type of mixed recipe (the "flat states") cannot be shrunk down much smaller than it already is. It's like trying to zip up a bag of water; no matter how hard you try, you can't make it significantly smaller without spilling it. This confirms that these quantum states are naturally "dense" with information.
• The "Are We Equal?" Game: They used their new machine to solve a classic game called "Equality." Two people want to know if they have the same secret number.
  • Old Way: They needed to share a lot of magic coins (about $\log n$) to play the game efficiently.
  • New Way: Using the authors' new method, they only need half as many magic coins ($\frac{1}{2} \log n$) to play the same game with the same accuracy. It's like realizing you can win a game with half the budget you thought you needed.

Summary

In short, this paper is like a master chef and an economist teaming up. They figured out the absolute minimum amount of "ingredients" (entanglement) and "instructions" (communication) needed to send a specific type of quantum recipe. They proved you can't cheat the system (you need rich ingredients if you want to send few instructions), and they built a new, highly efficient kitchen tool (the Damped Rejection Sampling protocol) that gets very close to that theoretical minimum. This allows us to send quantum information much more cheaply and efficiently than before.

Technical Summary

Technical Summary: Near-optimal entanglement-communication tradeoffs for remote state preparation

Problem Statement
The paper investigates the resource costs of Remote State Preparation (RSP), a task where a sender (Alice) holds a classical description of a quantum state and wishes to prepare that state on a receiver's (Bob's) side using shared entanglement and classical communication. Unlike quantum teleportation, where the state is unknown to Alice, RSP leverages Alice's knowledge of the state to potentially reduce communication costs.

The authors focus specifically on the preparation of flat states, defined as mixed states of the form $P/k$, where $P$ is a rank-$k$ projector on a $d$-dimensional Hilbert space $\mathbb{C}^d$. This ensemble, denoted $\mathcal{G}(d, k)$, is significant because flat states are "complete" for RSP; arbitrary RSP tasks can be reduced to RSP of flat states via the "Brothers Extension" method. The central question is to determine the optimal tradeoff between the amount of shared entanglement (measured in ebits) and classical communication (measured in bits) required to prepare these states with a given error tolerance.

Methodology
The authors employ a combination of information-theoretic lower bounds and constructive upper bound protocols.

• Lower Bound Technique:
  The authors introduce a novel approach to lower bounding entanglement costs using smoothed entanglement min-entropy ($H^{\varepsilon}_{\min}$), a measure stronger than the Schmidt rank previously used in RSP literature.

  1. Majorization: They utilize the fact that any RSP protocol using Local Operations and Classical Communication (LOCC) must satisfy a majorization condition: the Schmidt spectrum of the initial shared state must be majorized by the ensemble average of the Schmidt spectra of the final states.
  2. Superposition Argument: To analyze the spectrum of the final states, they run the protocol in superposition over Alice's inputs (projectors drawn from the Haar measure on $\mathcal{G}(d, k)$). This allows them to relate the initial state's spectrum to the average spectrum of the output ensemble.
  3. Spectral Analysis: By conditioning on the classical message $c$ sent by Alice, they show that the reduced state on Bob's side is close to the maximally mixed state, with deviations bounded by the communication cost $m$. Using concentration inequalities and properties of the truncated fidelity function, they derive a lower bound on the smoothed min-entropy of the initial state in terms of $\log d$ and the communication cost.

• Upper Bound Techniques:
  The authors propose two protocols for $(d, k)$-RSP:

  1. Kraus Operator Protocol: A generalization of a protocol by [Ben+05] for pure states. It uses a collection of unitaries to define a generalized measurement (POVM). This protocol achieves near-optimal entanglement cost but incurs a suboptimal communication cost of $\log(d/k) + \log \log d$. It features one-sided error: if the protocol fails, the failure is known; if it succeeds, the state is prepared perfectly.
  2. Damped Rejection Sampling: A novel protocol that refines the standard rejection sampling method. Instead of measuring a fixed projector, Alice measures a sequence of random projectors $Q_i = U_i P U_i^\dagger$ using a "damped" POVM $\{\sqrt{\eta}Q_i, \sqrt{I-\eta Q_i}\}$. This damping prevents the shared entangled state from being significantly disturbed during failed iterations (analogous to the Elitzur-Vaidman bomb testing). This protocol achieves communication cost $\log(d/k) + O(\log(1/\varepsilon))$ with worst-case error $\varepsilon$.
  3. Average-to-Worst-Case Reduction: The authors provide a general reduction showing that any $(d, k)$-RSP protocol with average-case error can be converted to one with worst-case error with only a modest increase in communication, even without shared randomness.

Key Contributions and Results

1. Tight Entanglement-Communication Tradeoffs:
   The paper establishes nearly matching lower and upper bounds for the resources required to prepare flat states.

   • Lower Bound: For any $(d, k)$-RSP protocol with communication $m$ and relaxed average error $\varepsilon_r$, the smoothed entanglement min-entropy of the shared state satisfies:
     $$H^{\delta+\gamma}_{\min}(A)_\sigma \geq \log d - 3\log(1/\gamma) - O(1)$$
     where $\delta$ depends on $k/d$ and $m/d$. Crucially, this implies that any pure entangled state capable of performing RSP with $o(d)$ communication must contain nearly $\log d$ distillable ebits.
   • Upper Bound: The authors present protocols that achieve communication costs of $\log(d/k) + O(\log(1/\varepsilon))$ and entanglement costs of $\lceil \log d \rceil$ ebits (a maximally entangled state of local dimension $d$).

2. Improvement over Prior Bounds:

   • For pure states ($k=1$), the lower bound on entanglement cost outperforms the best previously known bound by [Ben+05] because it uses the stronger smoothed min-entropy measure rather than Schmidt rank.
   • For mixed states, these are the first nearly-matching upper and lower bounds for RSP. Previous works (e.g., [BN20]) provided bounds on the sum of communication and entanglement but did not isolate a non-trivial lower bound on entanglement alone for protocols with $\log d$ communication.

3. Applications:

   • Incompressibility of Flat States: The entanglement lower bound is used to rederive and strengthen the result that ensembles of flat states cannot be compressed (visible compression) by more than a constant number of qubits, even with non-trivial error tolerance.
   • Equality Function Protocol: The authors construct an entanglement-assisted protocol for the Equality function ($EQ_n$) on $n$ bits. By mapping inputs to flat states and using their efficient RSP protocol, they achieve a protocol using $O(1)$ classical communication and only $\frac{1}{2}\log n + O(\log(1/\varepsilon))$ shared EPR pairs. This halves the entanglement cost of previous protocols (which used $\log n$ ebits) while maintaining constant communication.

Significance
The paper claims to resolve the fundamental question of the relationship between communication efficiency and entanglement distillability in the context of RSP. It demonstrates that for pure entangled states, the ability to perform communication-efficient RSP of flat states is essentially equivalent to the ability to distill $\log d$ ebits. This establishes a direct link between the utility of an entangled state for a communication task and its distillable entanglement.

Furthermore, the work provides the first rigorous, nearly-matching bounds for RSP of mixed states, a setting that had been largely unexplored compared to pure state RSP. The "damped rejection sampling" technique offers a new tool for reducing entanglement costs in quantum communication tasks, potentially applicable to state splitting and redistribution. The results suggest that the "cost" of RSP is fundamentally tied to the dimension of the state space, and that significant reductions in entanglement cost (below $\log d$) are impossible without a corresponding linear increase in communication.