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

## 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.

• What's the difference if I change your protocol a bit: Alice always measures in the $Z$ basis. If the answer is a bit she wants to send, she leaves it. If it's the opposite answer, she sends a bit to Bob in the appropriate minute. Bob measures all in the Z basis and flips and answer where he receives a bit from Alice. On average, Alice sends $n$ bits, Bob receives $2n$ bits. But there's nothing quantum about this protocol. Swap the Bell pairs for shared randomness. Jul 22 at 6:38
• Even better, forget the shared resources altogether. Alice sends a bit, or not, in each 1 minute window. That means, per minute, she sends 1 trit of information (no bit, 0 or 1 value) by only transmitting 1 qubit. Clearly, that timing resource you provide is quite a powerful construct! Jul 22 at 6:40
• @DaftWullie Yeah, but the time resource is a bit weird -- I'm sending information even when I don't send any physical bit? I can send $\log_2 n$ bits of information using only one bit by just sending the bit at $n^{\rm th}$ minute, for example? Intuitively, it makes obvious sense but I thought there was some theorem in classical information theory that you can't send more than one bit of information by sending one bit. Jul 22 at 7:03
• @FreeAssange Indeed, the timing resource is very weird, and my point is that it's that that you're using rather than the quantum resource. Jul 22 at 7:20

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. During the protocol, he behaves as follows:

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

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. $$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 }$$.

• Thanks for your detailed answer! I'm still a bit confused about the following aspect of the situation: From a physical perspective, Alice does send only 1 bit -- in other words, there is a discrepancy between the physical number of bits actually sent and the number of bits of information that the receiver learns. As DaftWullie pointed out, there is actually nothing quantum about this. Just that the idea that you need to send $n$ bits to learn $n$ bits of information appears to not be true. Jul 23 at 15:26
• OK, re-reading your answer, I think I get it now. Even physically speaking, not sending anything ought to count as a third state of the communication channel (because Bob ought to be able to distinguish between Alice sending 0 and Alice not sending anything). Thus, there is indeed a trit of information being sent every second. Jul 23 at 15:32
• exactly: the fact that there were 3 possible outcomes of the variable Bob learns from Alice means more than 1 bit of information is being communicated to Bob Jul 23 at 19:15