Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

2025 Turing award given for quantum information science

awards.acm.org

Post reply on HN
Print view View original

11–20 of 50 posts

Re: 2025 Turing award given for quantum information science

#11

Post by aleph_minus_one »

spot5010 wrote: post #9

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…

> 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

Re: 2025 Turing award given for quantum information science

#13

Post by shorden »

bawolff wrote: post #5

> 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…

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).

Re: 2025 Turing award given for quantum information science

#17

Post by Joel_Mckay »

DrNosferatu wrote: post #6

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

Re: 2025 Turing award given for quantum information science

#18

Post by dogtimeimmortal »

aleph_minus_one wrote: post #11
spot5010 wrote: post #9

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…

> 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

Re: 2025 Turing award given for quantum information science

#20

Post by matthewdgreen »

I don't want to take anything away from Bennett and Brassard, but I'd like someone to spare a word for poor Stephen Wiesner, who invented the earliest quantum information-distribution protocols as far back as the 1960s and published them before Bennett and Brassard. He also invented Oblivious Transfer (OT) which is required for multi-party computation -- although his was a quantum protocol that demonstrated some of the ideas behind QKD, not the classical protocol we call OT today [1].* Weisner was an inspiration for Bennett and Brassard, who then realized more useful systems.

While obviously this takes nothing away from BB's many later contributions (and they have extensively credited him), it's just a reminder of the randomness that goes with scientific credit. Since my PhD thesis was on OT, I like to remind people of Wiesner. He deserves a lot more credit than he gets!

* I suppose if you're a real theoretician, since OT implies MPC and MPC implies all cryptography, then perhaps Wiesner's OT implies everything that BB did subsequently. I'm not sure any of that is true (and I've since checked with an LLM and there are some no-go theorems from the 1990s that block it, so that's super interesting.)

[1] https://dl.acm.org/doi/10.1145/1008908.1008920

Post reply on HN