 |
| 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.
"we'll certainly see Turing awards, if not Nobel Prizes, for Peter Shor, Umesh Vazirani and others." What if someone classically breaks RSA and Diffie-Hellman or Discrete Logarithm protocols?
ReplyDeleteThen Turing awards for them too :P.
ReplyDeletelol.... i meant what if someone classically breaks RSA and Diffie-Hellman or Discrete Logarithm protocols? who gets Nobel or Turing? Technically classical breaking is application of classical physics to humanity if Shor's quantum breaking is application of quantum mechanics to humanity. So if there is ground for pessimism in delivering Nobel to classical breaking there should be grounds for pessimism in delivering Nobel to quantum breaking by Shor.
ReplyDeleteJust a year ago you were predicting "quantum winter". Why such enthusiasm, when quantum computing, unlike quantum information, has not progressed in practice?
ReplyDeleteBut Shor wouldn't be getting a Nobel for breaking RSA, he'd be getting a Nobel for noticing that Fourier transforms (which can do factoring) can be done real zippy fast by (then hypothetical) quantum computers.
ReplyDeleteIn some sense, that's a result in _Physics_ (what quantum entanglement means and can do) as much as it is in Computer Science.
I'm not fond of the hype around quantum computing, but figuring out if it can do what's claimed has to be scientifically and philosophically and intellectually significant.
That was someone else's work entirely
ReplyDeleteWhose work is that QFFT is fast on a QM? Wiki gives no leads except it points to Coppersmith's 2002 paper (I think it might be already known the importance of QFFT at that point. Surely philosophically it makes no sense to give Nobel for Shor's algorithm and if given then it should be the case for so many authors of so many classical algorithms which 'technically relies on classical physics'.
ReplyDeleteWhy are people skeptical of technological trends that aren’t available as consumer products? Moore’s law is great but you can laugh at fusion researchers and quantum computing researchers. See https://royalsocietypublishing.org/view-large/figure/15382458/rsta20170446f09.tif and https://francoismarieleregent.xyz/awesome-quantum-computing-experiments/
ReplyDelete