Ryan O'Donnell

I'm releasing a series of videos called "Quantum Computer Programming in 100 Easy Lessons". youtube.com/playlist?list=… It will cover the 'usual' content (...CHSH, Grover, Factoring), but with some expositional innovations that I *hope* will make it easier for beginners.

@SebastienBubeck That said, cool find Paata!

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

I guess it's now every day until the end of time

New w/ Meghal Gupta, William He, @BooleanAnalysis arxiv.org/abs/2508.09422 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)

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

@BooleanAnalysis @AlgoSvensson What is that complex analysis problem?

In my undergraduate algorithms class: The free version of ChatGPT scored 26 out of 36 in midterm 1 while the class median was 20. The highest was 36. ChatGPT did not do well where the question required understanding a figure in the process of designing an algorithm. In midterm 2, ChatGPT scored 32 out of 36. The median was 19. The highest was 36. The class has about 500 students. In the final, ChatGPT scored 98 out of 108. Looking forward to see how the class average/median turns out to be in the final. To be noted: The questions are freshly prepared, no run-off-the-mill coding questions, require reasoning and algorithmic thinking. The questions are not super hard and I expect top students (1% of the class) to get full marks.

@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: cs.cmu.edu/~odonnell/pape…

@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...?

@B1ar2n3a Deepseek solved all our questions in the Master Algorithms exam and OpenAI o1 solved all but one. I found those models to be significantly better than the non-reasoning ones for these tasks.

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

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

These days I log into this cursed site, within 30 secs see something that gets me really annoyed, and log off. This one is the winner today.

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

@BooleanAnalysis @singerng_ is there a zoom link or possibly recording?😅 would love to listen!

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. toc.csail.mit.edu/node/1671 Besides coauthor @singerng_, here's the cast of characters:

@dsivakumar @thegautamkamath @SimonsInstitute @Tim_Roughgarden Really hooked on Gil Cohen these days: @GilCohen82" target="_blank" rel="nofollow noopener">youtube.com/@GilCohen82 His Free Probability lectures were so good; really looking forward to the Algebraic Geometry Codes ones.

Name a better source for high-quality technical CS content than the @SimonsInstitute YouTube channel. I'll wait. Everyone in TCS already knows this. But for the ML folks, this year has a program on LLMs (simons.berkeley.edu/programs/speci…), see, e.g., this playlist youtube.com/playlist?list=…

@LongFormMath I don't know how to sell this any better than to say this is an extremely enjoyable video about Math + Halloween: youtube.com/watch?v=JlXUiq… So good!

Math 🤝 Halloween

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!🙏

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

@AlexKontorovich One issue is that students may not ask questions if they know they're being recorded. Another, that they may not attend if they know they can watch it later.

Had an interesting discussion offline about whether posting all my lectures to YouTube for free diminishes the value of the experience for students paying tuition at Rutgers (or this semester, Princeton). I claim it does not. Those students are paying for the opportunity to attend lectures live, ask questions in real-time, and engage with their professor during office hours and elsewhere outside of class. In fact, I would argue that recording and sharing lectures enhances the experience for paying students—they can review the material any time to study. It also has the potential added benefit to the broader community by providing free access to the same content. I’m curious to hear what you think?

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

@BooleanAnalysis ... could have done Grover first, then QFT, and simply put quantum counting in the QFT chapter as an application. I don't recall seriously considering that - think I was too stuck on it having to go in the search chapter

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.

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 :-) youtube.com/playlist?list=…

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. cmsa.fas.harvard.edu/event/freedman…

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

@BooleanAnalysis Curiosity question -- In a previous iteration, you also did Grover after factoring, no? cs.cmu.edu/~odonnell/quan…

@MHop_Theory Let this be a lesson to students out there: Yes, people may well read your actual PhD thesis document! :-) Thanks Max!

Thanks Tom :) -- this paper was inspired by an elegant proof of hypercontractivity due to Yu Zhao and @BooleanAnalysis appearing in Yu's PhD thesis. My hope is the techniques will eventually extend to weak HDX and beyond simplicial complexes -- still much to be done!