That was the last word on the theoretical foundations of quantum bit commitments for nearly 25 years. Then, in 2021, a paper by a graduate student named William Kretschmer prompted researchers to confront a question that nobody had thought to ask. Computational hardness was clearly necessary for bit commitments and most other forms of cryptography, but precisely what kind of hardness?

The answer would turn out to be weirder than anybody had anticipated.

Consulting Oracles

The 2021 paper came out of Kretschmer’s struggle to understand a specific version of a problem that sounds conceptually straightforward: How hard is it to distinguish, or discriminate between, two quantum states that look superficially similar? Kretschmer, who’s now a postdoctoral researcher at the Simons Institute, was initially interested in the problem for reasons that had nothing to do with bit commitment.

“Cryptography was not even on my radar,” he said.

The discrimination problem was interesting in part because it wasn’t even clear how to describe it using familiar mathematical language. Complexity theorists traditionally study problems with different possible inputs represented by strings of bits, or 0s and 1s. For the problem of decomposing large numbers into their prime factors, for instance, this string represents the number to be factored.

Even after researchers started studying how quantum physics might be harnessed for computation, they continued to focus on such “classical-input” problems. Typical quantum algorithms start with an ordinary classical bit string and then process it using quantum trickery. But in “quantum-input” problems like Kretschmer’s, the inputs aren’t bit strings — they’re quantum states that are as easily disrupted by computation as by measurement.

“The language with which we’ve described quantum computations in traditional complexity theory can’t directly talk about these problems,” Yuen said.

At first, Kretschmer thought he just needed to translate the problem into more standard language, but he couldn’t figure out how. So he did what complexity theorists often do when they’re desperate: He turned to an oracle.

In complexity theory, the term “oracle” refers to a hypothetical device that can solve a specific problem instantly. A computer with access to an oracle might be able to solve other problems more easily by consulting the oracle as an intermediate step in an algorithm. Of course, oracles don’t actually exist in the real world, but studying them helps complexity theorists understand the relationships between the difficulty levels of different problems.

Kretschmer wondered what kind of oracle could make it easy to distinguish two quantum states — the so-called state-discrimination problem. He decided to start with a special oracle that would boost the power of normal quantum algorithms, the ones that use quantum tricks to solve problems with classical bit string inputs. Such algorithms can solve some problems too hard for classical ones, like factoring large numbers, but they’re not omnipotent — many other problems lie beyond their reach.

Access to Kretschmer’s oracle would enable such algorithms to solve certain classical-input problems too hard for real quantum computers. Kretschmer assumed that it would be overkill, but to his surprise, he proved that the state-discrimination problem could still stump these souped-up quantum algorithms.

“I was really fascinated by William’s paper,” said Luowen Qian, a graduate student studying cryptography at Boston University. “I actually thought it had to be wrong, because it’s so counterintuitive.”