Stephen Wiesner

I’m deeply saddened by the death of Stephen Wiesner.

I got to know Steve from his sporadic arrivals to Dorit Aharonov’s seminars at the Hebrew University while I was a grad student there. Even though we met infrequently and didn’t have a chance to meet in the last couple of years, his work and character strongly influenced me.

Steve was arguably the father of quantum information and quantum cryptography.

He had two major contributions: Quantum money – which I’ll expand upon later, and super-dense coding, which he discovered with Charles Bennett in 1992. They asked the following question: how much classical information can Alice send Bob by transferring him a qubit? It turns out that if they have shared entanglement, then the answer is precisely 2 bits of information. Super-dense coding was the first work that viewed entanglement as a resource for communication tasks, and demonstrated that entanglement provides a tangible advantage. The advantage here is due to Holevo’s bound – which showed that without shared entanglement, a qubit could be used to send only 1 bit of information (though, I’m not sure if they were aware of it at the time). This protocol was the precursor of quantum teleportation, a closely related protocol discovered a year later.

Edit: Gilles Brassard commented that super-dense coding was first invented by Wiesner in 1970(!), 22 years before finally getting published. Charlie emailed his original note of his conversation with Steve. Charlie commented that he “added the pencilled notation “False” a little later (maybe a week or so) when he [Or: that is, Steve] realized that all four Bell states could be distinguished by a joint measurement.”

Charlie Bennett’s notes on an early version of superdense coding, dated from Feb. 24, 1970

His invention of quantum money was a tour de force, for reasons which will become clear shortly. So, what is quantum money? In his words, simply “money that it is physically impossible to counterfeit.” As far as I know, he started pondering about it during university strikes in 1968 at Columbia University, when he had some free time.

One of the key ideas in modern cryptography is to turn lemons into lemonade: the lemons are intractable computational problems, and the lemonades are the secure protocols. This is done by a security reduction, showing that in order to break the protocol, one essentially has to solve the intractable problem; hence, breaking it should take a very long time. The basic idea he had in mind is to use a different lemon, namely, the no-cloning property of quantum mechanics, to reason about the security of his quantum money scheme. To understand the challenges that he faced, one needs to remember that modern cryptography was invented in the mid-’70s, so the lemons-to-lemonade approach wasn’t invented, and the no-cloning theorem was discovered only a decade later! And even the model we take for granted, including qubits, how they can be manipulated, etc. had to be figured out, pretty much from scratch. So, his work is essentially a masterpiece of persuasive writing, explaining high-level ideas, and contains very few technical calculations. It’s hard to express how vastly different his writing style is from contemporary works, especially in cryptography.

He submitted his paper in 1969 to IEEE transactions on information theory. At the time, no one thought of quantum theory as a theory of information, and the manuscript was rejected. As far as I remember, he told me that he didn’t try to resubmit it anywhere, and that the message he received from most of the people around him (including his PhD. supervisor) was that these ideas aren’t “serious science”. Luckily, he sent copies of the manuscript to some of his colleagues, including Charlie Bennett, whom he knew from his undergraduate studies. As is well documented (see, e.g., Gilles Brassard’s piece here), these ideas were polished and later led to the development of Quantum Key Distribution.

The same manuscript that introduced quantum money also invented 1-of-2 oblivious transfer, which he called multiplexing. The catch? His result was, essentially, incorrect. A perfect 1-of-2 oblivious transfer, as he suggested is impossible; but imperfect variants are possible. It took more than 4 decades until André Chailloux, Gus Gutoski and Jamie Sikora fully resolved it. (And this work is part of a large project, tightly related to quantum coin-flipping, arguably, one of the deepest topics in quantum information science.) So, even though the scientific method (or, at least, its institutions) spectacularly failed in this case, the establishment had some reasons. In that regard, I recommend reading Asher Peres’s approach where he says that he “…was the referee who approved the publication of Nick Herbert’s FLASH paper, knowing perfectly well that it was wrong”. In other words, there are exceptional cases where even incorrect papers should get published. Unfortunately, there is no agreed-upon mechanism for that.

On a personal note, I have two vivid memories of him.

During my post-doc at Berkeley (2014), I came for a visit in Israel, and gave a talk about an adaptive attack on his scheme, based on a collaboration with Aharon Brodutch, Daniel Nagaj, and Dominique Unruh. The talk was at the Hebrew University and was still an ongoing project, and I was a bit nervous: I definitely didn’t want to insult him in any way. I remember Steve was only mildly interested during the talk. Later, I asked him for comments, and he kindly replied that this wasn’t how he imagined the quantum money would be used; for the attack to work, we assumed the attacker could ask for valid money back from the verifier. Of course, our goal was to spell out exactly how the scheme could be used securely, and non-trivial ways in which it wasn’t. This is exactly the type of questions asked in modern cryptography, and I feel he didn’t find these questions particularly interesting at the time.

Around the same time, I saw him on campus, and invited him to another lecture, this time, comparing quantum money and Bitcoin. He was familiar with Bitcoin (at the time, Bitcoin wasn’t as popular as it is today), and was very interested but refused. I offered him a ride, and tried to persuade him, but to no avail: the talk was at the Google startup campus at Tel-Aviv, and he was very concerned that there will be a security camera recording him entering the building. Last week I learned from his daughter, Sarah, (who was and still is very active in the Israeli Bitcoin scene), that they later viewed a recording of it.

In late 2020, I invited him for another lecture devoted to recent progress on quantum money and related topics, but he politely refused, since he was too weak to attend.

I would like to offer my deepest condolences to his family, friends, and colleagues. To read more about him and his work, see Scott Aaronson’s blog post.

~ by orsattath on August 14, 2021.