CWI Interview with Gilles Brassard

My brother Robert, who is 7 years older than me, taught me college-level mathematics when I was in primary school, and I got hooked. I thought mathematics was nice, interesting and elegant, so much more interesting than real life (laughs). My brother was a very good teacher. In my last year before college, I got an extraordinary math teacher again, who continued to make me interested in math and science in general.

At age 13, I went straight to college, in 1968, starting the first year with science in general, as there was no computer science at the time for first-year students. The second year we had a one-semester course in computer science, and I got hooked during the first term. In those days the only way to have access to a computer was to be registered in a computer science class. There was only one big machine in the whole university and I did not want to stop playing with it, so in the second term I asked a friend of mine if I could use his account, as did another friend. With the three of us on one account, we used more computing time than the whole rest of the class (about one hundred students), so we were caught. I was “severely” punished: I had to program all summer long.  ;)

When I had to choose my specialty, I realized I could either continue in mathematics without any access to computers, or continue in computer science and still do math on my own. So, I decided to register in computer science, and of course I stopped doing (serious) math. So, I like to think of myself as a failed mathematician (laughs). And I got all my degrees in computer science, including my Master’s and PhD. Therefore, I am also an amateur physicist.

In November 1979, just after I finished my PhD at Cornell University, I was in San Juan, Puerto Rico, swimming at the beach, when a complete stranger swam up to me and started telling me that he knows how to use quantum mechanics (of which I knew nothing) to create unforgeable banknotes. And the stranger, I had never seen him before, was Charlie Bennett. I didn’t know.

Bennett explained to me that it was not his idea, it was the idea of a friend of his 10 years before, Stephen Wiesner. Listening to him, at first I thought it was sort of crazy but then it sounded interesting, and I immediately noticed an aspect of Wiesner’s idea that made it useless. Then I realized that what I had just done for my PhD was exactly what was needed to make it useful. So, while swimming, we wrote our first paper. This was not at all considered serious work, we were just having fun, until it was published three years later. In 1982 we had a first paper whose title was ‘Quantum Cryptography’.

What I did not tell you is that I wasn’t on holiday, I was at a conference and he had seen in the program that I was scheduled to talk about cryptography. He spotted me by the reception with my name tag but waited until I was powerless to talk to him, in the water. Bennett was in the habit of telling random strangers about Wiesner’s idea. Seriously, I was the first interested ‘victim’. To make it even more amazing, when I was on the plane to Puerto Rico I read a paper in Scientific American that he wrote, so that was when I learned his name. Next day I meet him and it would never be the same.

From this day we slowly started to continue to talk and visit each other and make these ideas progress until we invented what is known as BB84. This is the prototypical protocol of quantum cryptography that we invented, as the name indicates, in 1983 (laughs), BB of course being our initials. So that’s how we started quantum cryptography, still not taking it seriously at all. It was not our day job, I was still a computer scientist, teaching computer science and cryptography as well. He was still a physicist.

We were just having fun, when I started giving talks about it and was mostly ignored as it was so crazy, until we decided to show them and built a prototype. However, neither of us is an experimentalist, so we asked the help of three students, all three theoreticians as well, although Bennett’s student (John Smolin) had some training in experiments. It is a miracle we were able to build something that worked.

We built this prototype in 1989, and wrote an article in Scientific American that caught attention of the public and research community. Until then it was very obscure. And then some serious people thought it would be interesting to make it work on a larger scale. Today, quantum cryptography as we invented it, is taken seriously by many people and several governments. An expert at Toshiba estimated a 20 billion dollar market by 2035. I don’t know if that’s true but I like to think it might be.

Later, in 1992, Bennett and I were at a general conference on cryptography (classical of course). Bennett gave me a paper from Bill (William) Wootters and Asher Peres. I invited one of them to come to give a talk about their paper in Montréal, and somehow I had this inkling that it is going to be a very interesting talk, more than interesting, so I invited Charlie to come and listen to the talk as well as a former student of mine, Claude Crépeau, who was in Paris at the time.

And at some point during Wootters’s talk, Bennett asks a question, which seems completely irrelevant (would it make a difference if the protagonists shared an EPR pair?—that what we called entanglement at the time). After the talk, we went to my office and brainstormed about Bennett’s question, and within a few hours the answer came, and yes, it would make a difference, because we could use teleportation, which we invented for that purpose. So, quantum teleportation was invented as a result of Bennett’s apparently idle question. It was not at all planned. We were very lucky. Pure serendipity!

I could try. I have to explain something about quantum information. Very small systems like atoms, photons or electrons, don’t behave the way we are used to in our macroscopic experience. They have all kinds of strange properties, in particular if you try to measure their state, they will give a somewhat random answer and will disturb it. This is unavoidable. This is the key to quantum cryptography. If I want to communicate in secret with someone and I send him a quantum system, an eavesdropper trying to intercept the communication will make a disturbance.

About teleportation: let’s say you have a quantum system and it’s in a state, and you don’t know what state it is in. For whatever reason, you want to have this physical piece of quantum information to be somewhere else, say, at your friend’s space shuttle outside the solar system. And you don’t have the option of just bringing him the physical system. What can you do? Well, you cannot measure it, because you cannot measure quantum information. What we discovered is that by using a somewhat surprising property of quantum information, entanglement, we could do this. Say that Alice and Bob that want to communicate, and Alice has this unknown quantum system that she wants to send over to Bob. She makes a joint measurement between the unknown state and her share of the entanglement. Although this is not really what happens, it looks exactly as if the unknown quantum state would appear at Bob’s instantaneously, but encrypted, so that without a key this is as good as pure randomness. But the key is classical, and it is given to Alice. So, when Alice does this measurement, there are two results. One is that the quantum state that she wanted to get to Bob is gone from her hands. But she also gets classical information, which is the key that is needed to unlock the encryption. Alice can send the key to Bob as it is just classical information, no problem. She sends it to Bob and Bob unlocks the quantum state and gets something that is identical to the original. That’s what we call quantum teleportation.

And we call it teleportation for two reasons other than being sensational: one is that it has to disappear from Alice before it appears at Bob. It is necessarily destructive, because one property of quantum information is that it cannot be cloned. If you have one quantum system, you cannot make two out of them. You can move it, but you cannot make two of one. So, if it did not disappear from Alice before appearing at Bob you would have two copies. This necessary destruction of the original evokes Star Trek (laughs). And the other reason we call it teleportation is that the information never finds itself anywhere between Alice and Bob. It is totally magical.

Well, until Bob has the key, he remains completely ignorant of the state Alice wanted to teleport to him. And the key being classical  cannot travel faster than at the speed of light. So teleportation does not violate relativity. There is nothing usable that Bob can obtain faster than light. You may consider that he has Alice’s state, but encrypted so perfectly that it is as good as pure randomness until he receives the classical information. Therefore, no communication happens faster than light, and there is no cloning. So, the two fundamental principles of quantum theory and relativity, which are no cloning and no faster than light communication, are both respected by quantum teleportation. That is how quantum teleportation goes. And that, as opposed to quantum key distribution, was immediately recognized as being important.

I know CWI from David Chaum, who was head of the Crypto group at CWI in the ‘80s. I met him at the first CRYPTO conference, in 1981. Every year we would meet and discuss cryptography at CRYPTO in Santa Barbara, and then he invited me to come here. He organized Eurocrypt 1987 in Amsterdam, and invited me here for a sabbatical of seven months. At the time, I lived in a houseboat across the canal from Heineken, which was still an active brewery. And I was hooked on Amsterdam. So that was my first contact with CWI.

How I met Harry…  In 1992, I gave a talk on quantum computing at the annual Structure in Complexity Theory conference, which was a very new topic at the time. It only became prominent when Peter Shor discovered how to do factoring in 1994, therefore how to break the cryptography used on the Internet. Harry was there, just quietly listening in the audience, and he thought it was very interesting and that is how he began to become interested in quantum computing. And then we met at other occasions, talking, and we realized that we had lots of common interests, including food (laughs). And we became very, very good friends; I think he’s my best friend in Europe. Furthermore, QuSoft is clearly the best place in Europe for quantum information from a theoretical computer science perspective, maybe in the world.

So, I was very happy that I was able to come back. Harry re-invited me several times. In total I spent about one and a half years of my life in Amsterdam, in stretches. I love Amsterdam.

It’s just so pleasant to live here. It is beautiful. I love how all the houses are different, leaning on each other at different angles. Of course, I like walking along the canals and bicycling and also the Concertgebouw! I think that in these 6 months I went to the Concertgebouw at least 30 times. It’s an amazing place. I like all sorts of classical music and the acoustics is amazing, and the main hall and the small hall as well - very, very beautiful and comfortable. I just love the place.

Amsterdam is free and tolerant. Also, I am often reminded by random Dutch people that the Netherlands was liberated by Canadians at the end of the Second World War, so we as Canadians are very welcome. As a people you are welcoming in general but even more so for Canadians. Of course, it makes life easier that you all speak such perfect English. With the downside it does not make it not too imperative for other people to learn Dutch. Seriously, I would love to move here for life, but I feel Dutch is beyond my capability and it would not feel right to move to a country and not learn to speak the language. Well, I know some of the important words like ‘pindakaas’. (laughs)

Well, the right question would be about the future of quantum information! Quantum computing is only one branch of it. There is also quantum communication, which includes cryptography and teleportation, and quantum metrology, to make clocks and telescopes better. So, quantum computing… Well, it is reasonable to believe that it will work one day in the not too far future, so that not taking seriously into account the threat it poses to classical cryptography would be silly.

One of the reasons quantum computing became so prominent is because of Peter Shor’s algorithm in 1994, when Peter first showed that quantum computers, if we could build them (which at the time seemed totally unrealistic) could just break all the cryptography used on the Internet to (attempt to) secure information, like RSA, Diffie-Hellman, elliptic curves. All of that is broken by Shor’s algorithm.

We have known Shor’s algorithm for almost 30 years now and for the first 20-25 years nobody did a thing about it. But nowadays quantum computing becomes reasonably probable in maybe no more than 10 years, so the threat is very serious and people are scrambling to do something. The main reason why this is very serious is because classical cryptography as practiced on the Internet is that people can download all the encrypted information that transits on the Internet and store it, and whenever a quantum computer (or even a classical algorithm that could factor numbers quickly) turns out, then they can just take everything out of storage and decrypt it, and nothing can be done about it. In other words, nothing can save the past, all communication over the Internet from its inception will become an open book when a quantum computer becomes available.

It’s possible that other classical methods exist that would not be susceptible to quantum computing attacks, which is the so-called post-quantum cryptography, but we have no tools to prove this. Nevertheless, they are being studied extensively. However, changing the cryptographic infrastructure is a major thing to do. Once we decide what to do, it will take several years.

Hackers have been able to get into quantum cryptographic communication and break them, but they have to do it as it is going on, because quantum information cannot be copied. You cannot take it down and study it later, you have to attack it as it happens. The main advantage of quantum cryptography over classical post-quantum is that the “harvest now and decrypt later” approach is not possible. One should use quantum cryptography and post-quantum cryptography together rather than thinking it has to be one or the other.

In conclusion, the study of quantum information from a theoretical computer science perspective is very exciting and promising, and one of the best places worldwide to pursue it is QuSoft at CWI.

(Annette Kik, November 2022)