- Grant Sanderson, of 3blue1brown, has put up a phenomenal YouTube video explaining Grover’s algorithm, and dispelling the fundamental misconception about quantum computing, that QC works simply by “trying all the possibilities in parallel.” Let me not futz around: this video explains, in 36 minutes, what I’ve tried to explain over and over on this blog for 20 years … and it does it better. It’s a masterpiece. Yes, I consulted with Grant for this video (he wanted my intuitions for “why is the answer √N?”), and I even have a cameo at the end of it, but I wish I had made the video. Damn you, Grant!
- The incomparably great, and absurdly prolific, blogger Zvi Mowshowitz and yours truly spend 1 hour and 40 minutes discussing AI existential risk, education, blogging, and more. I end up “interviewing” Zvi, who does the majority of the talking, which is fine by me, as he has many important things to say! (Among them: his searing critique of those K-12 educators who see it as their life’s mission to prevent kids from learning too much too fast—I’ve linked his best piece on this from the header of this blog.) Thanks so much to Rick Coyle for arranging this conversation.
- Progress in quantum complexity theory! In 2000, John Watrous showed that the Group Non-Membership problem is in the complexity class QMA (Quantum Merlin-Arthur). In other words, if some element g is not contained in a given subgroup H of an exponentially large finite group G, which is specified via a black box, then there’s a short quantum proof that g∉H, with only ~log|G| qubits, which can be verified on a quantum computer in time polynomial in log|G|. This soon raised the question of whether Group Non-Membership could be used to separate QMA from QCMA by oracles, where QCMA (Quantum Classical Merlin Arthur), defined by Aharonov and Naveh in 2002, is the subclass of QMA where the proof needs to be classical, but the verification procedure can still be quantum. In other words, could Group Non-Membership be the first non-quantum example where quantum proofs actually help?
In 2006, alas, Greg Kuperberg and I showed that the answer was probably “no”: Group Non-Membership has “polynomial QCMA query complexity.” This means that there’s a QCMA protocol for the problem where Arthur makes only polylog|G| quantum queries to the group oracle—albeit, possibly an exponential in log|G| number of quantum computation steps besides that! To prove our result, Greg and I needed to make mild use of the Classification of Finite Simple Groups, one of the crowning achievements of 20th-century mathematics (its proof is about 15,000 pages long). We conjectured (but couldn’t prove) that someone else, who knew more about the Classification than we did, could show that Group Non-Membership was simply in QCMA outright.
Now, after almost 20 years, François Le Gall, Harumichi Nishimura, and Dhara Thakkar have finally proven our conjecture—showing that Group Order, and therefore also Group Non-Membership, are indeed in QCMA. They did indeed need to use the Classification, doing one thing for almost all finite groups covered by the Classification, but a different thing for groups of “Ree type” (whatever those are).
Interestingly, the Group Membership problem had also been a candidate for separating BQP/qpoly, or quantum polynomial time with polynomial-size quantum advice—my personal favorite complexity class—from BQP/poly, or the same thing with polynomial-size classical advice. And it might conceivably still be! The authors explain to me that their protocol doesn’t put Group Membership (with group G and subgroup H depending only on the input length n) into BQP/poly, the reason being that their short classical witnesses for g∉H depend on both g and H, in contrast to Watrous’s quantum witnesses which depended only on H. So there’s still plenty that’s open here! Actually, for that matter, I don’t know of good evidence that the entire Group Membership problem isn’t in BQP—i.e., that quantum computers can’t just solve the whole thing outright, with no Merlins or witnesses in sight!
Anyway, huge congratulations to Le Gall, Nishimura, and Thakkar for peeling back our ignorance of these matters a bit further! Reeeeeeeee!
- Potential big progress in quantum algorithms! Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone (GLM) have given what they present as a quantum algorithm to estimate the determinant of an n×n matrix A, exponentially faster in some contexts than we know how to do it classically.
[Update (May 5): In the comments, Alessandro Luongo shares a paper where he and Changpeng Shao describe what appears to be essentially the same algorithm back in 2020.]
The algorithm is closely related to the 2008 HHL (Harrow-Hassidim-Lloyd) quantum algorithm for solving systems of linear equations. Which means that anyone who knows the history of this class of quantum algorithms knows to ask immediately: what’s the fine print? A couple weeks ago, when I visited Harvard and MIT, I had a chance to catch up with Seth Lloyd, so I asked him, and he kindly told me. Firstly, we assume the matrix A is Hermitian and positive semidefinite. Next, we assume A is sparse, and not only that, but there’s a QRAM data structure that points to its nonzero entries, so you don’t need to do Grover search or the like to find them, and can query them in coherent superposition. Finally, we assume that all the eigenvalues of A are at least some constant λ>0. The algorithm then estimates det(A), to multiplicative error ε, in time that scales linearly with log(n), and polynomially with 1/λ and 1/ε.
Now for the challenge I leave for ambitious readers: is there a classical randomized algorithm to estimate the determinant under the same assumptions and with comparable running time? In other words, can the GLM algorithm be “Ewinized”? Seth didn’t know, and I think it’s a wonderful crisp open question! On the one hand, if Ewinization is possible, it wouldn’t be the first time that publicity on this blog had led to the brutal murder of a tantalizing quantum speedup. On the other hand … well, maybe not! I also consider it possible that the problem solved by GLM—for exponentially-large, implicitly-specified matrices A—is BQP-complete, as for example was the general problem solved by HHL. This would mean, for example, that one could embed Shor’s factoring algorithm into GLM, and that there’s no hope of dequantizing it unless P=BQP. (Even then, though, just like with the HHL algorithm, we’d still face the question of whether the GLM algorithm was “independently useful,” or whether it merely reproduced quantum speedups that were already known.)
Anyway, quantum algorithms research lives! So does dequantization research! If basic science in the US is able to continue at all—the thing I promised not to talk about in this post—we’ll have plenty to keep us busy over the next few years.
This entry was posted
on Wednesday, April 30th, 2025 at 10:16 pm and is filed under Announcements, Complexity, Metaphysical Spouting, Quantum, The Fate of Humanity.
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.
You can use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations.
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.
Follow
Comment #1 April 30th, 2025 at 10:45 pm
I just watched this in the morning (as soon as I see the blue new-video dot next to 3Blue1brown in my YouTube subscriptions, my day is made), and while Grant Sanderson is absolutely amazing, you succeeded, too, Scott! When he asked the question at the beginning I correctly answered √N and immediately thought “I know that thanks to Shtetl Optimized!” For just a moment (and it was fleeting), I felt smarter than Stanford students and IMO Olympians.
Comment #2 April 30th, 2025 at 10:55 pm
Regarding Group Non-Membership, the authors note in the paper that they actually wouldn’t have to special-case Ree groups if they made use of a certain unpublished (and seemingly unavailable…) result, but they didn’t want to do that, presumably because the proof doesn’t actually seem to be available anywhere atm…
Comment #3 April 30th, 2025 at 11:15 pm
I’ve been a longtime fan (and supporter) of 3Blue1Brown, and I was incredibly happy he made this video. As an even-longer-time reader of yours, I was *very* excited to see that cameo of yours at the end!
Btw, I didn’t have a chance to comment on the last post, but your Harvard speech was wonderful.
Comment #4 April 30th, 2025 at 11:15 pm
You wrote “(Among them: that .)” Well, don’t leave us hanging!
Comment #5 April 30th, 2025 at 11:53 pm
Jair #4: Oops, fixed!
Comment #6 May 1st, 2025 at 7:17 am
From https://arxiv.org/abs/2010.04662: “It has been showed [sic] that most classical problems are not harder than multiplying two square matrices, such as matrix inversion, LU decomposition, nullspace basis computation, linear system solving, rank and determinant computations, etc.” Meanwhile the classical linear algebra analogous to GLM can be done in a black-box setting (with [Q]RAM pointing to sparsity pattern) and IIRC this generally entails something like O(nnz(A)*log(nnz(A))) to solve things (this obviously can’t be taken too literally for a dense matrix, but if I’m misremembering please chime in). This is a big speedup, and practically useful with actual solvers, but far from exponential.
Comment #7 May 1st, 2025 at 10:09 am
Vadim #1: Similar here: I immediately thought of the header of this blog and was not tempted by the O(1) option. But perhaps I *over*-learned the lesson, since (knowing nothing else about quantum computing despite being a long-time reader), I didn’t know why I should expect a quantum speedup for this particular problem. I would have conservatively guessed O(N) had it been an option!
Now I also see why it’s a tempting statement: the “flip the key dimension” operation really does look like trying everything in parallel in a single step! It’s just that it’s useless on its own: the universe doesn’t let us look at the little vector inside the computer, so we have to knock it around O(sqrt N) times before it’s useful. That’s very odd, and not what I expected quantum algorithms to look like!
Comment #8 May 1st, 2025 at 6:20 pm
Apologies for the basic questions, but what is a reasonable intuition for estimating how much information is held in “~log|G| qubits”?
Since the amplitudes are not discrete, can essentially infinite classical advice be shoved in there for the quantum computer (in say the decimal expansion of some real component)?
Presumably the answer is in some sense “no”, otherwise there would be no point in measuring the size of quantum advice in qubits. So quantum computers must not be able (in some sense) to “directly access” this type of information. Hmm… or at least not without “ruining” the initial state, such that we couldn’t ask questions about it again and again until we knew it to arbitrary precision. Maybe this just reduces to the “no-cloning theorem” if worded correctly.
This made me wonder, if a quantum computer was given two N qubit states, could it even say whether they were “equal” (to some specified degree of precision)? Even if a quantum “memcpy” is not allowed, can we at least do a quantum “memcmp” ?
Comment #9 May 1st, 2025 at 7:38 pm
3blue1brown is a revelation. From this, to LLMs, to even basic linear algebra, it teaches things better than almost any course I’ve ever taken. It’s pure magic.
Comment #10 May 1st, 2025 at 7:45 pm
Kevin #8: There are at least three defensible answers for “how much classical information is in an n-qubit state”: namely ~n, ~2n, and ∞. You see only n bits when you measure the state, but it takes ~2n bits to specify the state to some reasonable precision, and (as you pointed out) it takes ∞ bits to specify the state exactly.
For quantum advice, the two relevant answers are ~n and ~2n. Roughly speaking, we expect n-qubit quantum advice to be little better than n-bit classical advice “most of the time,” but for some special tasks, where you can actually extract what you need via appropriate measurements, it could be as good as 2n-bit classical advice. A lot of my work in quantum complexity theory over the past 20+ years has been devoted to where exactly quantum advice falls between these two extremes.
If you hold two n-qubit pure quantum states, the famous “swap test” lets you decide whether they’re nearly equal or nearly orthogonal (or more generally, estimate their inner product, with accuracy depending on how many copies of them you have). This doesn’t straightforwardly generalize to mixed states. Not sure if that’s what you were asking.
Comment #11 May 2nd, 2025 at 12:04 am
Why do you suspect the problem is BQP complete?
Comment #12 May 2nd, 2025 at 5:20 am
Thank you so much for directing me to Grant Sanderson’s video and his channel. This made my day and was a great birthday present. Please keep on sending rays of sun shine in my life :).
Comment #13 May 2nd, 2025 at 7:35 am
About GLM’s results – awesome! I’m curious as to why the estimate is good to a multiplicative error, as my intuition is that quantum algorithms shine especially on additive errors of numbers that can be both positive and negative. I think that this is where, e.g., classical Stockmeyer counting breaks down. In GLM’s case, is it because they estimate log det A up to an additive error (and hence estimate det A up to the multiplicative error?)
Also, it looks like GLM applies quantum phase estimation of \(U=(\exp(-iAt)\) to the maximally mixed state because they want to sample the eigenvalues of A (or of U) uniformly at random over all eigenvalues of A. So they don’t need to read the fine print about state preparation. But, because GLM acts on the fully mixed state, could GLM be complete for some version of DQC-1/DQC-k with k bits of accuracy in the QPE, if A were local or otherwise oracularly accessible and U was given as a black-box?
Comment #14 May 2nd, 2025 at 9:19 am
Scott, you mention that you gave some answers for what your intuition was for why the answer was root of N, but in the video Grant gives the Pythagoras intuition as explanation. Was this your explanation or did Grant go with another?
Comment #15 May 2nd, 2025 at 9:59 am
Regarding “dequantization” Scott: I would think that, if we are “fair” to quantum algorithms that can be outperformed by classical ones, some quantum might be “simpler/more elegant to derive” than the classical algs that equal their performance.
This seems like something you must have written about previously – have you?
Comment #16 May 2nd, 2025 at 10:29 am
The 3B1B video mentions you can flip the amplitude of a particular base vector (selected by some circuit) from +1 to -1. I have two questions regarding this:
1) if the circuit was selecting way more base vectors (like all the ones where the first qubit is 1 snd the second qubit is 0, which is a quarter of the entire state space), would that work too? I.e. all those qubits would flip to -1. Would this be cheap in terms of gate count?
2) if I have a system setup with one or more selected base vectors at -1, and all the rest still at +1, and then i have a separate system where all the base vectors are at +1 (after the original hadamar initialization), is there some kind of sum operation on those two states that give me a resulting state where the selected base vectors have amplitude zero and the others at 1? (like summing all the amplitudes and renormalizing)? And if feasible would that be cheap in terms of gate count?
Comment #17 May 2nd, 2025 at 10:50 am
Adam Treat #14: Yes, I explained to Grant that it’s all down to Pythagoras, or if you prefer, to amplitudes in QM being based on the 2-norm rather than the 1-norm. The square root in Grover’s algorithm comes in a very direct way from the square root that you take to change a probability into an amplitude (and the video explains how).
Comment #18 May 2nd, 2025 at 10:55 am
Hamish Todd #10: Yes, of course. Even when dequantization is possible in principle, it might be a pain in the butt—thereby giving us “practical quantum advantage if you count not merely computation time, but also human programmer/mathematician time.” This point must have been raised, by me and/or commenters, at least 10 previous times (probably more) in this blog’s 20-year history, but I don’t feel like looking for where right now.
Comment #19 May 2nd, 2025 at 11:08 am
Fred #16:
1) Yes, not only does Grover’s algorithm still work fine when there are multiple marked items, it’s faster: if K items out of N are marked, then the number of iterations is only ~√(N/K).
2) No, there’s no physical operation in QM to sum two states in general. Such an operation, if it existed, would violate normalization (ie probabilities adding up to 1). If we enforced normalization by hand, we’d get all sorts of superpowers, such as superluminal signaling and instantaneous solution of hard search problems, that normal QM doesn’t give us.
Comment #20 May 2nd, 2025 at 12:21 pm
Scott #19
ok, but maybe there’s a series of sqrt(n) operations to turn those -1 into zeros, that’s pretty much what grover is doing after all.
Instead of setting the base vectors we want to get rid off at -1, we set the ones we want to keep at -1, and apply grover?
That assumes that this flip of phase Grover is doing repeatedly would work to amplify multiple base vectors at once, not just one.
All im trying to do is initialize the QC on a large subset of its space, maybe you can already use hadamar easily to do this but i don’t know.
Comment #21 May 2nd, 2025 at 12:51 pm
fred #20: If I give you efficient procedures to prepare two states |v⟩ and |w⟩, you can derive from that an efficient procedure to prepare a linear combination a|v⟩+b|w⟩, although the time needed will blow up with the inverse of the angle between |v⟩ and |w⟩, relevantly for the example you discuss. And this is inherent, since otherwise we could use it to beat Grover’s algorithm, which is known to be impossible! See for example Proposition 3.3.4 in my Barbados talks.
Comment #22 May 2nd, 2025 at 1:08 pm
Scott #21 not sure I follow, sqrt(N) seems pretty efficient in the context of manipulating a large section of the entire 2^N space of base vectors!
So, for 3 qubits, even if Grover let us turn
+1, +1, -1, -1, +1, -1, +1, +1 (each is the factor of each base state, 000, 001,.. 111)
into
+1/5, +1/5, 0, 0, +1/5, 0, +1/5, +1/5
there isn’t any way to combine it with another state of 3 other qubits, like this one
+1/3, 0, +1/3, 0, 0, 0, +1/3, 0
and get a sort of OR combination
+1/6, +1/6, +1/6, 0, +1/6, 0, +1/6, +1/6
?
The funny thing is that the limitation of QC we mainly hear about, that one can only sample from the final state, that limitation is quite easily absorbed (even if it’s a really big one)… but noone hardly ever mentions all the other critical limitations like “you can’t OR or AND two states, you can’t duplicate a state”, etc. Which in my opinion are much harder to absorb for anyone familiar with classical circuit design… leaving one wondering “what the hell can I do then?!”. At least the video makes it more obvious that all you can do is rotate the state vector around its unit sphere, or reflect it a bit, etc and repeat that to try and approximate a more classical operation.
Comment #23 May 2nd, 2025 at 1:29 pm
I still believe it was a huge disservice/source of confusion to call those things “qbits” and “quantum gates”… it should have been “quantites” and “rotators/reflectors” or some new names like that with no callback to classical concepts that hardly apply at all. 😛
Comment #24 May 2nd, 2025 at 2:09 pm
fred #22-23: No, you completely misunderstood, N means the number of possible solutions (so, N=2n where n is the number of qubits).
And “qubits” and “quantum gates” seem like totally fine terms to me, as they really are the most obvious quantum generalizations of bits and Boolean logic gates respectively.
Comment #25 May 2nd, 2025 at 2:19 pm
Scott #24
oops, sorry, I didn’t missunderstand, but I did a quick edit and messed up the notation – it’s obviously sqrt in the number of base vectors, 2^n (it gets confusing to call that N=2^n, as I tend to call the size of any NP complete problems as n or N)
I guess it’s because in the context of Grover, you call the “DB” size N, and then need n=log(N) bits to label the entries.
Comment #26 May 2nd, 2025 at 2:38 pm
The video refers to the search being one example of NP problems, but while it’s indeed NP, as a practical problem you would only run a classical or grover search on a space that’s not exponentially large, e.g that would not need 100 bits to label 2^100 entries, but N is the search problem size, requiring n=log(N) bits.
While I’m more used to think the other way around for NP complete problems, where n bits is the input size and you’d need to test on 2^n solutions. Anyway….
So yea, Grover doesn’t help prepare actual problems that have exponentially large solution space, in that context it’s not efficient at all.
Comment #27 May 2nd, 2025 at 2:48 pm
Scott #24
Given that you can OR two classical states, but can’t do that with quantum gates, I don’t quite see how quantum gates are a “generalization” of classical gates. The term generalization implies that you get the specific capabilities and then something extra on top, no?
Of course classical computers are quantum systems, so there’s a way for a QC to give back the classical behavior (by getting rid of the quantumness), but the generalization doesn’t happen at the qbit/quantum gate or small circuit level, since for example you can’t even duplicate a very simple state like you can classically.
And you can’t easily compose quantum circuits like you can compose classical ones (otherwise achieving quantum scaling would be a smoothly achievable win at Moore’s rate).
So I don’t think the terminology is as intuitively useful as you put it.
Comment #28 May 2nd, 2025 at 3:13 pm
I shut up after this.
As an aside, in the 60s, the popular philosopher Alan Watts explains that human brains are processing the patterns they get in their perceptions by turning spaces into grids (and measuring and counting, a form of labeling) as a process of taking literal bites at the world, i.e turning things into small absorbable “bits” (exactly the way we eat). But the brain is quite inefficient, so it needs those bits and process them serially, one at a time, what we call rational thinking (and it’s funny how this maps to the term “bit” used in CS).
But the brain has a more basic/fundamental parallel way of functioning where perceptions are just experienced as is – and the purpose of meditation is to go back to it and take a break from rational/bit thinking… we need this to make thinking more efficient/meaningful.
Comment #29 May 2nd, 2025 at 3:21 pm
fred:
– People run exponential-time algorithms all the time, with small values of n. Grover’s algorithm could absolutely help in that context, reducing 2n to 2n/2.
– You can compute OR (or any other classical function) on a quantum computer as long as you embed it into a larger reversible function, like
|x,y,z⟩ → |x,y,z⊕(x OR y)⟩.
Comment #30 May 2nd, 2025 at 3:36 pm
Adam Treat #14, Scott #17: This sounds like Grant learned the general Pythagoras intuition for the root of N from Scott (both in the sense of generalized probability, and as the actual reason for the 1/sqrt(N) entries), but elaborated this intuition into a geometric picture himself for Grover’s algorithm, in the sense that the intermediate states on the diagonal only exist for the quantum case.
Comment #31 May 2nd, 2025 at 3:44 pm
Scott #29
1) that’s a great point, thank you: slicing n in 2 makes indeed a huge practical difference.
2) yes, i’m actually aware you can indeed implement many classical gates as long as you make them reversible (by adding ancillary qbits), so you’re right there it’s indeed a generalization, I stand corrected.
But I was stuck thinking a more general manipulation of states on n qubits
like (on 3 qubits)
1/sqrt(2) (0,0,0)+ 1/sqrt(2) (1,1,1)
mushed with
1/sqrt(2) (0,0,0)+ 1/sqrt(2) (0,0,1)
to give
1/sqrt(3) (0,0,0) + 1/sqrt(3)(0,0,1) + 1/sqrt(3) (1,1,1)
but you already pointed out this can’t be done, it’d be too powerful.
I’m terribly stubborn, but thank you for correcting me once again, I hope it wasn’t a waste of time for other readers!
Comment #32 May 2nd, 2025 at 5:11 pm
@gentzen #30
I’m always amused by the fact that when you walk between two points in the NYC street grid, the distance you travel can never be shorter than p2.y – p1.y + p2.x -p1.x, no matter the trajectory you take (as long as it’s within the rectangle defined by the two points). As a result you should always cross at the currently green direction at intersections.
Then the scale doesn’t matter either – if the city grid was huge, and you’d be an observer far up (but didn’t know that space was quantized this way on the small scale), and observe a traveller go from p1 to p2 on what looks like a smooth diagonal, even though the distance appears to be sqrt ((p2.y-p1.y)^2 + (p2.x-p1.x)^2), the speed of the traveller would appear to be mysteriously smaller when he takes that diagonal (because he’s making microscopic zigzags imperceptible to the observer).
Comment #33 May 2nd, 2025 at 8:14 pm
Ah I love Grant’s channel. He has such a pleasant and delightful style. He was a guest on StarTalk too some time ago.
Comment #34 May 2nd, 2025 at 8:16 pm
Grant gets a lot of praise, but not enough– he really is amazing.
Comment #35 May 2nd, 2025 at 10:40 pm
Hello Scott and the community.
I’m jumping in here to mention that a few years ago I wrote a similar algorithm for the log-determinant, which can be found here: https://arxiv.org/abs/2011.06475 . It seems to me that it is more general and faster: we have a linear dependence in the approximation error (instead of cubic) and we are linear in the sparsity (instead of quadratic).
The GLM authors were very kind and prompt in replying and are updating their manuscript to include references to earlier work on this problem (which is not only my work, but also https://link.aps.org/accepted/10.1103/PhysRevA.100.012304 and https://arxiv.org/pdf/1902.10394 )
Our work also introduces some additional non-trivial algorithms that might be of interest to the readers following this topic.
– \(Tr[A^{-1}]\) (this can be improved a lot)
– Entropy of graphs (i.e. the von Neumann entropy of the rescaled adjacency matrix of a graph)
– \(Tr[A^p]\) for big and small p. This uses a cute polynomial approximation of monomials (quadratic speedup without Grover!!) and a powerful algo for \(Tr[A^TA]\).
As applications we consider 3 problems in spectral graph theory: counting triangles, spanning trees and estimating effective resistance between nodes.
I collected few interesting non-trivial(!) open-problems around this topic, and I am happy to discuss with anyone, if interested.
I might be wrong, but I don’t see why a quantum algorithm for the log-determinant should not be dequantized. Subsampling a smaller matrix \(B\) of exponentially smaller size from \(A\), and using the log-determinant of that as unbiased estimator might suffice. Or am I missing something?
Before delving into BQP-complete problems, is there anything interesting things to say on the relation between log-det and DQC1-related classes?
Comment #36 May 2nd, 2025 at 10:54 pm
Alessandro Luongo #35: Thanks!! Will add something about this to the post tomorrow.
Comment #37 May 3rd, 2025 at 8:55 am
Alessandro Luongo #35-
Neat! Dumb question – does your putative classical subsampling algorithm only work when entries of A are non-negative or non-positive, or otherwise at least real? I really don’t know! Just thinking that it might be hard to use Monte Carlo to classically estimate the volume of the symmetric difference of two beans or potatoes in n-space, if the two potatoes are similarly oriented to each other.
Also, with f(x) being a (Lipschitz continuous?) matrix function, as for DQC-1 problems I think Cade and Montenaro’s Schatten p-norm paper is noteworthy; I think they apply phase estimation of U=exp(-iAt) to the maximally mixed state, and evaluate f=|\lambda|^p on the clock registers in superposition, then using HHL’s rotation trick and uncompute the phase estimation. Whereas what I think GLM is doing is phase estimation on the maximally mixed state, measuring the clock registers, and evaluating f=\log\lambda classically. I’m not sure but it looks like your and Shao’s algorithm doesn’t act on the maximally mixed state; rather, Lemma 39 seems to imply it acts on the uniform state?
Comment #38 May 4th, 2025 at 7:07 am
Note that 3B1B added an additional video on Grover
Comment #39 May 4th, 2025 at 10:02 pm
Hamish Todd #15 and Scott #18: See the last paragraph of https://scottaaronson.blog/?p=7409, which mentions that what counts as a “quantum advantage” could in principle change depending on whether you include all of the time and resources required to “set up” the algorithm implementation (e.g. by fine-tuning a general algorithm for a specific problem).
Arguably, a “real-world” quantum advantage should incorporate those “setup costs” (including the research resources required to discover the algorithms in the first place!). But of course these costs are vastly more difficult to quantify and analyze systematically than straightforward runtimes and qubit counts are. And under the more “inclusive” approach to resource cost analysis, it is inherently somewhat arbitrary where you draw the line for which “operational overhead costs” to include. Eventually, it becomes more a problem for businesspeople than for computer scientists.
Comment #40 May 5th, 2025 at 11:29 pm
Hey, just watched your talk on the Harvard CSMA YouTube and the slides you presented at the end around 58 minutes in caused me to have a question.
You said that with classical physics, we can solve problems in P efficiently, and with quantum physics, we can exploit interference to efficiently solve some problems in NP.
Carrying that logic further, if you were a science fiction writer trying to design a system of physics in which NP complete systems could be efficiently solved, what kind of properties might you have in that physics to serve a role sort of like interference. What might “higher order interference” look like in terms of the associated physics?
You do talk about ways people have addressed similar problems by thinking about actual physics, but I’m interested in imaginary sci-fi physics.
(Hard question, obviously, feel free to speculate recklessly or include details just for Hollywood.)
Comment #41 May 6th, 2025 at 6:40 am
Ryan #40: Twenty years ago, I wrote an entire fun survey article about exactly that question, called NP-complete Problems and Physical Reality. Enjoy! 🙂
Incidentally, all P problems are also NP problems (P is a subset of NP). Quantum computing does indeed promise to solve certain specific NP problems (like factoring and discrete log) that are not currently known to be in P.
Comment #42 May 6th, 2025 at 9:14 am
Ryan #40,
Scott’s is a great article, but unless I’m missing something it seems to omit my favorite speculative answer in the same vein: that physical reality might not be computable. That there exist physical systems which are in principle uncomputable. The results from experiments on such systems might give answers to uncomputable questions and thus be exploitable to solve NP problems.
A long time ago, Scott gave me an example of how a physical system that “answered” the halting problem or gave kolmogorov complexity could possibly be exploited to solve NP-complete problems.
I think that’s a rich ground for sci fi speculation. Imagine a wormhole which contained a box that could answer whether a given computation halts. You’d have to go in and come out to get the answer, but that could in theory be used to solve NP-complete problems. Fun!
Comment #43 May 7th, 2025 at 3:40 am
I always feel a little bit “bilked” by the intuition usually given for Grover’s algorithm. Transforming the black box function working with classical gates into a quantum based one (in the of course excellent video at 20:50) seems like an unfair method of changing the game’s rules to me (actually, you do not consult the orginal black box but a mightier version of it).
Comment #44 May 9th, 2025 at 4:40 am
I am surprised that the algorithm for log-determinant is so highly praised here. In the end it’s “Take a matrix A, implement e^itA, run it on a random state, then run QPE, you get a random eigenvalue”. Which is neat, but also it is just a combination of existing primitives (hamiltonian simulation, QPE).
Frankly most “new” quantum algorithms are just Grover or QFT/QPE applied in some new context, which leads me to the sad belief that there aren’t really any significant quantum speedups left to discover.
Comment #45 May 9th, 2025 at 7:03 am
I must have missed something.
Luks in 1993 “Permutation groups and polynomial-time computation” states that obtaining the order of a group, testing membership of an element, and testing subgroup can be done in polynomial time, all because Sim’s methods.
Could you tell what is different for them to be just in AM and coAM?
Thank you.
Comment #46 May 9th, 2025 at 8:25 am
Cristóbal Camarero #45: That’s all for permutation groups—meaning, groups given to you via permutations, not merely groups that can be represented that way (as all finite groups can). The problems for arbitrary black-box groups are harder.
Comment #47 May 9th, 2025 at 8:38 am
Thank you Scott #46, that makes sense, yet I have to think more on it.
I also wanted to say that I love the movie scenario you describe in 3blue1brown video.
Comment #48 May 10th, 2025 at 8:52 am
Collette #44:
Perhaps, but taken to the extreme I don’t think you would analogously say that the Schönhage–Strassen algorithm is just the FFT applied in a new way… That’s not to say that finding the determinant of a large matrix, enabled by GLM, has as many applications as the Schönhage–Strassen algorithm does in enabling the multiplication of very large numbers, just that we should be careful about pigeonholing new uses for old paradigms.
Also, Yamakawa-Zhandry is “new”, as is Decoded Quantum Interferometry, but they both work on very different primitives from the Hamiltonian Simulation + Quantum Fourier Transform = Quantum Phase Estimation standard.
Comment #49 May 19th, 2025 at 6:38 pm
If we can have polysized 3cnf formula f1, f2 where deciding f1 is NP complete and f1(x)=0 iff f2(x)=1 where we can get such polysized f2 from f1 in FZPP is NP in coAM or may be othrr related effects? So if P=ZPP then is NP=coNP if such construction exists?
Comment #50 May 22nd, 2025 at 4:15 pm
Assume just even f1 and f2 are 3SAT formulas on m and n variables respectively constrained by |x:phi(x)=1|=|y:psi(y)=0|. If the reduction from phi to psi is in FP or FZPP would it follow NP=coNP or NP in coAM respectively?
Comment #51 December 24th, 2025 at 11:40 pm
[…] inspired by Grant Sanderson’s 3Blue1Brown—a math YouTube channel that I’ve also praised to the skies on this blog—but Aaron has chosen to focus on theoretical computer […]