Here’s a 53-minute podcast that I recorded this afternoon with a high school student named Micah Zarin, and which ended up covering …[checks notes] … consciousness, free will, brain uploading, the Church-Turing Thesis, AI, quantum mechanics and its various interpretations, quantum gravity, quantum computing, and the discreteness or continuity of the laws of physics. I strongly recommend 2x speed as usual.
QIP’2026, the world’s premier quantum computing conference, is happening right now in Riga, Latvia, locally organized by a team headed by the great Andris Ambainis, who I’ve known since 1999 and who’s played a bigger role in my career than almost anyone else. I’m extremely sorry not to be there, despite what I understand to be the bitter cold. Family and teaching obligations mean that I jet around the world so much less than I used to. But many of my students and colleagues are there, and I’ll plan a blog post on news from QIP next week.
Greg Burnham of Epoch AI tells me that Epoch has released a list of AI-for-math challenge problems—i.e., open math problems that are below the level of P vs. NP and the Riemann Hypothesis but still of very serious research interest, and that they’re putting forward as worthy targets right now for trying to solve with AI assistance. A few examples that should be familiar to some Shtetl-Optimized readers: degree vs. sensitivity of Boolean functions, improving the constant in the exponent of the General Number Field Sieve, giving an algorithm to test whether a knot has unknotting number of 1, and extending Apéry’s proof of the irrationality of ζ(3) to other constants. Notably, for each problem, alongside a beautifully written description by a (human) expert, they also show you what the state-of-the-art models were able to do on that problem when they tried.
There’s been a major advance in understanding constant-depth quantum circuits, by my former PhD student Daniel Grier (now a professor at UCSD), along with his PhD student Jackson Morris and Kewen Wu of IAS. Namely, they show that any function computable in TC0 (constant-depth, polynomial-size classical circuits with threshold gates) is also computable in QAC0 (constant-depth quantum circuits with 1-qubit and generalized Toffoli gates), as long as you provide many copies of the input. Two examples of such TC0 functions, which we therefore now know to be in QAC0 given many copies of the input, are Parity and Majority. It’s been a central open problem of quantum complexity theory for a quarter-century to prove that Parity is not in QAC0, complementing the celebrated result from the 1980s that Parity is not in classical AC0 (a constant-depth circuit class that, for all we know, might be incomparable with QAC0). It’s known that showing Parity∉QAC0 is equivalent to showing that QAC0 can’t implement the “fanout” function, which makes many copies of an input bit. To say that we’ve gained a new understanding of why this problem is so hard would be an understatement.
You can use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations.
Comment Policies:
After two decades of mostly-open comments, in July 2024 Shtetl-Optimized transitioned to the following policy:
All comments are treated, by default, as personal missives to me, Scott Aaronson---with no expectation either that they'll appear on the blog or that I'll reply to them.
At my leisure and discretion, and in consultation with the Shtetl-Optimized Committee of Guardians, I'll put on the blog a curated selection of comments that I judge to be particularly interesting or to move the topic forward, and I'll do my best to answer those. But it will be more like Letters to the Editor. Anyone who feels unjustly censored is welcome to the rest of the Internet.
To the many who've asked me for this over the years, you're welcome!
Follow