Bennett and Brassard Win the Turing Award

Gilles Brassard and Charlie Bennett

Charlie Bennett and Gilles Brassard will receive the 2025 ACM Turing Award for their work on the foundations of quantum information science, the first Turing award for quantum. Read all about it in The New York Times, Science and Quanta.

Bennett and Brassard famously met in the water off a beach during the 1979 FOCS conference in Puerto Rico. That led to years of collaboration, most notably for their quantum secure key distribution protocol. The basic idea is pretty simple and does not require quantum entanglement. Alice sends a series of random bits, either straightforward or rotated 45 degrees. Bob measures each of these bits in randomly chosen bases. They discard the bits where they used different bases and use some of the remaining bits to check for eavesdropping, which would collapse the state, and others to set the key.

Bennett and Brassard and four other authors showed how to teleport a quantum bit using entanglement and two classical bits. Bennett with Stephen Wiesner gave the dual superdense coding protocol of sending two classical bits using a single quantum bit. 

Bennett and Brassard, with Ethan Bernstein and Umesh Vazirani, showed that in black-box setting, quantum computers would require \(\Omega(\sqrt{n})\) queries to search \(n\) entries, matching Grover's algorithm. For some reason, the popular press rarely covers these results that limit the power of quantum computing. 

I've had the pleasure of knowing both Bennett and Brassard since the 1980s, both just full of enthusiasm and wonderful ideas. 

Let me end by saying I don't see this as a Turing award for quantum computing. Once (if?) we get large scale machines, we'll certainly see Turing awards, if not Nobel Prizes, for Peter Shor, Umesh Vazirani and others.