DISTINGUISHABLE FOR WHOM?

May 2026

Álvaro Yángüez Bachiller

In my last story of the month, we saw that quantum cryptography does not merely replace classical protocols with quantum ones. It can change the foundations themselves. In particular, we saw that even if classical cryptography does not exist, intrinsically quantum assumptions such as pseudorandom quantum states could still support meaningful cryptographic tasks.

But how is this possible?

This question naturally leads to a more fundamental one: when we say that two quantum
objects “look the same” to an adversary, what exactly do we mean? If our cryptographer asks a physicist, the answer may seem straightforward. Quantum information theory provides many mathematical tools to quantify distances between quantum states. These quantities tell us how distinguishable two states are.

But there is a catch.

Standard tools usually allow the adversary to perform any quantum transformation and any quantum measurement. This is natural from a mathematical point of view, but too strong from a cryptographic one. In practice, an adversary is computationally bounded: it can only implement efficient operations, namely those that do not require exponentially large time or space.

So the relevant question is not:

Is there some measurement that distinguishes these states?

but rather:

Is there an efficient quantum measurement that distinguishes them?

This distinction is exactly what makes quantum cryptography under computational assumptions possible. It suggests a new way of looking at quantum information quantities: instead of asking what can be distinguished by arbitrary measurements, we ask what can be distinguished by efficient ones. In this way, our quantum cryptographer can model the real power of adversaries and build protocols whose security rests precisely on their computational limitations.