As a young grad student, I remember going to a talk by Bennett where he explained how a Quantum Computer allows manipulation in a 2^N dimensional hilbert space, while the outputs measurements give you only N bits of information. The trick is to somehow encode the result in the final N bits.
I felt this was a much better layman explanation of what a quantum computer does than simply saying a quantum computer runs all possible paths in parallel.
> I felt this was a much better layman explanation of what a quantum computer does than simply saying a quantum computer runs all possible paths in parallel.
ACM has named Charles H. Bennett and Gilles Brassard as the recipients of the 2025 ACM A.M. Turing Award for their essential role in establishing the foundations of quantum information science and transforming secure communication and computing.
* An accessible news excerpt via CNN science [1]
Years before emails, internet banking, cloud servers and cryptocurrency wallets, two scientists devised a way to keep secrets perfectly safe and indecipherable to eavesdropping outsiders.
Their 1984 work depended on the hidden, counterintuitive world of quantum physics, which governs the way the world works at the smallest, subatomic scale, rather than complex but theoretically breakable mathematical codes to secure data.
The insights of Charles Bennett, an American physicist who is a fellow at IBM Research, and Gilles Brassard, a Canadian computer scientist and professor at the University of Montreal, have since transformed cryptography and computing. The pair received the A.M. Turing Award on Wednesday for their groundbreaking work on quantum key cryptography.
> Bennett and Brassard, with Ethan Bernstein and Umesh Vazirani, showed that in black-box setting, quantum computers would require big-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.
This is mentioned almost as a footnote, but to (layman) me seems much more important than QKD, especially from a comp sci perspective instead of a physics perspective.
Worth noting that this is a bound on arbitrary search, but there exist some problems with structure (e.g. integer factorization) for which quantum algorithms are exponentially faster than known classical algorithms (a problem believed to be in NP and BQP but not P).
The quantum computers are not quite large enough to search at an `n` such that O(n)` is not viable but `O(sqrt(n))` is, that's where there's money to be made, especially if viability is defined by small time horizons. So it's a footnote for the future.
It can, but it isn't largely because the classical solutions solve the problem better and you usually have to resort to classical solutions to solve MITM anyways afaik. However my point is less about practicality and more QKD seems more like a physics or engineering thing and not a computer science thing.
After all, this is supposed to be a computer science prize not a make money prize, so which is more sellable should be besides the point.
Really curious, not a critique: apart from the idea of the possibility of intrusion detection due to the quantum nature of the communication link, what is special about the protocol that is mentioned?
As a young grad student, I remember going to a talk by Bennett where he explained how a Quantum Computer allows manipulation in a 2^N dimensional hilbert space, while the outputs measurements give you only N bits of information. The trick is to somehow encode the result in the final N bits.
I felt this was a much better layman explanation of what a quantum computer does than simply saying a quantum computer runs all possible paths in parallel.
> I felt this was a much better layman explanation of what a quantum computer does than simply saying a quantum computer runs all possible paths in parallel.
Relevant concerning your point:
> "The Talk"
> https://www.smbc-comics.com/comic/the-talk-3
Thanks for this! I guess i need to read up on Hilbert Space.
...and Shor's Algorithm
* From the announcement [0]:
ACM has named Charles H. Bennett and Gilles Brassard as the recipients of the 2025 ACM A.M. Turing Award for their essential role in establishing the foundations of quantum information science and transforming secure communication and computing.
* An accessible news excerpt via CNN science [1]
Years before emails, internet banking, cloud servers and cryptocurrency wallets, two scientists devised a way to keep secrets perfectly safe and indecipherable to eavesdropping outsiders.
Their 1984 work depended on the hidden, counterintuitive world of quantum physics, which governs the way the world works at the smallest, subatomic scale, rather than complex but theoretically breakable mathematical codes to secure data.
The insights of Charles Bennett, an American physicist who is a fellow at IBM Research, and Gilles Brassard, a Canadian computer scientist and professor at the University of Montreal, have since transformed cryptography and computing. The pair received the A.M. Turing Award on Wednesday for their groundbreaking work on quantum key cryptography.
[0] https://www.acm.org/media-center/2026/march/turing-award-202...
[1] https://edition.cnn.com/2026/03/18/science/quantum-key-crypt...
> Bennett and Brassard, with Ethan Bernstein and Umesh Vazirani, showed that in black-box setting, quantum computers would require big-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.
This is mentioned almost as a footnote, but to (layman) me seems much more important than QKD, especially from a comp sci perspective instead of a physics perspective.
Worth noting that this is a bound on arbitrary search, but there exist some problems with structure (e.g. integer factorization) for which quantum algorithms are exponentially faster than known classical algorithms (a problem believed to be in NP and BQP but not P).
QKD can be sold today.
The quantum computers are not quite large enough to search at an `n` such that O(n)` is not viable but `O(sqrt(n))` is, that's where there's money to be made, especially if viability is defined by small time horizons. So it's a footnote for the future.
> QKD can be sold today.
It can, but it isn't largely because the classical solutions solve the problem better and you usually have to resort to classical solutions to solve MITM anyways afaik. However my point is less about practicality and more QKD seems more like a physics or engineering thing and not a computer science thing.
After all, this is supposed to be a computer science prize not a make money prize, so which is more sellable should be besides the point.
The math might be beautiful, but I'm very skeptical - practical - quantum computers will ever deliver their promise.
Forever is a long time, but I agree people that assert reality is the model are almost always incorrect eventually.
There is some interesting work being done, but it will never match the excessive hype. =3
"The Genius of Computing with Light"
https://www.youtube.com/watch?v=rbxcd9gaims
Coincidentally, the same people also recently received the Science Fiction Award 2025!
Source?
I suspect the parent considers quantum computing science fiction.
That's 2 Turing award for the Université de Montréal in 6 years. Sadly, I never had those 2 teachers during my years there!
I did see Gilles' lunch talks though, it was really insightful!
Really curious, not a critique: apart from the idea of the possibility of intrusion detection due to the quantum nature of the communication link, what is special about the protocol that is mentioned?
Well deserved and much needed recognition in quantum key cryptography, for once not a single mention of "AI" anywhere.
Congratulations to Charles Bennett and Gilles Brassard.