https://scottaaronson.blog/?p=9183 Shtetl-Optimized The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel. Also, please read Zvi Mowshowitz's masterpiece on how to fix K-12 education! --------------------------------------------------------------------- << HSBC unleashes yet another "qombie": a zombie claim of quantum advantage that isn't The QMA Singularity A couple days ago, Freek Witteveen of CWI and I posted a paper to the arXiv called "Limits to black-box amplification in QMA." Let me share the abstract: We study the limitations of black-box amplification in the quantum complexity class QMA. Amplification is known to boost any inverse-polynomial gap between completeness and soundness to exponentially small error, and a recent result (Jeffery and Witteveen, 2025) shows that completeness can in fact be amplified to be doubly exponentially close to 1. We prove that this is optimal for black-box procedures: we provide a quantum oracle relative to which no QMA verification procedure using polynomial resources can achieve completeness closer to 1 than doubly exponential, or a soundness which is super-exponentially small. This is proven by using techniques from complex approximation theory, to make the oracle separation from (Aaronson, 2008), between QMA and QMA with perfect completeness, quantitative. You can also check out my PowerPoint slides here. To explain the context: QMA, or Quantum Merlin Arthur, is the canonical quantum version of NP. It's the class of all decision problems for which, if the answer is "yes," then Merlin can send Arthur a quantum witness state that causes him to accept with probability at least 2/3 (after a polynomial-time quantum computation), while if the answer is "no," then regardless of what witness Merlin sends, Arthur accepts with probability at most 1/3. Here, as usual in complexity theory, the constants 2/3 and 1/3 are just conventions, which can be replaced (for example) by 1-2^-n and 2 ^-n using amplification. A longstanding open problem about QMA--not the biggest problem, but arguably the most annoying--has been whether the 2/3 can be replaced by 1, as it can be for classical MA for example. In other words, does QMA = QMA[1], where QMA[1] is the subclass of QMA that admits protocols with "perfect completeness"? In 2008, I used real analysis to show that there's a quantum oracle relative to which QMA [?] QMA[1], which means that any proof of QMA = QMA[1] would need to use "quantumly nonrelativizing techniques" (not at all an insuperable barrier, but at least we learned something about why the problem is nontrivial). Then came a bombshell: in June, Freek Witteveen and longtime friend-of-the-blog Stacey Jeffery released a paper showing that any QMA protocol can be amplified, in a black-box manner, to have completeness error that's doubly exponentially small, 1/exp(exp(n)). They did this via a method I never would've thought of, wherein a probability of acceptance is encoded via the amplitudes of a quantum state that decrease in a geometric series. QMA, it turned out, was an old friend that still had surprises up its sleeve after a quarter-century. In August, we had Freek speak about this breakthrough by Zoom in our quantum group meeting at UT Austin. Later that day, I asked Freek whether their new protocol was the best you could hope to do with black-box techniques, or whether for example one could amplify the completeness error to be triply exponentially small, 1/exp(exp(exp (n))). About a week later, Freek and I had a full proof written down that, using black-box techniques, doubly-exponentially small completeness error is the best you can do. In other words: we showed that, when one makes my 2008 QMA [?] QMA[1] quantum oracle separation quantitative, one gets a lower bound that precisely matches Freek and Stacey's protocol. All this will, I hope, interest and excite aficianados of quantum complexity classes, while others might have very little reason to care. But here's a reason why other people might care. This is the first paper I've ever put out for which a key technical step in the proof of the main result came from AI--specifically, from GPT5-Thinking. Here was the situation: we had an NxN Hermitian matrix E(th) (where, say, N=2^n), each of whose entries was a poly(n)-degree trigonometric polynomial in a real parameter th. We needed to study the largest eigenvalue of E(th), as th varied from 0 to 1, to show that this l[max] (E(th)) couldn't start out close to 0 but then spend a long time "hanging out" ridiculously close to 1, like 1/exp(exp(exp(n))) close for example. Given a week or two to try out ideas and search the literature, I'm pretty sure that Freek and I could've solved this problem ourselves. Instead, though, I simply asked GPT5-Thinking. After five minutes, it gave me something confident, plausible-looking, and (I could tell) wrong. But rather than laughing at the silly AI like a skeptic might do, I told GPT5 how I knew it was wrong. It thought some more, apologized, and tried again, and gave me something better. So it went for a few iterations, much like interacting with a grad student or colleague. Within a half hour, it had suggested to look at the function $$ Tr[(I-E(\theta))^{-1}] = \sum_{i=1}^N \frac{1}{1-\lambda_i(\ theta)}. $$ It pointed out, correctly, that this was a rational function in th of controllable degree, that happened to encode the relevant information about how close the largest eigenvalue l[max](E(th)) is to 1. And this ... worked, as we could easily check ourselves with no AI assistance. And I mean, maybe GPT5 had seen this or a similar construction somewhere in its training data. But there's not the slightest doubt that, if a student had given it to me, I would've called it clever. Obvious with hindsight, but many such ideas are. I had tried similar problems a year ago, with the then-new GPT reasoning models, but I didn't get results that were nearly as good. Now, in September 2025, I'm here to tell you that AI has finally come for what my experience tells me is the most quintessentially human of all human intellectual activities: namely, proving oracle separations between quantum complexity classes. Right now, it almost certainly can't write the whole research paper (at least if you want it to be correct and good), but it can help you get unstuck if you otherwise know what you're doing, which you might call a sweet spot. Who knows how long this state of affairs will last? I guess I should be grateful that I have tenure. Email, RSS Follow This entry was posted on Saturday, September 27th, 2025 at 6:55 pm and is filed under Complexity, Nerd Interest, Quantum. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site. 16 Responses to "The QMA Singularity" 1. Joshua Zelinsky Says: Comment #1 September 27th, 2025 at 7:11 pm Regarding the AI bit: I had a similar experience with the GPT5-thinking on a much smaller problem. I had a Lemma already which classified all integers a and b such that b|a^2 + a +1 and a|b+1 . I wanted a version of this in the Gaussian integers with some small restrictions. After I worked it out (essentially using the proof of the first one as a template), I asked GPT5 to work it out, and I gave it a small amount of guidance. It was able to work out essentially the correct result with only a small amount of (minor) errors. I don't know if it would have been faster to have asked GPT5 first and then checked it over, but it was plausibly close. But in this case, nothing it was doing was as deeply original (or as important) as what you apparently got it to do. 2. Danylo Yakymenko Says: Comment #2 September 28th, 2025 at 1:25 am > I guess it's good that I have tenure. HA-HA-HA (laughs in a robot voice, sound version https:// www.youtube.com/watch?v=jN6_rO2rYA8) If a general model can already help you with research, then what could be achieved with models that have received gold medals on the IMO and ICPC? What could be achieved with models after they have exercised self-play with Lean? I remind that AlphaZero reached a grandmaster chess level from scratch in less than 4 hours. It seems plausible to me that, in the not-too-distant future, models could reach a grandmaster level in math in just days of self-play, given sufficient compute power. The world simply can't be the same again. 3. arch496 Says: Comment #3 September 28th, 2025 at 3:04 am There is still, it seems, a sizable impressiveness gap between reasoning mode, after going through a few rounds of "but I can tell that's not right, because x" iterations with you, making its final suggestion based on a) having seen it in training data vs b) having seen nothing similar in training data. I suppose that more experience with this version will resolve that question, but perhaps not long before capability improvements render it moot. 4. OnceMore Says: Comment #4 September 28th, 2025 at 3:43 am Scott, the formula you end up with seems really obvious to come up with if your goal is to argue about what happens if the eigenvalues of $E(\theta)$ get too close to $1$. Also, would you be okay with editing your post to not compare grad students to AI tools? It's kind of disheartening. 5. Scott Says: Comment #5 September 28th, 2025 at 7:28 am OnceMore #4: Allowing your comment through despite its snideness. For me, the non-obvious part was just that there would exist a rational function of the matrix entries, of suitable degree, that would capture the needed information about the largest eigenvalue, rather than needing to dig up results from the approximation theory literature that talked about matrix norm directly. Yes, it's obvious with hindsight (many things are!). Yes, I probably would've noticed it myself given more time or had I been younger. But frankly, I've reached a point of confidence in my career where I'm happy to tell the world that GPT5-Thinking helped us prove a lemma, it can probably help you too, and I don't care who knows. I edited "grad student" to "grad student or colleague." For now, I expect that actual grad students in math, theoretical computer science, etc. will be enormously enhanced in what they can do, if they learn to use these tools well. And when and if these tools can do everything we do better than we do it--at that point, I expect we'll all have much bigger things to worry about than the academic career ladder. I was joking about tenure. 6. Geoffrey Irving Says: Comment #6 September 28th, 2025 at 8:25 am I while ago I was doing some manual calculations involving Bottcher coordinates. I got partway through a derivation, then realised I had made a fundamental mistake and had to back up. I asked GPT-5 the same question, and delightfully it made the identical conceptual error I had made with the same erroneous result. I pointed the error out, and it immediately solved the problem the correct way. 7. Ted Says: Comment #7 September 28th, 2025 at 9:33 am OnceMore #4: I do not think that a feeling that someone else's factually accurate and informative comparison is "kind of disheartening" is a good reason for suppressing it from the public discourse. 8. Julian Says: Comment #8 September 28th, 2025 at 9:34 am I had a similar experience recently. I'm taking a CS course this semester (not my major, just an elective) and I was curious to see if it the new GPT-thinking could tackle my homework problems (only after I submitted my solutions, don't tell my ubiversity's academic honesty office ). It was a proof of a basic result about matroids. I was really surprised that it gave me a perfect answer. I've tried earlier versions of GPT before on CS assignments, and mostly got nonsense. Now, this was a pretty basic result about matroids, and there's probably a solution somewhere on math overflow or stack exchange. Perhaps it did "pre-memorize" the solution to this basic problem. Yet, the total data contained in the weights of GPT (terabytes?) is orders of magnitude less than the training data (the whole public internet, so hundreds of petabytes?) so naively it seems impossible that it's just some fraud, pre-memorizing answers to all these questions. And even though this problem is simple, if it didn't "pre-memorize" some solution on stack exchange, it's capable of some impressive reasoning about abstract mathematical objects. But, "your mileage may vary." It's totally hopeless doing proofs in mathematical physics, axiomatic quantum field theory, smooth manifolds, Lie groups. Believe me, I've tried. But maybe a future GPT-8 will be able to solve my Lie Groups or QFT problem sets. I have a question for you, Scott. You're familiar with some very abstract, general theory about AI and ML. I was surprised when I took an ML theory course to discover all the general theorems surrounding what kind of hypothesis functions are "learnable," etc. Is there some kind of general abstract theorem that would tell us whether an AI is "pre-memorizing all answers in its training data?" 9. Sam (B) Hopkins Says: Comment #9 September 28th, 2025 at 9:44 am Hi Scott -- Thanks for the discussion about how you used GPT5-thinking. I am very interested in how to use GPT/Claude/Gemini in TCS/math research in a way which actually increases productivity. So far most of my experience is that I have a similar several-round exchange with the chatbot to what you describe, except at the end the chat has gone totally off the rails and the arguments the bot suggests have hidden bugs which take a long time to discover and the whole thing is generally a way to burn precious research time unproductively. I also try sometimes to automate this "back and forth" by having some other chatbot act as "reviewer". But so far again with limited success. Curious if you have also tried this. Specifically regarding the rational function suggested by GPT-5, I have maybe a less snide version of OnceMore's comment. I think it is actually extremely likely that variants of this particular idea appear frequently in the training data. One guise in which I think it would appear is as a "baby" version of the Stieltjes transform which is commonly used in random matrix theory to e.g. derive the limiting spectral distribution of a Wigner matrix. Of course, it is extraordinary that the model is able to figure out which idea from the training to apply in the context you give it. (And possibly a huge time-savings for human researchers if we can figure out how to get it to do this more reliably.) 10. Scott Says: Comment #10 September 28th, 2025 at 9:47 am Julian #8: Is there some kind of general abstract theorem that would tell us whether an AI is "pre-memorizing all answers in its training data?" There are many theorems that bear on that question in one way or another. Most notably, the basic theorem on the sample complexity of PAC-learning--the "Occam's Razor Theorem" of Blumer, Ehrenfeucht, Haussler, and Warmuth--basically says that as long as you explain a sufficiently large amount of sample data drawn from some probability distribution D, using a model drawn from a class with sufficiently small "VC-dimension" (a combinatorial parameter), you can't just be "memorizing the training data," meaning that your model will probably approximately predict most future data that's drawn from the same distribution D. There are many generalizations and variations on this, but that's a paradigmatic example. 11. Julian Says: Comment #11 September 28th, 2025 at 10:44 am Hi Scott, Thanks! You know, I think I do remember this result from ML theory, but those abstract results from PAC-learning and VC-dimension theory sort of blend together in my mind Any chance of using this, or similar, results to convince the "naysayers" who think ChatGPT is all one big pre-memorization fraud? It's a beautiful result, but what do we know about the VC dimension of transformer models being "sufficiently small?" Or about the distribution that represents data on the public internet? That's one thing that bugs me about PAC learning theory, that despite the beautiful and compelling results, it seems hard to actually apply them to LLMs trained on the internet, in a compelling way. Part of the reason I ask this is because I've gotten myself in internet arguments with idiots who think ChatGPT is a fraud pre-memorizing answers to all questions, and it would be great to convonce them with some beautiful theorem from PAC learning theory... 12. Egg Syntax Says: Comment #12 September 28th, 2025 at 11:24 am Scott #10: ' There are many generalizations and variations on this' I'd be grateful if you would point to a few of these, to the extent they're approaching the problem at different angles from Blumer et al. I'm quite interested in the fundamental limitations of LLMs, and while I'm aware of some research in the area (Qiu et al's 'Ask, and it shall be given: Turing completeness of prompting' is one I find especially interesting), I'm sure there are whole swaths of the literature that I haven't found. 13. OnceMore Says: Comment #13 September 28th, 2025 at 12:26 pm Scott #5: Sorry. 14. Phillip Harris Says: Comment #14 September 28th, 2025 at 2:29 pm Is this any different from considering $det(I-E(\theta))$, or was GPT overcomplicating it a bit? 15. Dax Fohl Says: Comment #15 September 28th, 2025 at 3:00 pm Could this have been automated more completely? Like if you'd said, "assuming the conclusions of papers X and Y (attached) are correct, can you produce a formally verified proof that such-and-such conjecture holds? iterate until complete." Would that have gotten there by itself? Or if you'd asked more generally, "given the results of papers X and Y, are there any open conjectures that might be straightforward extensions of those results", would it come up with the right one? 16. Jules Jacobs Says: Comment #16 September 28th, 2025 at 5:34 pm > For me, the non-obvious part was just that there would exist a rational function of the matrix entries, of suitable degree, that would capture the needed information about the largest eigenvalue, rather than needing to dig up results from the approximation theory literature that talked about matrix norm directly. I think this is somewhat less surprising given that any symmetric rational function in the eigenvalues is a rational function in the coefficients. In fact, this applies even to functions that are symmetric in all the eigenvalues of a collection of commuting matrices. For instance, if A,B are 2x2 commuting matrices with eigenvalues a_1,a_2 and b_1,b_2, then, say, a_1 b_1 / a_2 + a_2 b_2 / a_1 is a rational function of the coefficients. Leave a Reply 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! [ ] Name (required) [ ] Mail (will not be published) (required) [ ] Website [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [Submit Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] --------------------------------------------------------------------- Shtetl-Optimized is proudly powered by WordPress Entries (RSS) and Comments (RSS).