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

Communication Complexity of Remote State Preparation

Shima Bab Hadiashar

Published May 27, 2014• 1 citation
OpenAlex

Abstract

Superdense coding and quantum teleportation are two phenomena which were not possible without prior entanglement. In superdense coding, one sends n bits of information using n/2 qubits in the presence of shared entanglement. However, we show that n bits of information cannot be sent with less than n bits of communication in LOCC protocols even in the presence of prior entanglement. This is an interesting result which will be used in the rest of this thesis. \n \nQuantum teleportation uses prior entanglement and classical communication to send \nan unknown quantum state. Remote state preparation (RSP) is the same distributed task, \nbut in the case that the sender knows the description of the state to be sent, completely. \nWe study the communication complexity of approximate remote state preparation in which \nthe goal is to prepare an approximation of the desired quantum state. Jain showed that the worst-case error communication complexity of RSP can be bounded from above in terms of the maximum possible information in an encoding [18]. He also showed that this quantity is a lower bound for communication complexity of exact remote state preparation [18]. \nIn this thesis, we characterize the worst-case error and average-case error communication complexity of remote state preparation in terms of non-asymptotic information-theoretic quantities. We also utilize the bound we derived for the communication complexity of LOCC protocols in the first part of the thesis, to show that the average-case error communication complexity of RSP can be much smaller than the worst-case.

Related papers

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

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

Experimental multilocation remote state preparation

Magnus Rådmark, Marcin Wieśniak, Marek Żukowski +1 more

Transmission of quantum states is a central task in quantum information science. Remote state preparation (RSP) has the same goal as teleportation, i.e., transferring quantum information without sending physically the information carrier, but in RSP the sender knows the state which is to be transmitted. We present experimental demonstrations of RSP for two and three locations. In our experimental scheme Alice (the preparer) and her three partners share four and six photon polarization entangled singlets. This allows us to perform RSP of two or three copies of a single-qubit state, a two-qubit Bell state, and a three-qubit $W$, or $\overline{W}$ state. A possibility to prepare two-qubit nonmaximally entangled and GHZ states is also discussed. The ability to remotely prepare an entangled states by local projections at Alice is a distinguishing feature of our scheme.

arXiv:1304.4504•Physical Review A•Sep 5, 2013•41 citations

On communication over an entanglement-assisted quantum channel. (arXiv:quant-ph/0206122v1 CROSS LISTED)

Ashwin Nayak, Julia Salzman

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.

•Mar 21, 2018•0 citations

Remote State Preparation for Multiple Parties

Wenhan Dai, Tianyi Peng, Moe Z. Win

Remote state preparation (RSP) is a technique to transmit quantum states with classical communication and previously shared entanglement. In this paper, we consider RSP in a multiparty setting. A simple yet nontrivial case is studied, where there is one sender and two receivers. We put forth a broadcasting method for developing multiparty RSP protocols. We show that this method can remotely prepare arbitrary states by consuming classical and quantum resources. For preparing highly entangled states, the proposed method achieves the lower bound for the amount of consumed resources asymptotically.

IEEE International Conference on Acoustics Speech and Signal Processing•Apr 17, 2019•3 citations

Quantum teleportation and superdense coding

Anirban Pathak

The beauty of the quantum circuit lies in the fact that it can perform certain tasks which are impossible in the classical world. For example, consider teleportation and superdense coding. Teleportation is a quantum task in which an unknown quantum state is transmitted from a sender (Alice) to a spatially separated receiver (Bob) via an entangled quantum channel and with the help of some classical communications. Dense coding is another communication scheme in which if Alice and Bob share a prior entanglement then one of them can send n bits of classical information to the other by communicating m-qubits (m < n). Before we go into the technical details of these two schemes let us try to lucidly visualize the uniqueness of teleportation. Suppose Alice and Bob are spatially separated and Alice wants to send an unknown quantum state |ψ〉 = α|0〉 + β|1〉 to Bob. For some reason she is not allowed to send the state directly through a quantum channel. She cannot measure it and send the information to Bob because the moment she will try to measure the state, it will collapse either to |0〉 or to |1〉. But the state can be sent by using a simple quantum circuit (pre-shared entanglement) and some classical communications. In the process the unknown quantum state gets destroyed at Alice’s end and reappears at Bob’s end. The state never exists in the communication channel. This process is called quantum teleportation. The uniqueness of quantum teleportation will be clearer if we note that the Fax is not an example of teleportation because the original copy remains with the sender. Again a letter posted in a letter box is not an example of teleportation because the letter exists (travels) in its original form in the communication channel. In brief, there is no classical analogue of quantum teleportation. The same is true for dense coding. In this chapter we will describe these two unique quantum communication schemes and discuss their significance and applications.

CRC Press eBooks•Jun 20, 2013•0 citations
Superdense coding and quantum teleportation are two phenomena which were not possible without prior entanglement. In superdense coding, one sends n bits of information using n/2 qubits in the presence of shared entanglement. However, we show that n bits of information cannot be sent with less than n bits of communication in LOCC protocols even in the presence of prior entanglement. This is an interesting result which will be used in the rest of this thesis. \n \nQuantum teleportation uses prior entanglement and classical communication to send \nan unknown quantum state. Remote state preparation (RSP) is the same distributed task, \nbut in the case that the sender knows the description of the state to be sent, completely. \nWe study the communication complexity of approximate remote state preparation in which \nthe goal is to prepare an approximation of the desired quantum state. Jain showed that the worst-case error communication complexity of RSP can be bounded from above in terms of the maximum possible information in an encoding [18]. He also showed that this quantity is a lower bound for communication complexity of exact remote state preparation [18]. \nIn this thesis, we characterize the worst-case error and average-case error communication complexity of remote state preparation in terms of non-asymptotic information-theoretic quantities. We also utilize the bound we derived for the communication complexity of LOCC protocols in the first part of the thesis, to show that the average-case error communication complexity of RSP can be much smaller than the worst-case.
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.
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.
Transmission of quantum states is a central task in quantum information science. Remote state preparation (RSP) has the same goal as teleportation, i.e., transferring quantum information without sending physically the information carrier, but in RSP the sender knows the state which is to be transmitted. We present experimental demonstrations of RSP for two and three locations. In our experimental scheme Alice (the preparer) and her three partners share four and six photon polarization entangled singlets. This allows us to perform RSP of two or three copies of a single-qubit state, a two-qubit Bell state, and a three-qubit WWW, or W‾\overline{W}W state. A possibility to prepare two-qubit nonmaximally entangled and GHZ states is also discussed. The ability to remotely prepare an entangled states by local projections at Alice is a distinguishing feature of our scheme.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.
Remote state preparation (RSP) is a technique to transmit quantum states with classical communication and previously shared entanglement. In this paper, we consider RSP in a multiparty setting. A simple yet nontrivial case is studied, where there is one sender and two receivers. We put forth a broadcasting method for developing multiparty RSP protocols. We show that this method can remotely prepare arbitrary states by consuming classical and quantum resources. For preparing highly entangled states, the proposed method achieves the lower bound for the amount of consumed resources asymptotically.
The beauty of the quantum circuit lies in the fact that it can perform certain tasks which are impossible in the classical world. For example, consider teleportation and superdense coding. Teleportation is a quantum task in which an unknown quantum state is transmitted from a sender (Alice) to a spatially separated receiver (Bob) via an entangled quantum channel and with the help of some classical communications. Dense coding is another communication scheme in which if Alice and Bob share a prior entanglement then one of them can send n bits of classical information to the other by communicating m-qubits (m < n). Before we go into the technical details of these two schemes let us try to lucidly visualize the uniqueness of teleportation. Suppose Alice and Bob are spatially separated and Alice wants to send an unknown quantum state |ψ〉 = α|0〉 + β|1〉 to Bob. For some reason she is not allowed to send the state directly through a quantum channel. She cannot measure it and send the information to Bob because the moment she will try to measure the state, it will collapse either to |0〉 or to |1〉. But the state can be sent by using a simple quantum circuit (pre-shared entanglement) and some classical communications. In the process the unknown quantum state gets destroyed at Alice’s end and reappears at Bob’s end. The state never exists in the communication channel. This process is called quantum teleportation. The uniqueness of quantum teleportation will be clearer if we note that the Fax is not an example of teleportation because the original copy remains with the sender. Again a letter posted in a letter box is not an example of teleportation because the letter exists (travels) in its original form in the communication channel. In brief, there is no classical analogue of quantum teleportation. The same is true for dense coding. In this chapter we will describe these two unique quantum communication schemes and discuss their significance and applications.