Is the BB84 protocol an example of "quantum supremacy"?

Question

This is a fairly broad question, I hope it fits here. I am wondering if the BB84 protocol is an example of "quantum supremacy", ie. something a quantum computer can do but something that is assumed a classical computer cannot do the equivalent of. Are there any classical algorithms that can allow for the equivalent of secure key distribution as accomplished through BB84, with unconditional security proof? If not, what would it mean if there did exist such protocol?

Answer 1

This is an interesting question that reflects a conflation of some concepts in quantum information sciences. TL/DR - there is no task in BB84 that corresponds to what we when we speak of quantum computation, so BB84 is not evidence of what researchers mean when they speak of "quantum supremacy". But historians will likely still consider the initial hardware implementing BB84 as a sort of quantum advantage, in much the same way that the "Enigma" machine is a bit of a precursor to an (electronic) computer.

In more detail, lately there's been a push to ask for and discuss evidence of "quantum computational supremacy", with an emphasis on "computation". Adding the word "computational" into the phrase is seen as a means to move away from the loaded phrase "quantum supremacy."

However, this also helps to emphasize that quantum computers may do computational tasks much faster than classical computers. Indeed, this appears to be the sense in to which Preskill referred when coining the phrase.

That is, a key aspect of a programmable quantum computer is the ability to fully explore much of the Hilbert space afforded it. This means that a programmable quantum computer having $n$ qubits can prepare the qubits into a superposition in a Hilbert space of dimension $2^n$ - e.g., exponential in the number of qubits.

Turning to BB84, the BB84 scheme in quantum cryptography does not use any entanglement, and Alice and Bob (and Eve) only work on product states of the $n$ photons traded therebetween. The dimension of their Hilbert space only grows linearly with the length of the secret key. There is no computation in the BB84 quantum key exchange. Similarly, although E92 uses entangled Bell pairs, the Hilbert space dimension of E92 still only grows linearly with the number of qubits exchanged.

The information-theoretical security of BB84 is contingent on the uncertainty principle - which can be recast as a purely classical phenomenon. However, that's not to say that BB84 is not using a uniquely quantum resource - indeed, Alice provides Bob with quanta of light (photons.) This does seem unique and different from that of, for example, classical one-time pads (OTPs.)

Added

In his 1989 article for New Scientist describing the prototype quantum key distribution device that implemented BB84, David Deutsch exclaimed that Bennett, Smolin, and friends who built the machine:

...have created the first information processing device with capabilities that exceed those of the Universal Turing Machine. This is a theoretical model proposed by the English mathematician Alan Turing in 1936... The lasting significance of [the BB84 scheme] will be for the foundations of computer science. The Turing machine is no longer a universal model for practical computations. (Emphasis added)

Thus from Deutsch's 1989 perspective espoused above, devices that implement the BB84 protocol are certainly post-classical, but from the narrower interpretation as used since, e.g., Preskill's 2012 paper the BB84 machines don't explore the entanglement frontier and hence may not be deemed evidence of quantum supremacy.