Ryan O'Donnell

Videos:

[Ryan O'Donnell @BooleanAnalysis]

I'm releasing a series of videos called "Quantum Computer Programming in 100 Easy Lessons".

https://t.co/lfKXwEIHWU

It will cover the 'usual' content (...CHSH, Grover, Factoring), but with some expositional innovations that I *hope* will make it easier for beginners.

[Ryan O'Donnell @BooleanAnalysis]

FOCS 2026 Test of Time call for nominations is out:
https://t.co/yXzpjMii1X

Please submit your nominations! More info on the award here:
https://t.co/L7guxegDUb

and here's DBLP links for FOCS '16, '06, '96:
https://t.co/sDsJz4rrmW
https://t.co/2RARbtx09Z
https://t.co/aSS1vQaiV6

[Ryan O'Donnell @BooleanAnalysis]

@SebastienBubeck That said, cool find Paata!

[Ryan O'Donnell @BooleanAnalysis]

@SebastienBubeck To be fair, many people (e.g. Sivakanth Gopi) gave a simple n=5 counterexample to the similar 'Majority Is Least Stable' problem 10+ years ago...

[Noah Singer @singerng_]

New w/ Meghal Gupta, William He, @BooleanAnalysis

https://t.co/sUjeqEkBCK

We give a quadratically faster classical algo for noisy planted kXOR (k > large const), dispelling (for now) claimed quartic speedup for quantum algos. 🧵 (1/10)

[Ryan O'Donnell @BooleanAnalysis]

@B1ar2n3a @AlgoSvensson Here's screencaps of excerpts of the other one...

[Ryan O'Donnell @BooleanAnalysis]

@B1ar2n3a @AlgoSvensson Note that the answer is correct, but it has never given me a non-nonsensical proof. The proof always looks good until the key moment... A correct proof is the second paragraph of Theorem 4.1 here: https://t.co/zjzuB8wt8I

[Ryan O'Donnell @BooleanAnalysis]

@AlgoSvensson @B1ar2n3a Am I the only one who's no good at this? I tried to get the $20 o3-mini-high to solve an elementary complex analysis problem and it gave nonsense despite huge hints. (On another recent attempt it insisted that 0<=1<=1<=1 is false.) What am I doing wrong...?

[Ryan O'Donnell @BooleanAnalysis]

@mraginsky @thegautamkamath Looking forward to it, as Yihong's online notes are outstanding!

[Ryan O'Donnell @BooleanAnalysis]

@thesasho I know it's a trap, but I still can't help but point out: he proved Gödel's 2nd Incompleteness theorem independently, but let Gödel have it.

[Ryan O'Donnell @BooleanAnalysis]

@ZeyiAndyLiu @singerng_ Not sure. I'll try to make it into a YouTube video at some point, though...

[Ryan O'Donnell @BooleanAnalysis]

In case you're in Cambridge, MA on Tue. Dec. 10, I'll give a talk at 4pm (MIT 32-G449) about coboundary expansion in high-dimensional expanders.

It's kind of about group theory, though.

https://t.co/nLTm5kqfXl

Besides coauthor @singerng_, here's the cast of characters:

[Ryan O'Donnell @BooleanAnalysis]

@dsivakumar @thegautamkamath @SimonsInstitute @Tim_Roughgarden Really hooked on Gil Cohen these days: https://t.co/gwmKez6rkn
His Free Probability lectures were so good; really looking forward to the Algebraic Geometry Codes ones.

[Ryan O'Donnell @BooleanAnalysis]

@LongFormMath I don't know how to sell this any better than to say this is an extremely enjoyable video about Math + Halloween: https://t.co/fcgkghJV8E

So good!

[Ryan O'Donnell @BooleanAnalysis]

Student I know wants to apply for a PhD program doing quantum computing. But she also wants to be in the *math* department.

My brain couldn't do the lookup "QC person but in Math dept." Any suggestions for universities having such a person? Diverse suggestions (by DM) welcome!🙏

[Ryan O'Donnell @BooleanAnalysis]

@kjoshanssen @AlexKontorovich This is a fair point! It's why I now edit out student questions (replacing them with subtitles).

[Ryan O'Donnell @BooleanAnalysis]

After doing quantum counting by Grover+Binary Search, I found it natural also to do Phase Estimation by Binary Search plus the Hadamard Test. It felt less "magical" than doing it with QFT (even if maybe it's sort of the same thing in the end).

(The you also have the option of doing Factoring via Phase Estimation, rather than via QFT...)

[Ryan O'Donnell @BooleanAnalysis]

Final quantum course tidbit #10: In the course, we do Grover's algorithm (i.e., SAT in (√2)ⁿ quantum time) before doing the Factoring algorithm.

Always seems funny to me that most courses do them in the other order. (Why is this? To follow the historical order?)

Not only is Grover much easier than Factoring, there's a straight through-line:
1. Distinguishing two 1-qubit states.
2. Distinguishing two 1-qubit rotations (or reflections).
3. Elitzur-Vaidman Bomb.
4. Grover.
5. Grover when you don't know the fraction of satisfying assignments, by binary search.
6. Rotation (Phase) Estimation for 1-qubit rotations.
7. Very high-precision 1-qubit Rotation Estimation, if you can do any power of the rotation efficiently.
8. General Rotation Estimation when you don't know the plane of rotation (i.e. Phase Estimation with an input eigenvector).
9. Applying Rotation Estimation to the permutation induced by "multiply by B, mod N".
10. Factoring N.

[Ryan O'Donnell @BooleanAnalysis]

I just posted the 100th and final video in my YouTube course, "Quantum Computer Programming in 100 Easy Lessons".

If you're interested in learning quantum computing, and you have some 100 consecutive days with a half-hour free, maybe check it out :-)

https://t.co/lfKXwEIHWU

[Ryan O'Donnell @BooleanAnalysis]

In case you're in the Boston area, I'll talk about "Quartic quantum speedups for planted inference" tomorrow (Sep. 13) at Harvard at 4pm.

This is at the Freedman CSMA Seminar. https://t.co/qOemh9Z7EZ

[Ryan O'Donnell @BooleanAnalysis]

@diveshaggarwal Yes, I was kind of following how other people did it :)
But then I came to feel Grover-first was better.