Using the Q-box to share information

We’ve introduced the idea of a Q-box as an analogy for how a quantum protocol works. Let’s now see how a Q-box can be used by two people to share random strings.

Suppose Alice generates two random binary strings, each of length (n). She uses her first string to decide whether to set up the Q-box in the T/B direction (if the bit is 0) or the L/R direction (if the bit is 1). If she selects T/B, she then uses her second string to choose whether to set state Top (if the bit is 0) or Bottom (if the bit is 1). We can summarise her choice, and how it depends upon the first bits in her two strings, as follows:

Alice then sends the prepared Q-box to Bob. She repeats this (n) times, using a new Q-box each time.

Bob also generates a random binary string of length (n). For each of the (n) boxes he received he uses the corresponding bit of his string to choose whether to do a T/B measurement (if his bit is 0) or a L/R measurement (if his bit is 1). He then records a value of 0 if the outcome of his measurement is Top or Left, and records 1 otherwise.

Example

Suppose Alice’s first string starts with a 0 and her second starts with a 1. Looking at the table, this means she initialises her first Q-box as Bottom. The internal state of the Q-box after initialisation is then either BL or BR, but Alice cannot know which.

Let us consider the two possibilities for the first bit of Bob’s string.

1. If the first bit of Bob’s string is 0 he does a T/B measurement, which will reveal the outcome Bottom, and he records value 1. This matches the first bit of Alice’s second string.
2. If, on the other hand, the first bit of Bob’s string is 1, he does a L/R measurement:
   • if the internal state of the box was BL he gets outcome Left and records value 0 – this disagrees with Alice’s second string;
   • but if it was BR he gets Right and records value 1 – this agrees with Alice’s second string.

So in Case 1, Bob’s recorded value will match Alice’s; in Case 2, Bob’s value matches the first bit of Alice’s string with probability (1 /2).

Your turn!

Try the following exercises, to check your understanding; use the comments to report how you’re getting on.

Working through a similar logic, show that whenever the ith bit of Alice’s first string and Bob’s string match, Bob’s recorded value always matches the ith bit of Alice’s second string. Similarly, show that whenever the ith bit of Alice’s first string and Bob’s string are different, Bob’s recorded value matches the ith bit of Alice’s second string with probability (1 /2).

How is this useful?

In order to share a random string, Alice and Bob can proceed by having Bob announce his random string, i.e., his choice of measurements, after they have been made. Alice then tells him to discard the results from any Q-boxes for which her first string value differs from his; Alice also discards these rounds. Having done so, Alice and Bob should (if everything works perfectly and in the absence of an eavesdropper) share identical random strings.

However, they cannot rely on perfect functionality. In order to check it, Alice randomly selects a small fraction of the remaining rounds and asks Bob to announce his recorded values for these rounds. Alice checks that Bob’s outputs agree with her second string. Both Alice and Bob discard the rounds that Bob announced.