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

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•11 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•3 citations

Remote State Preparation

Charles H. Bennett, David Peter Divincenzo, Peter W. Shor +3 more

Quantum teleportation uses prior entanglement and forward classical communication to transmit one instance of an unknown quantum state. Remote state preparation (RSP) has the same goal, but the sender knows classically what state is to be transmitted. We show that the asymptotic classical communication cost of RSP is one bit per qubit--half that of teleportation--and even less when transmitting part of a known entangled state. We explore the tradeoff between entanglement and classical communication required for RSP, and discuss RSP capacities of general quantum channels.

arXiv:quant-ph/0006044•Physical Review Letters•Jul 26, 2001•865 citations

Remote state preparation without oblivious conditions

A. Hayashi, T. Hashimoto, M. Horibe

In quantum teleportation, neither Alice nor Bob acquires any classical knowledge on teleported states. The teleportation protocol is said to be oblivious to both parties. In remote state preparation (RSP), it is assumed that Alice is given complete classical knowledge on the state that is to be prepared by Bob. Recently, Leung and Shor [e-print quant-ph/0201008] showed that the same amount of classical information as that in teleportation needs to be transmitted in any exact and deterministic RSP protocol that is oblivious to Bob. Assuming that the dimension of subsystems in the prior-entangled state is the same as the dimension of the input space, we study similar RSP protocols, but not necessarily oblivious to Bob. We show that in this case Bob's quantum operation can be safely assumed to be a unitary transformation. We then derive an equation that is a necessary and sufficient condition for such a protocol to exist. By studying this equation, we show that one-qubit RSP requires two classical bits of communication, which is the same amount as in teleportation, even if the protocol is not assumed oblivious to Bob. For higher dimensions, it is still an open question whether the amount of classical communication can be reduced by abandoning oblivious conditions.

arXiv:quant-ph/0205009•Physical Review A•May 13, 2003•118 citations

On communication over an entanglement-assisted quantum channel

A. 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: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.

IEEE Conference on Computational Complexity (CCC)•Jun 25, 2003•10 citations

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•198 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.
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.
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 entanglement and forward classical communication to transmit one instance of an unknown quantum state. Remote state preparation (RSP) has the same goal, but the sender knows classically what state is to be transmitted. We show that the asymptotic classical communication cost of RSP is one bit per qubit--half that of teleportation--and even less when transmitting part of a known entangled state. We explore the tradeoff between entanglement and classical communication required for RSP, and discuss RSP capacities of general quantum channels.
In quantum teleportation, neither Alice nor Bob acquires any classical knowledge on teleported states. The teleportation protocol is said to be oblivious to both parties. In remote state preparation (RSP), it is assumed that Alice is given complete classical knowledge on the state that is to be prepared by Bob. Recently, Leung and Shor [e-print quant-ph/0201008] showed that the same amount of classical information as that in teleportation needs to be transmitted in any exact and deterministic RSP protocol that is oblivious to Bob. Assuming that the dimension of subsystems in the prior-entangled state is the same as the dimension of the input space, we study similar RSP protocols, but not necessarily oblivious to Bob. We show that in this case Bob's quantum operation can be safely assumed to be a unitary transformation. We then derive an equation that is a necessary and sufficient condition for such a protocol to exist. By studying this equation, we show that one-qubit RSP requires two classical bits of communication, which is the same amount as in teleportation, even if the protocol is not assumed oblivious to Bob. For higher dimensions, it is still an open question whether the amount of classical communication can be reduced by abandoning oblivious conditions.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.
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.