Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9912009 · Physical Review A

Classical-communication cost in distributed quantum-information processing: A generalization of quantum-communication complexity

Hoi‐Kwong Lo

Published Jun 16, 2000• 671 citations
arXivHTMLPDF

Abstract

We study the amount of classical communication needed for distributed quantum-information processing. In particular, we introduce the concept of ``remote preparation'' of a quantum state. Given an ensemble of states, Alice's task is to help Bob in a distant laboratory to prepare a state of her choice. We find several examples of an ensemble with an entropy S where the remote preparation can be done with a communication cost lower than the amount $(2S)$ required by standard teleportation. We conjecture that, for an arbitrary N-dimensional pure state, its remote preparation requires $2{\mathrm{log}}_{2}N$ bits of classical communication, as in standard teleportation.

DOI
10.1103/physreva.62.012313

Related papers

Remote Preparation of Quantum States

C.H. Bennett, Patrick M. Hayden, Debbie Leung +2 more

Remote state preparation is the variant of quantum state teleportation in which the sender knows the quantum state to be communicated. The original paper introducing teleportation established minimal requirements for classical communication and entanglement but the corresponding limits for remote state preparation have remained unknown until now: previous work has shown, however, that it not only requires less classical communication but also gives rise to a tradeoff between these two resources in the appropriate setting. We discuss this problem from first principles, including the various choices one may follow in the definitions of the actual resources. Our main result is a general method of remote state preparation for arbitrary states of many qubits, at a cost of 1 bit of classical communication and 1 bit of entanglement per qubit sent. In this "universal" formulation, these ebit and cbit requirements are shown to be simultaneously optimal by exhibiting a dichotomy. Our protocol then yields the exact tradeoff curve for memoryless sources of pure states (including the case of incomplete knowledge of the ensemble probabilities), based on the recently established quantum-classical tradeoff for visible quantum data compression. A variation of that method allows us to solve the even more general problem of preparing entangled states between sender and receiver (i.e., purifications of mixed state ensembles). The paper includes an extensive discussion of our results, including the impact of the choice of model on the resources, the topic of obliviousness, and an application to private quantum channels and quantum data hiding.

arXiv:quant-ph/0307100•IEEE Transactions on Information Theory•Jan 1, 2005•143 citations

The hidden cost of quantum teleportation and remote state preparation

R. Srikanth

The amount of information transferred during standard quantum teleportation or remote state preparation is equal to the preparation information of the transmitted state, rather than the classical communication required by respective protocol. This is shown by noting that the information required to specify the operation that verifies the transmitted state is identical to the preparation information, at the given level of precision m (in bits). Depending on the resolution of the projective Hilbert space, the preparation information can be made arbitrarily precise and hence indefinitely larger than the classical communication cost. Therefore, the classical communication is insufficient to account for the transfer of preparation information, which is then attributed to the Einstein-Podolsky-Rosen channel. Some fundamental repercussions for relativistic quantum information processing are briefly discussed.

arXiv:quant-ph/0104081•Apr 17, 2001•0 citations

Near-optimal entanglement-communication tradeoffs for remote state preparation

Srijita Kundu, Olivier Lalonde

We study the following task: Alice is given a classical description of a rank-$k$ projector $P$ on $\mathbb{C}^d$, and Alice and Bob want to prepare the quantum state $P/k$ on Bob's side using shared entanglement and classical communication. The general form of this task is known as remote state preparation (RSP). We give nearly-matching lower and upper bounds for the entanglement cost and communication cost for RSP of the states $P/k$. Ours are the first nearly matching upper and lower bounds for RSP of mixed states, and in the special case of pure states, our lower bound outperforms the best previously known lower bound. Our results show that any pure entangled state that can be used to do RSP of these states with $o(d)$ bits of communication, can distill $\log d$ ebits of entanglement, and conversely, any state that can distill $\log d$ ebits of entanglement can be used to do RSP of these states efficiently. As applications of our results, we rederive a previously-known incompressibility result for states of the form $P/k$, and give a new entanglement-assisted communication protocol for the equality function that uses $\frac{1}{2}\log n + O(1)$ many ebits, and $O(1)$ communication.

quant-pharXiv:2602.09428•Feb 11, 2026•0 citations

A.: Remote preparation of quantum states

Charles H. Bennett, Patrick M. Hayden, Debbie Leung +2 more

Abstract—Remote state preparation is the variant of quantum state teleportation in which the sender knows the quantum state to be communicated. The original paper introducing teleportation established minimal requirements for classical communication and entanglement but the corresponding limits for remote state preparation have remained unknown until now: previous work has shown, however, that it not only requires less classical communication but also gives rise to a tradeoff between these two resources in the appropriate setting. We discuss this problem from first principles, including the various choices one may follow in the definitions of the actual resources. Our main result is a general method of remote state preparation for arbitrary states of many qubits, at a cost of 1 bit of classical communication and 1 bit of entanglement per qubit sent. In this “universal ” formulation, these ebit and cbit requirements are shown to be simultaneously optimal by exhibiting a dichotomy. Our protocol then yields the exact tradeoff curve for memoryless sources of pure states (including the case of incomplete knowledge of the ensemble probabilities), based on the recently established quantum-classical tradeoff for visible quantum data compression. A variation of that method allows us to solve the even more general problem of preparing entangled states between sender and receiver (i.e., purifications of mixed state ensembles). The paper includes an extensive discussion of our results, including the impact of the choice of model on the resources, the topic of obliviousness, and an application to private quantum channels and quantum data hiding. Index Terms—Cryptography, entanglement, large deviations, teleportation, tradeoff. I.

•Jul 15, 2003•120 citations

CLASSICAL COMMUNICATION COSTS IN QUANTUM INFORMATION PROCESSING

MING-XING LUO, Xiu‐Bo Chen, Yixian Yang +1 more

Classical communication plays an important role in quantum information processing such as remote state preparation and quantum teleportation. First, in this paper, we present some simple faithful remote state preparation of an arbitrary n-qubit state by constructing entanglement resources and special measurement basis for the sender. Then to weigh the classical resource required, we present an information-theoretical model to evaluate the classical communication cost. By optimizing the classical communication in quantum protocols, we obtain the optimal classical communication cost. This model can also be applied to the quantum teleportation. Moreover, based on the present computation model, we reinvestigate some remote state preparation and teleportation protocols in which the classical communication cost was imperfectly computed. Finally, some problems will be presented.

International Journal of Quantum Information•Jun 15, 2011•4 citations

Communication Complexity of One-Shot Remote State Preparation

Shima Bab Hadiashar, Ashwin Nayak, Renato Renner

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 nonoblivious compression of a single sample from an ensemble of quantum states.) We study the communication complexity of approximate RSP (ARSP) 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 ARSP 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 paper, we tightly characterize the worst-case and average-case communication complexity of remote state preparation in terms of nonasymptotic 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 local operations and classical communication protocols. This strengthens a result due to Nayak and Salzman (J. ACM, 2006) and may be of independent interest.

arXiv:1802.07795•IEEE Transactions on Information Theory•Mar 2, 2018•10 citations
We study the amount of classical communication needed for distributed quantum-information processing. In particular, we introduce the concept of ``remote preparation'' of a quantum state. Given an ensemble of states, Alice's task is to help Bob in a distant laboratory to prepare a state of her choice. We find several examples of an ensemble with an entropy S where the remote preparation can be done with a communication cost lower than the amount (2S)(2S)(2S) required by standard teleportation. We conjecture that, for an arbitrary N-dimensional pure state, its remote preparation requires 2log2N2{\mathrm{log}}_{2}N2log2​N bits of classical communication, as in standard teleportation.
Remote state preparation is the variant of quantum state teleportation in which the sender knows the quantum state to be communicated. The original paper introducing teleportation established minimal requirements for classical communication and entanglement but the corresponding limits for remote state preparation have remained unknown until now: previous work has shown, however, that it not only requires less classical communication but also gives rise to a tradeoff between these two resources in the appropriate setting. We discuss this problem from first principles, including the various choices one may follow in the definitions of the actual resources. Our main result is a general method of remote state preparation for arbitrary states of many qubits, at a cost of 1 bit of classical communication and 1 bit of entanglement per qubit sent. In this "universal" formulation, these ebit and cbit requirements are shown to be simultaneously optimal by exhibiting a dichotomy. Our protocol then yields the exact tradeoff curve for memoryless sources of pure states (including the case of incomplete knowledge of the ensemble probabilities), based on the recently established quantum-classical tradeoff for visible quantum data compression. A variation of that method allows us to solve the even more general problem of preparing entangled states between sender and receiver (i.e., purifications of mixed state ensembles). The paper includes an extensive discussion of our results, including the impact of the choice of model on the resources, the topic of obliviousness, and an application to private quantum channels and quantum data hiding.
The amount of information transferred during standard quantum teleportation or remote state preparation is equal to the preparation information of the transmitted state, rather than the classical communication required by respective protocol. This is shown by noting that the information required to specify the operation that verifies the transmitted state is identical to the preparation information, at the given level of precision m (in bits). Depending on the resolution of the projective Hilbert space, the preparation information can be made arbitrarily precise and hence indefinitely larger than the classical communication cost. Therefore, the classical communication is insufficient to account for the transfer of preparation information, which is then attributed to the Einstein-Podolsky-Rosen channel. Some fundamental repercussions for relativistic quantum information processing are briefly discussed.
We study the following task: Alice is given a classical description of a rank-kkk projector PPP on Cd\mathbb{C}^dCd, and Alice and Bob want to prepare the quantum state P/kP/kP/k on Bob's side using shared entanglement and classical communication. The general form of this task is known as remote state preparation (RSP). We give nearly-matching lower and upper bounds for the entanglement cost and communication cost for RSP of the states P/kP/kP/k. Ours are the first nearly matching upper and lower bounds for RSP of mixed states, and in the special case of pure states, our lower bound outperforms the best previously known lower bound. Our results show that any pure entangled state that can be used to do RSP of these states with o(d)o(d)o(d) bits of communication, can distill log⁡d\log dlogd ebits of entanglement, and conversely, any state that can distill log⁡d\log dlogd ebits of entanglement can be used to do RSP of these states efficiently. As applications of our results, we rederive a previously-known incompressibility result for states of the form P/kP/kP/k, and give a new entanglement-assisted communication protocol for the equality function that uses 12log⁡n+O(1)\frac{1}{2}\log n + O(1)21​logn+O(1) many ebits, and O(1)O(1)O(1) communication.
Abstract—Remote state preparation is the variant of quantum state teleportation in which the sender knows the quantum state to be communicated. The original paper introducing teleportation established minimal requirements for classical communication and entanglement but the corresponding limits for remote state preparation have remained unknown until now: previous work has shown, however, that it not only requires less classical communication but also gives rise to a tradeoff between these two resources in the appropriate setting. We discuss this problem from first principles, including the various choices one may follow in the definitions of the actual resources. Our main result is a general method of remote state preparation for arbitrary states of many qubits, at a cost of 1 bit of classical communication and 1 bit of entanglement per qubit sent. In this “universal ” formulation, these ebit and cbit requirements are shown to be simultaneously optimal by exhibiting a dichotomy. Our protocol then yields the exact tradeoff curve for memoryless sources of pure states (including the case of incomplete knowledge of the ensemble probabilities), based on the recently established quantum-classical tradeoff for visible quantum data compression. A variation of that method allows us to solve the even more general problem of preparing entangled states between sender and receiver (i.e., purifications of mixed state ensembles). The paper includes an extensive discussion of our results, including the impact of the choice of model on the resources, the topic of obliviousness, and an application to private quantum channels and quantum data hiding. Index Terms—Cryptography, entanglement, large deviations, teleportation, tradeoff. I.
Classical communication plays an important role in quantum information processing such as remote state preparation and quantum teleportation. First, in this paper, we present some simple faithful remote state preparation of an arbitrary n-qubit state by constructing entanglement resources and special measurement basis for the sender. Then to weigh the classical resource required, we present an information-theoretical model to evaluate the classical communication cost. By optimizing the classical communication in quantum protocols, we obtain the optimal classical communication cost. This model can also be applied to the quantum teleportation. Moreover, based on the present computation model, we reinvestigate some remote state preparation and teleportation protocols in which the classical communication cost was imperfectly computed. Finally, some problems will be presented.
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 nonoblivious compression of a single sample from an ensemble of quantum states.) We study the communication complexity of approximate RSP (ARSP) 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 ARSP 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 paper, we tightly characterize the worst-case and average-case communication complexity of remote state preparation in terms of nonasymptotic 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 nnn bits cannot be communicated with less than nnn transmitted bits in local operations and classical communication protocols. This strengthens a result due to Nayak and Salzman (J. ACM, 2006) and may be of independent interest.