Podcasts!
Update (Dec. 9): For those who still haven’t gotten enough, check out a 1-hour Zoom panel discussion about quantum algorithms, featuring yours truly along with my distinguished colleagues Eddie Farhi, Aram Harrow, and Andrew Childs, moderated by Barry Sanders, as part of the QTML’2024 conference held in Melbourne (although, it being Thanksgiving week, none of the four panelists were actually there in person). Part of the panel devolves into a long debate between me and Eddie about how interesting quantum algorithms are if they don’t achieve speedups over classical algorithms, and whether some quantum algorithms papers mislead people by not clearly addressing the speedup question (you get one guess as to which side I took). I resolved going in to keep my comments as civil and polite as possible—you can judge for yourself how well I succeeded! Thanks very much to Barry and the other QTML organizers for making this happen.
Do you like watching me spout about AI alignment, watermarking, my time at OpenAI, the P versus NP problem, quantum computing, consciousness, Penrose’s views on physics and uncomputability, university culture, wokeness, free speech, my academic trajectory, and much more, despite my slightly spastic demeanor and my many verbal infelicities? Then holy crap are you in luck today! Here’s 2.5 hours of me talking to former professional poker players (and now wonderful Austin-based friends) Liv Boeree and her husband Igor Kurganov about all of those topics. (Or 1.25 hours if you watch at 2x speed, as I strongly recommend.)
But that’s not all! Here I am talking to Harvard’s Hrvoje Kukina, in a much shorter (45-minute) podcast focused on quantum computing, cosmological bounds on information processing, and the idea of the universe as a computer:
Last but not least, here I am in an hour-long podcast (this one audio-only) with longtime friend Kelly Weinersmith and her co-host Daniel Whiteson, talking about quantum computing.
Enjoy!
Follow
Comment #1 December 4th, 2024 at 3:50 pm
Hi Scott, I’ve listened to your interviews before, and I found them interesting and informative! Could you also provide link to the first two podcasts you mentioned?
I can only see the link to the last podcast.
Comment #2 December 4th, 2024 at 4:02 pm
Dikshant #1: Just click on the videos themselves!! Does that not work?
Comment #3 December 5th, 2024 at 3:13 am
Thanks Scott, I didn’t see the link to the videos previously. I can see the videos now, thanks!
Comment #4 December 5th, 2024 at 1:28 pm
This is great, will listen to the podcasts when I have the time!
Also, now I know that Kelly Weinersmith has a podcast, which I somehow didn’t know before. I’m a huge fan of Zach and of their books together, so this is great to know 🙂
Comment #5 December 5th, 2024 at 2:32 pm
Think of the universe as a refrigerator. After all, if I’m not mistaken, the universe is cooling down. At the same time, it is fairly obvious that the universe is not really a refrigerator. Why isn’t it just as obvious to you that the universe isn’t a computer?
Comment #6 December 5th, 2024 at 5:07 pm
Andre #5: The right question to ask is what each perspective buys you. Thinking of the universe as a thermodynamic system (the charitable version of “universe as refrigerator”) really was an incredibly fruitful lens, from Boltzmann’s time through the rise of Big Bang cosmology. The claim here is precisely that thinking of the universe as an information processing system (again, the charitable version of the universe as literally, like, an iPad or MacBook or whatever) is a similarly fruitful lens in our own time.
Comment #7 December 5th, 2024 at 9:07 pm
One more question if you have you’re willing 🙂
Year that you think AI will be better than you are at coming up with problems and proving theorems (the main theorems that go into your papers for example)
Comment #8 December 6th, 2024 at 12:11 am
Opt #7: Sorry, but I’m feeling burned out from “when do you expect AI to do X?” questions—everyone’s just guessing, no one has any intellectually meaty principles on which to base such predictions, and the only contribution I can make is to point that out.
Comment #9 December 6th, 2024 at 6:44 pm
Any thoughts on all the recent rumors twirling around that the latest efforts to massively scale up LLMs are showing a dramatic diminishing return in performance gains?
If true, I wouldn’t be surprised.
As I’ve written before, the scaling up hypothesis is like feeding to an LLM all the books and scientific papers prior to Einstein discoveries on relative and general relativity, and expect that backpropagation on all the text of those papers would somehow imprint somewhere in the model various plausible theories, including Einstein’s … or if it doesn’t, it’s just a matter of feeding it more papers and books on pre-relativity physics and putting more parameters in the model. Always seems unlikely to me.
I’m not saying that LLM aren’t wildly successful, it’s like having a smart assistant who does the best Google search for you, instantly, and also is able to interpolate almost perfectly whatever answer can be interpolated between previously asked questions that came up over and over again.
But I’m sure LLMs will be a part of AGIs. Ironically, the capability of LLMs to “hallucinate” will be a key ingredient in making progress towards AGIs. In other words I expect that some subsystems of AGIs will be nothing but hallucination machines, finding connections between distant internal models that most likely aren’t connected 99.999% of the time, but once a while they will indeed find some connection. And then more logical subsystems on top of those will “test” those “dreams”. This is what humans call “imagination” and anyone who has a tendency to obsess over hard problems for days and days will tell you that a solution eventually often just appeared magically while they were at the edge of sleep or in the shower.
Comment #10 December 6th, 2024 at 6:57 pm
Scott #6
it’s funny you mention this.
Because today I was remembering the modern argument against the Maxwell demon being able to separate back a gas, against the second law of thermodynamics, being that recording the positions of all the particles will eventually force it to erase its memory, and that contributes to entropy, etc.
And I remembered that Feynman talked in his 1960s lectures about Maxwell demon, so I was curious to find out again how he dealt with this (he couldn’t have been mentioning bits of memory being erased)… and his explanation was that the demon had to look at the particles coming near the separation, and that looking involves absorbing photons, and so the demon would slowly start to heat up as he observes more and more particles, enough so that eventually he wouldn’t be able to “see” correctly (pretty much the same type of analysis he does with the ratchet for a perpetual motion machine).
Comment #11 December 7th, 2024 at 12:11 am
Not on the topic of the podcasts, but about the “peaked circuits” proposal for quantum supremacy experiments. I was looking at SA’s slides “The Future of Quantum Supremacy Experiments”, in particular the “New Open Question” slide. Comparing the circuits U -> U^(-1) and an obfuscated version looks vaguely (very vaguely!) reminiscent of trying to determine whether a knot is the unknot. The equational theory of CHMPV gives a set of somethings that look vaguely (very vaguely!) like Reidemeister moves. This is worth nothing, but I thought it was an interesting superficial resemblance.
Comment #12 December 7th, 2024 at 6:19 am
Scott #6
First of all, it is amazing that nature provides these different lenses(thermodynamic, information processing etc) to describe the Universe in a consistent fashion, but also these alternate descriptions have some overlaps among them. Which leads us to believe that there is possibly an underlying more general way to describe it, but has been more elusive to find. Maybe our current mathematics is not developed enough or its become too complicated (string theory) for us to comprehend ?
Comment #13 December 7th, 2024 at 6:45 am
Hi Scott, I’m sorry for this post being completely unrelated to your podcast, but I suppose you get a ton of requests for advice from grad students. Well, here’s one from an undergrad:
I’m getting a bachelor’s in physics but I’ve recently discovered that I don’t really like physics all that much – complexity theory seems a lot more interesting. What would be the best way to pivot to complexity theory entirely? How do I find low-hanging fruit that a lowly undergrad like myself could possibly work on? Quantum complexity seems like the natural way to go, do you have any recommendations for papers or surveys that a beginner should read?
What math courses would be the most useful? Ring theory seems important. Fields? Representation theory? Measure theory?
Also, for what it’s worth, I’ve been studying the book by Arora and Barak for the past couple of months and I just grokked the IP = PSPACE proof (now my favorite math proof) two weeks ago. I know I have to do more than solely studying from books, I just don’t know what.
Sorry for the offtopic posting again, there aren’t any complexity theorists at my university.
Comment #14 December 7th, 2024 at 9:39 am
Ethan Bernstein #13: Many, many people with physics backgrounds have gotten into quantum complexity theory — Stephen Jordan, Aram Harrow, even Ed Farhi and John Preskill. It’s a well-trodden path. Take all the math you can, especially discrete probability, abstract algebra, combinatorics. Take CS, including classical algorithms and complexity (and computability, and randomized algorithms, and computational learning theory, whatever else is offered). Read the best books for classical complexity theory: Papadimitriou, Arora-Barak, Mertens-Moore, and so on. For QC, try the Nielsen-Chuang book, or lecture notes by Umesh Vazirani or Ronald de Wolf or yours truly, or of course Quantum Computing Since Democritus.
Comment #15 December 7th, 2024 at 10:26 am
Scott #14: Thank you for replying :). Unfortunately there are very few CS courses offered here and none of what you mentioned besides the introductory algorithms course are in the list. I have already read Nielsen and Chuang (except for the last three chapters), and I have also looked at Ronald de Wolf’s lecture notes.
My primary issue is that I really don’t have any clue what to do after reading a book. The natural progression appears to be reading papers, but what papers? In what subfield? Is any of the reading I do going to be relevant a year from now? I can’t shake the feeling that I’m sinking months of my time into learning something that nobody is going to care about in the end because I haven’t actually _done_ anything.
Thanks for the combinatorics mention, that wasn’t on my mind.
Comment #16 December 7th, 2024 at 1:18 pm
Ethan Bernstein #15: It sounds like you’re already well along the path then. When can you apply to PhD programs—this fall (better hurry)? Next fall?
Right now, nothing stops you from scanning the quant-ph arXiv and ECCC every day, flagging any papers that resonate with you, and seeing if they have any open problems (either stated or unstated) that you’d like to work on. Small problems are 100% fine for a start.
Comment #17 December 7th, 2024 at 2:55 pm
Scott #16: I’ll have to start applying to PhD programs next fall. Didn’t know about the ECCC, will keep an eye out on it.
Comment #18 December 7th, 2024 at 3:23 pm
Hi Scott. Say I want to figure out if a future quantum computer will provide a speed-up for a particular problem. Is there a simple computational problem P such that I can think of a quantum computer as like a classical computer equipped with an oracle for P? So then the question becomes how much of my problem can I encode as an instance of P.
Comment #19 December 7th, 2024 at 6:09 pm
Martin Mertens #18: Yes, you could simply take P to be any “BQP-complete promise problem” (google it). Unfortunately, the canonical BQP-complete promise problem is simply “given as input a quantum circuit, estimate that circuit’s acceptance probability”! Which gives more of a tautological restatement of the question you asked me, than a new insight into that question. There are more interesting BQP-complete problems, like “additively estimate the Jones polynomial of a given knot at a root of unity.” Even there, though, figuring out how to reduce the problems you care about to those problems, will usually be just as hard as simply designing quantum algorithms outright. Ultimately, if there were a simple answer to the question of “which problems admit exponential quantum speedup and which don’t,” it wouldn’t have been a whole huge research field for the past 30 years! 😀
Comment #20 December 10th, 2024 at 1:00 am
Hey Scott,
Could you please write something about Google’s recent announcement on their quantum chip Willow? I am honestly tired of scrolling through 100s of posts on Linkedin hyping this without an iota of understanding what it’s all about.
Thanks.
Comment #21 December 10th, 2024 at 10:07 am
Hi Scott,
following up on Sandeep #20 request, this is the Google paper (it’s more interesting than the blog post IMO) https://www.nature.com/articles/s41586-024-08449-y Also, this comment on HN seems interesting https://news.ycombinator.com/item?id=42368491
Comment #22 December 11th, 2024 at 1:22 pm
Sandeep
Yea, without any context/details it’s all pretty trivial:
A dog turd is a quantum system, and, if you throw it at a wall, the end result you get (i.e. the state of the dog turd splattered on the wall) is very efficiently computed by the dog turd itself, as a simulation of a quantum system.
You can make the dog turd as “programmable” as you like by imposing/choosing various parameters like the number of nuts it contain (N).
And it would take a zillion years for a digital computer to simulate it just as well as the dog turd itself can do it.
Now, if the final state of the dog turd were to match some “useful” computation, like factoring a number, that’d be really impressive.
Comment #23 December 11th, 2024 at 4:45 pm
This CS professor (Alan Woodward) interviewed by the BBC basically makes the same point I’m making (just more elegantly than using dog turds)
“I’m not sure the comparison with a super computer is a valid one, because the algorithm they’ve implemented is really all about… it relies on quantum physics… and so the first thing the super computer would have to do is simulate the quantum computer, so I’m not sure it’s a fair comparison in some way”
Comment #24 December 11th, 2024 at 5:05 pm
fred #22, #23: We’ve had this exact same discussion on this blog before (albeit with flower pots rather than dog turds).
The key observation is that whatever issues make a dog turd difficult to simulate on a classical computer, none of those issues involve a tensor product of Hilbert spaces, and therefore none of them will lead to exponential scaling in the size of the turd. With Random Circuit Sampling, by contrast, we do see such exponential scaling with system size. Validating the outputs using Linear XEB lets us rule out all alternative, more turd-like explanations for the difficulty (involving chaotic dynamics, unknown initial conditions, etc etc).
Comment #25 December 12th, 2024 at 4:17 pm
Scott #24
Ok, let’s scale it back.
We’re told that the main application of QC will be to fully simulate quantum systems like all the individual bits (one by one) of possible organic chemistry going on in a dog turd at the molecular level, which would also include all the processes going on in a bacteria. Basically the pharmaceutical industry or material science (e.g. the study of supra conductors, etc) will be able to explore all sorts of complex chemistry, efficiently, by running simulations in a QC.
I wonder how many qubits would be needed to perfectly simulate processes like glycolysis as a quantum system of atoms (i.e. coming up with the actual chemistry, simulating all the atomic mechanics, without the shortcuts of chemistry):
https://en.wikipedia.org/wiki/Glycolysis
But maybe that’s already too complex to answer.
Do we know how many qubits would be able to simulate a hydrogen atom? (i.e. to come up with all the possible energy levels/configurations of the electron around the proton, etc)? This could be actually simple (I know it’s possible to compute this by hand by solving the equations, using various simplifications and math tricks)
Comment #26 December 12th, 2024 at 5:58 pm
fred #25: For simulating hydrogen, 0 qubits suffice, since we already know everything there is to know about the hydrogen atom. 🙂
That sounds facetious but there’s a serious point: any cost estimate for a simulation will be a function of what you want to learn from the simulation and also what you already know.
There’s a whole community doing detailed cost estimates for various quantum simulation problems right now — look at the company PhaseCraft for example. Long story short, a couple hundred logical qubits should already be enough for some interesting physics and chemistry, if you can do hundreds of thousands of gates on those qubits.
Comment #27 December 18th, 2024 at 8:41 pm
Hi Scott, thanks for your very interesting blog over all these years.
I guess mine is a sociological question. There is a lot of discourse online about how AI will do these amazing feats. And yet, you look at how AI is currently trained, ultimately it’s just gradient descent. In other words, greedy local search. (In the space of algorithms, if you will.)
Now, everything we know about computer science tells us that greedy local search can’t solve most problems. It can’t come even close to finding various optima except in very restricted settings.
So, the overwhelming prior should be that greedy local search, which can’t even solve Knapsack, will probably not SOLVE INTELLIGENCE. This is vague but I posit that, for any reasonable meaning of these terms, the claim holds.
And yet, I can’t really find any complexity theorists “shouting this from the rooftops”, as they say. The purpose of the entire discipline is to tell us what computers can’t do. Now, the world is aflame with people claiming computers will do wildly improbable things. Shouldn’t complexity theorists be coming forward to educate the public?
Comment #28 December 18th, 2024 at 9:16 pm
Oscar #27: As a complexity theorist, I can tell you that gradient descent doesn’t suffice to solve NP-complete problems in polynomial time in the worst case.
I can’t tell you that it doesn’t suffice to find weights for a giant neural net that are good enough to outperform humans at pretty much everything humans do. For all I know it does suffice for that. Or if it doesn’t, then it’s not for any reason currently known to complexity theory.
Incidentally, I told people the same thing decades ago, long before the deep learning revolution put an exclamation point on it. Does the distinction make sense?
Comment #29 December 19th, 2024 at 1:01 pm
Thanks Scott for taking the time to reply. Yes, I understand the distinction you’re making. I should say that I used to be in complexity theory myself, before getting a job in industry.
Of course none of us can *prove* that gradient descent won’t “solve intelligence” (for any reasonable definition we can come up for that). Last I checked, we couldn’t even prove that AC0[6] does not solve NP-complete problems!
But I think our experience in the field gives us strong priors that braindead greedy local search in the space of neural net algorithms will not yield something that can do complex mathematical reasoning. (Much less become superintelligent, solve all physics, perfectly manipulate humans, and other such Yudkowskyan fantasies.) Greedy local search can’t even make efficient change from a set of coin denominations! It can’t solve 0/1 knapsack, or any number of simple problems from programming competitions.
So I think it is a mistake to say: since we can’t PROVE anything, we must be SILENT on this. No, we have knowledge and intuitions that are informative, and which the public lacks.
To put it another way: forget gradient descent. Imagine ML models were trained randomly, i.e. on every training step, all weights are re-initialized completely at random, the loss is calculated, and after N steps of this, we return the weights with the lowest loss. Can complexity theorists prove that THIS will not surpass humans at various tasks? No, they probably can’t PROVE it. But it would be silly to have no OPINION on it.
Comment #30 December 19th, 2024 at 1:32 pm
Oscar #29: But we’re no longer in an empirical vacuum here. We have, e.g., the GPT o1 model and AlphaProof, which can solve math olympiad problems as well as the top few hundred high school students in the US, ace undergrad physics exams, etc. The problems weren’t in the training set, and the solutions would often be called creative, clever, etc. if a human had given them. Actual results speak much more loudly to me than a-priori opinions about the weaknesses of gradient descent that you or anyone else might have.
Comment #31 December 21st, 2024 at 5:00 pm
We describe Shakespeare not through his (fairly digital!) DNA source code but through his analogue behaviour, which was dynamically determined by his interaction with 17th century Stratford upon Avon etc. Once any digital computer programme starts interacting with its unique analogue locale, is it ever cloneable?
For example, a computer might be running a complicated simulation based on many inputs which predicts some chaotic system like the weather, sending commands to devices that seed the atmosphere or something, in order to keep a narrow range of conditions. While we could clone the digital state of the computer, we couldn’t place it the exact same stream of data (as the weather is a continuous analogue system), and it might therefore diverge and behave very differently if the fixed point it was maintaining was very particular to the environment it was designed for? The environment would be performing part of the computation which determines its future state. Does this not make computers interacting with the real world also kind of ephemeral like Shakespeare?
Comment #32 December 22nd, 2024 at 7:32 am
Oscar #27: “I guess mine is a sociological question. There is a lot of discourse online about how AI will do these amazing feats. And yet, you look at how AI is currently trained, ultimately it’s just gradient descent. In other words, greedy local search. (In the space of algorithms, if you will.)”
Now I feel bad that I haven’t commented on Luca Trevisan (1971-2024) about how his blog post series on “Online Optimization”/”Regret Bounds” has changed my perception of stochastic gradient descent and improved my understanding of multiplicative weights. Those two topics were item 4. in his initial announcement of the series:
https://lucatrevisan.wordpress.com/2019/04/17/online-optimization-for-complexity-theorists/
Here are links to all the posts in the series (Post 3 is the one which talks about gradient descent.):
https://lucatrevisan.wordpress.com/2019/04/22/online-optimization-post-0-definitions/
https://lucatrevisan.wordpress.com/2019/04/24/online-optimization-post-1-multiplicative-weights/
https://lucatrevisan.wordpress.com/2019/04/25/online-optimization-post-2-constructing-pseudorandom-sets/
https://lucatrevisan.wordpress.com/2019/05/06/online-optimization-post-3-follow-the-regularized-leader/
https://lucatrevisan.wordpress.com/2019/05/16/online-optimization-post-4-regularity-lemmas/
https://lucatrevisan.wordpress.com/2019/05/20/online-optimization-post-5-bregman-projections-and-mirror-descent/
https://lucatrevisan.wordpress.com/2021/10/20/online-optimization-post-6-the-impagliazzo-hard-core-set-lemma/
https://lucatrevisan.wordpress.com/2021/11/10/online-optimization-post-7-matrix-multiplicative-weights-update/
Scott #30: “Actual results speak much more loudly to me than a-priori opinions about the weaknesses of gradient descent that you or anyone else might have.”
You are right that results are more important than a-priory opinions. But if there is really a huge disconnect between a-priory opinions and results, then one could also take this as a hint that there might be an opportunity to discover “important” gaps in the knowledge on which those a-priority opinions were based.
Comment #33 December 28th, 2024 at 8:28 pm
Scott#30,
You would have definitely experimented more with o1. But, I honestly doubt some of the claims on its mathematical ability beyond concocting solutions to Olympiad problems using well-known strategies. Don’t mistake me, this itself is great and would put it among the top 10% at least. Posting an o1 response when asked to conjecture something in number theory:
————————————
Conjecture (Consecutive-Squares-Plus-One Prime Conjecture)
Statement. There are infinitely many integers n such that both
n^2 + 1 and (n+1)^2 + 1 are prime numbers.
In other words, this conjecture claims that prime values of n^2 + 1 not only occur infinitely often (which itself is an open question) but sometimes appear back-to-back for consecutive n. Namely, that we can find infinitely many “pairs” of consecutive squares whose increments by 1 are both prime.
————————————
A good high school kid would disprove this in a minute. To me it seems like these are great at finding needles in haystacks but quite bad in discovering needles outside the haystack.