Communication Complexity of One-Shot Remote State Preparation
arXiv:1802.07795 · doi:10.1109/TIT.2018.2811509
Abstract
Quantum teleportation uses prior shared entanglement and classical communication to send an unknown quantum state from one party to another. Remote state preparation (RSP) is a similar distributed task in which the sender knows the entire classical description of the state to be sent. (This may also be viewed as the task of non-oblivious compression of a single sample from an ensemble of quantum states.) We study the communication complexity of approximate remote state preparation, in which the goal is to prepare an approximation of the desired quantum state. Jain [Quant. Inf. & Comp., 2006] showed that the worst-case communication complexity of approximate RSP can be bounded from above in terms of the maximum possible information in an encoding. He also showed that this quantity is a lower bound for communication complexity of (exact) remote state preparation. In this work, we tightly characterize the worst-case and average-case communication complexity of remote state preparation in terms of non-asymptotic information-theoretic quantities. We also show that the average-case communication complexity of RSP can be much smaller than the worst-case one. In the process, we show that n bits cannot be communicated with less than n transmitted bits in LOCC protocols. This strengthens a result due to Nayak and Salzman [J. ACM, 2006] and may be of independent interest.
arXiv comment36 pages
References in corpus (29)
- Mixed State Entanglement and Quantum Error Correction
- Remote State Preparation
- Classical Communication Cost in Distributed Quantum Information Processing - A generalization of Quantum Communication Complexity
- Distance measures to compare real and ideal quantum processes
- Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Renyi relative entropy
- Min- and Max- Relative Entropies and a New Entanglement Monotone
- Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask)
- One-Shot Classical-Quantum Capacity and Hypothesis Testing
- A Hierarchy of Information Quantities for Finite Block Length Analysis of Quantum Tasks
- Optimal Remote State Preparation
- Oblivious remote state preparation
- Duality Between Smooth Min- and Max-Entropies
- Low-Entanglement Remote State Preparation
- The quantum capacity of channels with arbitrarily correlated noise
- The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
- Remote preparation of quantum states
- Remote State Preparation without Oblivious Conditions
- Finite blocklength converse bounds for quantum channels
- Single-shot Quantum State Merging
- On bit-commitment based quantum coin flipping
- Smooth Max-Information as One-Shot Generalization for Mutual Information
- Generalized Entropies
- Sine distance for quantum states
- Lower bound on the relative error of mixed-state cloning and related operations
- Strong converse theorems using Rényi entropies
- Strong converse exponents for the feedback-assisted classical capacity of entanglement-breaking channels
- Quantum Stein's lemma revisited, inequalities for quantum entropies, and a concavity theorem of Lieb
- General formulas for capacity of classical-quantum channels
- Role of Hypothesis Testing in Quantum Information