$2$ ebits $+$ $1$ bit $ = 2$ bits?

Question

The Set-Up

Let's say Alice and Bob share $k$ ebits, i.e., they have one-qubit each of each of the $k$ Bell states $\frac{\vert 00\rangle+\vert 11\rangle}{\sqrt{2}}$. Now, Alice wants to send $2n$ bits of classical information to Bob, however, she wants accomplish this via sending as few classical bits as possible. They don't have a quantum channel established between them that Alice can use to implement superdense coding. Is there a way for Alice and Bob to come up with a strategy that lets them utilize the shared ebits to send $2n$ bits of classical information via sending $<2n$ bits?

The Question

I can think of a strategy that, on average, allows Alice to successfully relay $2$ bits of classical information per each classical bit she sends to Bob (using $2$ ebits on average). However, I'm interested in knowing if there are more efficient protocols for such communication (or if such communication is even possible). The spirit of the question is to know whether shared entanglement can be used to do something akin to superdense coding without using a quantum channel.

My Attempt

The relatively simple strategy that I can think of is as follows:

Let's say Alice wants to send two bits of classical information $a,b$. Alice performs the following sub-protocol every minute (and positively completes the sub-protocol well within a minute) until she has sent a classical bit to Bob.

• If $a=0$:
  • She measures her share of an ebit in $Z$ basis.
  • If the outcome of the measurement is equal to $b$, she sends the classical bit $a$ to Bob.
  • If the outcome of the measurement is not equal to $b$, end of the sub-protocol.
• If $a=1$:
  • She measures her share of an ebit in $X$ basis.
  • If the outcome of the measurement is equal to $b$, she sends the classical bit $a$.
  • If the outcome of the measurement is not equal to $b$, end of the sub-protocol.

Alice and Bob have agreed on the order in which ebits will be used up, thus, if Bob receives the message from Alice during the $n^{\rm th}$ minute since they start the procedure (say, Alice uses $1$ extra classical bit to ping Bob that she's starting so Bob can keep the clock), Bob knows that he should use the $n^{\rm th}$ ebit to receive the message. Once Bob has picked the right ebit, if the classical bit he received was $0$, he measures his share of the ebit in $Z$ basis, otherwise he measures it in $X$ basis -- and voila, he recovers the second bit of classical information, namely, $b$.

Of course, it would take Alice $2$ tries, on average, to get the $b$ that she wants to send as the result of her measurement of her share of ebit. Thus, all in all, we have $2n$ ebits $+$ $n$ bits $=$ $2n$ bits.

Answer 1

The protocol you describe is correct, but the resource estimation is wrong. Furthermore, something like superdense coding with purely classical bits is prohibited by the No-Signaling Principle.

This protocol sends more than $n$ cbits

Bob has communication channel $\mathcal{C}$, and he conditions his decisions on the information he can learn from $\mathcal{C}$, whether he received a message or not. The communication protocol between Alice and Bob is initialized with them sharing a sequence of Bell states $|\Phi_i\rangle = (|00\rangle + |11\rangle)/\sqrt{2}$ ($i$ just indicates which timestep corresponds to which Bell state).

When communication begins, both parties set $i=0$. Then, Alice behaves as you described, and Bob behaves as follows:

Define a variable $z\in\{0, 1, \emptyset\}$

While $b$ is unknown:

  1. Check $\mathcal{C}$:

   a. If no signal was received: $z \leftarrow\emptyset$

   b. If a signal $a \in \{0, 1\}$ was received, $z \leftarrow a$

 2. Apply the following controlled operation on $|\Phi_i\rangle$:

   a. If $z=\emptyset$, discard $|\Phi_i\rangle$.

   b. If $z \in \{0, 1\}$ apply $\text{controlled-}H$ (controlled on $z$) and perform computational basis measurement.

 3. increment $i \leftarrow i+1$

Suppose each 2-bit message is equally likely, then theres a 50% chance nothing arrives (Bob learns $\emptyset$) and theres a 25% chance each of Bob receiving $a=0$ or $a=1$. Whether he receives anything, each check of $\mathcal{C}$ therefore counts as $$ -\frac{1}{2} \log_2\left(\frac{1}{2}\right) -2 \cdot \frac{1}{4} \log_2\left(\frac{1}{2}\right) = 1.5\text{ cbits} $$ of information. On average, requiring two steps means that the protocol involves transmission of $3$ cbits of information on average. From a channel capacity perspective, this is less efficient than having just sent $a$ in one timestep and $b$ in another.

As @DaftWullie wrote, this kind of protocol would be like $n$ steps of a purely classical scheme to transmit $x \in \{0, 1\}^n$ where Alice only sends $x_i$ if $x_i=1$. If Bob doesn't receive anything, he records $0$, and so paradoxically (for uniformly distributed $x$) he can learn $n$ bits of information $x=x_1x_2\dots x_n$ having only received $n/2$ cbits. The resolution to this paradox is that Bob does receive information every time he checks the channel, even if nothing arrived.

A deterministic protocol for $2 \text{ ebits } + 1 \text{ cbit } \rightarrow 2 \text{ cbits }$ cannot exist

This follows from the No-Signaling Principal, which states that the use of shared ebits alone cannot allow communication of information.

Alice has a two-bit message $m \in \{0,1\}^2$ ($m$ is uniformly random), access to a shared entangled state $|\psi\rangle$ (e.g. $(|00\rangle + |11\rangle\sqrt{2})^{\otimes n})$, and an operation $A$ that acts on $m$ and her half of $|\psi\rangle$ to output $x$. She applies $A$ to $m$ and $|\psi\rangle$ (so that $|\psi\rangle$ becomes $|\psi'\rangle$), and then she uses a communication channel $\mathcal{C}$ to transmit $x$.

Bob has a an operation $B$ that acts on a single bit $x$ and his half of $|\psi'\rangle$, and his goal is to output a two-bit message $m'\in\{0,1\}^n$ that matches what Alice meant to send ($m'=m$).

We can prove that this is impossible by contradiction. Say $B$ does exist, implying that a single bit $x$ can be combined with $|\psi'\rangle$ to output $m'$. Now discard $\mathcal{C}$ completely - there is now no communication between the parties - and instead feed $B$ a uniformly random cbit $x'$ along with $|\psi'\rangle$. Alice still applies $A$ to $|\psi\rangle$ to prepare the exact same shared entangled state with Bob. But 50% of the time, Bob gets lucky and randomly guesses $x'=x$, inputs it to $B$, and outputs $m'=m$. The probability of guessing $m'=m$ is 25% (4 possible messages $m$), but the existence of $B$ means Bob has a 50% chance of guessing $m$ correctly. This implies that signaling occurred using the shared entanglement, and is in direct contradiction with the No-Signaling principle. Therefore, $B$ cannot not exist and there is no way to accomplish $2 \text{ ebits } + 1 \text{ cbit } \rightarrow 2 \text{ cbits }$.