Of course Grover’s algorithm offers a quantum advantage!
Unrelated Update: Huge congratulations to Ethernet inventor Bob Metcalfe, for winning UT Austin’s third Turing Award after Dijkstra and Emerson!
And also to mathematician Luis Caffarelli, for winning UT Austin’s third Abel Prize!
I was really, really hoping that I’d be able to avoid blogging about this new arXiv preprint, by E. M. Stoudenmire and Xavier Waintal:
Grover’s Algorithm Offers No Quantum Advantage
Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine) which must be specified for a given application and whose internal structure is not part of the formal scaling of the quantum speedup guaranteed by the algorithm. Grover’s algorithm also requires exponentially many steps to succeed, raising the question of its implementation on near-term, non-error-corrected hardware and indeed even on error-corrected quantum computers. In this work, we construct a quantum inspired algorithm, executable on a classical computer, that performs Grover’s task in a linear number of call to the oracle – an exponentially smaller number than Grover’s algorithm – and demonstrate this algorithm explicitly for boolean satisfiability problems (3-SAT). Our finding implies that there is no a priori theoretical quantum speedup associated with Grover’s algorithm. We critically examine the possibility of a practical speedup, a possibility that depends on the nature of the quantum circuit associated with the oracle. We argue that the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions on both hardware quality and availability.
Alas, inquiries from journalists soon made it clear that silence on my part wasn’t an option.
So, desperately seeking an escape, this morning I asked GPT-4 to read the preprint and comment on it just like I would. Sadly, it turns out the technology isn’t quite ready to replace me at this blogging task. I suppose I should feel good: in every such instance, either I’m vindicated in all my recent screaming here about generative AI—what the naysayers call “glorified autocomplete”—being on the brink of remaking civilization, or else I still, for another few months at least, have a role to play on the Internet.
So, on to the preprint, as reviewed by the human Scott Aaronson. Yeah, it’s basically a tissue of confusions, a mishmash of the well-known and the mistaken. As they say, both novel and correct, but not in the same places.
The paper’s most eye-popping claim is that the Grover search problem—namely, finding an n-bit string x such that f(x)=1, given oracle access to a Boolean function f:{0,1}n→{0,1}—is solvable classically, using a number of calls that’s only linear in n, or in many cases only constant (!!). Since this claim contradicts a well-known, easily provable lower bound—namely, that Ω(2n) oracle calls are needed for classical brute-force searching—the authors must be using words in nonstandard ways, leaving only the question of how.
It turns out that, for their “quantum-inspired classical algorithm,” the authors assume you’re given, not merely an oracle for f, but the actual circuit to compute f. They then use that circuit in a non-oracular way to extract the marked item. In which case, I’d prefer to say that they’ve actually solved the Grover problem with zero queries—simply because they’ve entirely left the black-box setting where Grover’s algorithm is normally formulated!
What could possibly justify such a move? Well, the authors argue that sometimes one can use the actual circuit to do better classically than Grover’s algorithm would do quantumly, and therefore, they’ve shown that the Grover speedup is not “generic,” as the quantum algorithms people always say it is.
But this is pure wordplay around the meaning of “generic.” When we say that Grover’s algorithm achieves a “generic” square-root speedup, what we mean is that it solves the generic black-box search problem in O(2n/2) queries, whereas any classical algorithm for that generic problem requires Ω(2n) queries. We don’t mean that for every f, Grover achieves a quadratic speedup for searching that f, compared to the best classical algorithm that could be tailored to that f. Of course we don’t; that would be trivially false!
Remarkably, later in the paper, the authors seem to realize that they haven’t delivered the knockout blow against Grover’s algorithm that they’d hoped for, because they then turn around and argue that, well, even for those f’s where Grover does provide a quadratic speedup over the best (or best-known) classical algorithm, noise and decoherence could negate the advantage in practice, and solving that problem would require a fault-tolerant quantum computer, but fault-tolerance could require an enormous overhead, pushing a practical Grover speedup far into the future.
The response here boils down to “no duh.” Yes, if Grover’s algorithm can yield any practical advantage in the medium term, it will either be because we’ve discovered much cheaper ways to do quantum fault-tolerance, or else because we’ve discovered “NISQy” ways to exploit the Grover speedup, which avoid the need for full fault-tolerance—for example, via quantum annealing. The prospects are actually better for a medium-term advantage from Shor’s factoring algorithm, because of its exponential speedup. Hopefully everyone in quantum computing theory has realized all this for a long time.
Anyway, as you can see, by this point we’ve already conceded the principle of Grover’s algorithm, and are just haggling over the practicalities! Which brings us back to the authors’ original claim to have a principled argument against the Grover speedup, which (as I said) rests on a confusion over words.
Some people dread the day when GPT will replace them. In my case, for this task, I can’t wait.
Thanks to students Yuxuan Zhang (UT) and Alex Meiburg (UCSB) for discussions of the Stoudenmire-Waintal preprint that informed this post. Of course, I take sole blame for anything anyone dislikes about the post!
For a much more technical response—one that explains how this preprint’s detailed attempt to simulate Grover classically fails, rather than merely proving that it must fail—check out this comment by Alex Meiburg.
Follow
Comment #1 March 22nd, 2023 at 10:43 am
When you say “the technology isn’t quite ready to replace me at this blogging task” is it because GPT-4 was unable to read the pre-print given input methods available to you, or because it did read it and its answer was not satisfactory? If the former, how are you able to have it read linked (or uploaded?) pdf’s? If the latter, how off was it?
Comment #2 March 22nd, 2023 at 10:53 am
lewikee #1: It was insufficiently scathing. 🙂 It said that I’d have various concerns about the results, blah blah blah, but it didn’t go straight for the central reasons why there’s nothing new here. Then, when I explicitly asked it to be scathing, it was scathing about Grover’s algorithm, rather than about this paper falsely claiming to refute Grover!
Comment #3 March 22nd, 2023 at 10:59 am
Scott,
I kindly encourage you to moderate your tone here. These are young researchers at a vulnerable stage in their career. When one of the leading minds in quantum complexity theory writes something so rude and disrespectful on his blog, frequented by so many, it’s not only embarassing for these young scientists but positively damaging to their career. As the most prominent voice in the community, you have the obligation to treat young, vulnerable scientists with respect and dignity, not to trash their work and shame them on your blog. Yes, you can criticize their work, but do it in a kinder and more respectful tone.
Comment #4 March 22nd, 2023 at 11:03 am
Clearly Grover on a fault-tolerant quantum computer can solve general SAT (not just 3SAT) in time 2^{n/2}*poly(n) if we let f correspond to a poly(n)-sized classical reversible circuit that evaluates the truth-value of a given logical formula on n Boolean variables. If this is not a quantum speedup over classical algorithms, then the strong exponential-time hypothesis is refuted (which is not out of the question, but would be a very big result).
Comment #5 March 22nd, 2023 at 11:12 am
Anonymous CS Academic #3: I would’ve tended to agree with you, had the preprint itself not trashed the work of hundreds of young quantum computing theorists over the past quarter-century and today, by implicitly accusing them of basing all their work on a trivial, freshman-level misunderstanding. In a situation like that, ad-hominem attacks are still strictly off limits, but the authors have forfeited the right to kid gloves.
Comment #6 March 22nd, 2023 at 11:12 am
(Wow- I get the to comment on a post before there are 100 comments before mine.)
1) The quote I like about novel and correct is
Your paper is novel and correct. Unfortunately the parts that are novel are not correct, and the parts that are correct are not novel.
I’ve also seen the same quote for Interesting/original.
2) I used to look at papers that, say, claim to have shown P=NP or P NE NP and read them thinking that, though I doubt they live up to their claim, may have something of interest. I no longer do that. I used to ask someone like you (and often you) things like `I know the Grover-refuting paper is not correct, but is there anything of interest in it’ I no longer do.
Comment #7 March 22nd, 2023 at 11:29 am
I thought we covered many of these “breakthrough” ideas in 2004
https://arxiv.org/abs/quant-ph/0405001
Comment #8 March 22nd, 2023 at 11:29 am
But now that we know that Scott Aaronson complains about GPT not being able to replace him at blogging, we can expect that when the day comes where GPT replaces him at blogging, it will need tp be able to complain about how GPT can’t replace him at blogging.
Comment #9 March 22nd, 2023 at 11:39 am
Anonymous CS Academic #3: According to his CV, Miles Stoudenmire graduated from college in 2005, so he’s probably pushing 40.
Comment #10 March 22nd, 2023 at 11:49 am
> So, on to the preprint, as reviewed by the human Scott Aaronson.
Rather more a sneer than a review, I feel. I’d be interested to see you engage with (what I would say is) the paper’s core point:
“We emphasize that our work does not contradict previous work that formally proves that the quantum speed-up of GA is optimal [8]. While the proof is certainly valid technically, its usefulness for a given problem requires the best known classical strategy to scale as 2^n (i.e. worst-case classical scaling) for that problem. But for any specific problem, if Grover’s can be applied there must exist an explicit circuit for the oracle. So there is always at
least some structure to the problem: the structure of the oracle circuit. One can always try to simulate this oracle circuit by applying it to a tensor network.”
(Incidentally, I think you were being trolled by comment #3; the paper’s authors are hardly “young researchers”, nor are their careers in condensed matter physics likely to be affected by this post)
Comment #11 March 22nd, 2023 at 12:15 pm
Thanks for writing this Scott (and thanks to Ryan Babbush for his comment on scirate).
Comment #12 March 22nd, 2023 at 12:43 pm
Scott, I’m curious to hear your opinion as a quantum complexity expert: do you think a quantum algorithm might exist beating Grover’s square-root speedup, say a polynomial-time quantum algorithm for solving the generic preimage problem? O(2^{n/2}) isn’t sufficient for a preimage attack on cryptographic hash, for example, but a polynomial-time quantum algorithm could break all these cryptographic hash.
Comment #13 March 22nd, 2023 at 12:48 pm
Scott, Can you elaborate on how they “use the circuit in a non-oracular way to extract the marked item”? Below Eq.(18), the authors say “We emphasize that QiGA itself knows nothing about the solution \( w^\alpha \) and only uses the amplitudes \( \langle \beta \vert \psi_w\rangle \). So the authors are not assuming that the oracle knows the solutions. I think they only assume that it can verify the solutions, which sounds reasonable.
Comment #14 March 22nd, 2023 at 1:02 pm
Vladimir #10: As I already said in the post, to the extent there’s anything correct in that passage (e.g., that the unconditional Grover speedup becomes conditional as soon as you instantiate the oracle), it’s been obvious to every quantum algorithms researcher since 1996, and is taught in the Grover portion of undergraduate quantum computing courses (certainly including mine).
If the authors had just wanted to write a pedagogical article bringing this well-known point to the attention of outsiders (e.g., in condensed-matter physics), that would’ve been great. Instead, they explicitly positioned their paper as refuting the usual understanding of Grover’s algorithm, and as proving that the Grover problem can (sometimes? usually? always?) be solved classically with a “linear number of queries”—all of which kicks up a thick layer of obfuscating dust and results in a negative contribution to understanding the issue.
Comment #15 March 22nd, 2023 at 1:07 pm
Scott #2: “Then, when I explicitly asked it to be scathing, it was scathing about Grover’s algorithm, rather than about this paper falsely claiming to refute Grover!”
I often wonder how AI will perform on subjects with a very high bullshit-to-truth ratio on the internet. For instance, my mom is a veterinary behaviorist, and generally finds that at least 90% of the popular articles about dog and cat behavior are wrong (some of which leading to dangerous or destructive results). When it comes to e.g. dog behavior, exercise progressions, and (for some reason) quantum computing, it seems that everyone online thinks their view is just as valid as that of the experts.
I imagine it’s difficult for GPT to deal with that issue? Short of getting you, my mom, and others to quit their jobs and manually label training data as “true” or “bullshit,” I’m not really sure what else OpenAI could do. But I don’t really know the details on how these systems work…
Comment #16 March 22nd, 2023 at 2:54 pm
I agree that the paper is excessively strident in its claims of overturning previous results, but if I was to steelman the argument, I think there is a well-defined non-oracular problem which most people implicitly associate with Grover, which is “given an arbitrary quantum circuit with a promise that it is diagonal in the computational basis, find an input to that circuit with eigenvalue -1”. The relevant metric would then be circuit depth, rather than oracle calls.
Is it possible that this Grover-esque problem is actually classically solvable with equal circuit depth to the quantum case (via some sort of tensor network magic that I’m not following at the moment)? My guess is no, but it doesn’t seem obviously ruled out.
Comment #17 March 22nd, 2023 at 3:25 pm
Topologist Guy #12:
do you think a quantum algorithm might exist beating Grover’s square-root speedup, say a polynomial-time quantum algorithm for solving the generic preimage problem?
I’m extremely doubtful that there’s anything better than Grover for the generic preimage problem, though I’d be happy to be proved wrong about that. I’m much more optimistic about the possibility that, for certain specific natural NP-complete problems, there might be quantum algorithms that achieve superquadratic speedups over the best classical algorithms, or maybe even superpolynomial speedups (e.g., exp(√n) rather than exp(n)).
Comment #18 March 22nd, 2023 at 3:35 pm
Bhuvanesh Sundar #13:
Scott, Can you elaborate on how they “use the circuit in a non-oracular way to extract the marked item”?
For starters: do you agree that, if the circuit were used only as an oracle, then a Ω(2n) lower bound on query complexity would hold—that this is a proven theorem?
If you do, then since the authors claim to violate that bound, plainly they must use the circuit in a non-oracular way, leaving only the question of how! Agreed?
And indeed, the paper explicitly talks about using the circuit non-oracularly—looking at the states that it generates, doing tensor network voodoo on it, etc. etc. Frankly, I don’t much care about the technicalities of this, because we’ve already established that they’re not relevant. The car of reasonableness and clarity has already veered off the cliff; what’s left is just hashing out the details of how it explodes in flames.
Comment #19 March 22nd, 2023 at 3:41 pm
If I understood correctly, some instances of circuits for the oracle admit an efficient classical algorithm like the one presented by the authors of the preprint. My question is: which practical problem does not admit a classical efficient algorithm, therefore showing off quantum advantage of GA for that specific instance of the oracle ?
Comment #20 March 22nd, 2023 at 3:45 pm
Phil Reinhold #16:
Is it possible that this Grover-esque problem is actually classically solvable with equal circuit depth to the quantum case (via some sort of tensor network magic that I’m not following at the moment)? My guess is no, but it doesn’t seem obviously ruled out.
Of course it’s possible (given current knowledge), because it’s possible even that P=NP! But as Ronald de Wolf rightly points out in #4 above, for Grover even to be matched classically on the general problem that you mention, the Strong Exponential Time Hypothesis (SETH) would have to fail, which would be a big deal.
And again: this is all stuff that complexity theorists have understood extremely well for decades. What grates is for this paper to position itself as refuting the accepted ideas in quantum complexity theory, with its jumbled freshman-level observations about Grover, when the authors apparently couldn’t be bothered to consult even a single complexity theorist before releasing it.
Comment #21 March 22nd, 2023 at 5:47 pm
Related to Unrelated Update Dept: Luis Caffarelli of UT Austin has just won the Abel Prize.
Comment #22 March 22nd, 2023 at 6:07 pm
Several people have asked (in this comment section, and other fora) whether the classical algorithm they describe may give new SOTA on some problems. This is an interesting question, but I am fairly confident that the answer is “no”, and I’ll try to explain why here. Scott, I apologize for filling your comment section with a large wall of text.
[TL;DR: The performance of their algorithm is directly related to the entanglement entropy of the oracle circuit. Oracle circuits for hard problems that we care about always have high entanglement entropy; the easy one have low tree-width, which we already know how to solve. If you somehow came up with an oracle circuit for a hard problem that had much better entanglement entropy, then that is an insight to the problem structure that we should expect give you an easy classical algorithm anyway — with no reference to Grover’s algorithm or MPSs. We should only expect an advantage if someone finds an oracle circuit for a problem that is both (1) low entanglement entropy and (2) truly quantum. In which case, that would be the true, exciting result.]
First, a brief overview of the approach of the paper and MPSs.
The computational cost in their algorithm is dominated by largest entanglement entropy generated by the oracle circuit. Grover’s algorithm begins by preparing a Hadamard state |s> = |+++…+>. This is followed by ~2(n/2) alternating applications of the oracle and the diffusion operation. This gives a quantum circuit that can be simulated by any number of classical simulation algorithms. Among the more popular simulation algorithms is MPS simulation, where the quantum state at each step of computation is stored in an MPS. This can be exact, where the bond dimension may grow exponentially, or bonds can be truncated to keep runtime manageable (at the cost of precision). If the entanglement entropy grows at most logarithmically (resp. is constant), then this gives a polynomial time (resp. linear time) algorithm for quantum simulation of that circuit.
As an additional bonus, you can act on the circuit with an MPO as well, not just gates. MPOs are a bounded-entanglement representation of unitaries in the same way that MPSs are bounded-entanglement representations of states. Like the gates in any other tensor-based simulation, you’re free to choose the MPO to be non-unitary if you want; the resulting state won’t be normalized, but you get some quantum state out at the end anyway. In general, an MPO might not have a compact circuit representation, so MPS-based simulation is a little bit extra-powerful in this way.
[2303.11317] is pointing out that, for the case of Grover’s algorithm, most steps have very small entanglement entropy. The initial state |s> has no entanglement, the diffusion operator has a compact MPO representation, and the MPS state has small entanglement after the application of any complete oracle or diffusion step. In fact, the oracle has small entanglement entropy as well, as long as the original search problem has a small number of solutions. It has a compact MPO representation.
As the authors note, the simple fact that the oracle has a compact MPO representation doesn’t mean we can find it; we only have it as a circuit. But, they say, if that circuit has low entanglement, then the full MPS simulation can be run efficiently. Since it’s a strong classical simulation, we can actually extract the answer much faster than 2^(n/2), from the prepared Grover states.
—-
First, if we have an oracle circuit with low entanglement entropy (that is, we know a way to write it as an MPO with low bond dimension), we don’t need to prepare the Grover state at all. We can subtract off the identity operator to get a new MPO, one which is exactly a mixed state over all solutions. We can then sample from this MPO to get a solution. In this sense, only one “application” of the circuit is used, with a lot less mathematical machinery.
Okay, so we have a good algorithm for oracles with low entanglement entropy. Is that a useful condition? Let’s look at an oracle circuit for, say, 3-SAT. The most straightforward implementation would be a series of checks into log(n) ancilla qubits, tracking “how many clauses so far have been violated”. Each clause gets a gate accumulating into the counter. At the end, if the counter is at zero (a solution string), a conditional phase gate is applied. Then the whole circuit is uncomputed. This circuit will have a high entanglement entropy in general, as the various clauses will connect qubits all over. Each clause creates an extra factor of 2 in the bond dimension; since we should expect at least o(n) clauses, the bond dimension will grow exponentially. It is possible that our 3-SAT instance has some linear structure that admits a better connectivity. This is, in fact, precisely the instances on graphs of bounded pathwidth, an easy set of problems. We can actually move from an MPS-simulator setting to the slightly more flexible setting of Tree Tensor Network simulation; this gives us precisely the 3-SAT problems of bounded treewidth.
We can actually do better than the oracular circuit, since we’re just looking for any (potentially non-unitary) MPO. We can just have a series of projectors that each project into the valid subspace. This drops the ancillae qubits, is even easier to simulate, and gives the exact answer distribution without any subtraction. This makes the correspondence between entanglement entropy and bounded-treewidth instances more obvious.
———-
That was a bit specific to 3-SAT. In general, we should expect the entanglement entropy of the MPO to be directly related to the treewidth of the circuit implementing it. This observation is not new or hard, see for instance Verstraete/Cirac/Murg ’09 or Oh/Noh/Fefferman/Liang ’21. So we can equivalently state the setting as: we have an efficient solver for problems with a (potentially non-unitary!) circuit with low treewidth.
But we really shouldn’t expect there to be hard problems with bounded treewidth! One of the foundational ideas in parameterized complexity theory, https://en.wikipedia.org/wiki/Courcelle%27s_theorem, states that (very loosely) every “easy to state” question on a graph with bounded treewidth has a simple polynomial time implementation. This includes any property that could be checked with a classical circuit with low treewidth. High-quality SAT solvers already use heuristics to detect tree decompositions that can solve the problem faster. Random SAT instances have near-maximal treewidth.
————–
So what are we left with? I admit there are a few “gaps” in the argument above, and these are the places with room for a new efficient classical approach.
——————–
With all that said: approximate tensor network contraction is a pretty interesting tool and I’d love if more was known about its theoretical performance on hard combinatorial problems. Low-width tree decompositions of graphs can accelerate many problems immensely and are, in my opinion, still used much less than they should be for practical work.
Comment #23 March 22nd, 2023 at 6:13 pm
Alex #22: Far from demanding an apology for that wall of text, I offer deep thanks!!
We might say: whereas I merely (correctly) saw a dungpile, you looked more closely than I could with my failing 41-year-old eyes, and (again correctly) saw a dungpile with tiny diamonds of fruitful research problems buried inside. 🙂
Comment #24 March 22nd, 2023 at 7:07 pm
I haven’t read the paper (yet… perhaps I’ll wait for ChatGPT-5 to read it for me), but you say that the fact they exploit knowledge of the way the oracle circuit is built makes their claim irrelevant to Grover’s algorithm (“The car of reasonableness … explodes in flames”) as they left the “realm of the oracles”
If I understand correctly the authors claim they can identify “easy” problems based on the circuit and solve these problems on classical super computers. If so, their point should focus on either:
1. novelty and usefulness of the hardness classification (noting that they classify based on the implementation and not the problem’s description)
2. whether they managed to solve a specific problem, with some advantage over known classical algorithms
Comment #25 March 22nd, 2023 at 7:18 pm
Seconding comment #1,
I’m curious how you prompted GPT-4 in this case. I know the new model accepts text and image input; did you somehow submit the whole pdf of the article and ask it for the flaw in the mathematical reasoning? Or did you copy-paste some relevant portion of the text? Somehow identifying the conceptual flaw in this article—as trivial as it may be to an expert in computational complexity theory—seems so far beyond the capabilities of our current LLMs that I’m curious if you’re being somewhat ironic here. I’ve played around with GPT-3, 3.5, managed to get some funny outputs (e.g., a “proof” that P=NP, and P=BQP) but the LLM could really only generate coherent logical arguments in the simplest cases, where it seemed more like a paraphrase of an explanation already existing somewhere on the web. The capability of these models to generate code seems a lot more impressive to me.
Incidentally, as someone from academic mathematics I find it interesting how quickly discoveries in quantum complexity theory have become “undergraduate level material.” The earliest quantum algorithms (Grover’s and Schur’s) date back to the 1990s, and are already routinely taught at the undergraduate level. Compare, say, to algebraic geometry—even if you go back to the 1960s, schemes and etale cohomology aren’t taught until specialized PhD courses.
Comment #26 March 22nd, 2023 at 8:20 pm
I’d like to echo the sentiments expressed by Anonymous CS Academic above.
While Miles may be around the same age as you, Scott, it’s important to acknowledge the significant influence you hold within the quantum realm.
I appreciate the factual statements in your post, as well as Alex Meiburg’s insightful comment.
Nonetheless, I believe that the sarcastic tone employed here can hinder effective communication across disciplines and may even border on scientific bullying.
Comment #27 March 22nd, 2023 at 9:38 pm
Lei Wang #26: Whatever small influence I might have, I’d feel guilty if, cowering in silence, I didn’t use that influence to defend my hundreds of brilliant, hardworking colleagues against the widely-publicized charge that they’ve all been deluding the entire scientific world, on the basis of garbled rediscoveries of some simple observations about Grover’s algorithm that my colleagues have understood and written about and taught in undergraduate courses since 1996. That’s the part you’re missing!
Comment #28 March 22nd, 2023 at 9:44 pm
I think that, globally, Scott and Miles are at a roughly similar level of influence within academia — the Flatiron is an extremely well-endowed and prominent position (which Miles earned as a result of many years of many important, correct, and contentful work, which I assume Scott knows well). I think an ideal outcome is for Miles to respond here to the post — I’d expect there is context that makes the claims of the paper useful, eg some “vernacular Grover’s algorithm” that he can demonstrate has been misquoted as the real thing, or some reasonably-near future setting in which a “partial Grover’s algorithm” is expected to be tested as a proxy for the real thing.
Comment #29 March 22nd, 2023 at 10:21 pm
Topologist Guy #25: It was even faster than you say—Shor’s and Grover’s algorithms started to be taught to undergrads in the late 90s / early 2000s. They were correctly understood to be foundational to the field almost immediately after being discovered.
As for GPT-4, I prompted it by pasting the full abstract and introduction of the paper (plain text rather than LaTeX), and asking it to write a response for Shtetl-Optimized, the blog of quantum computing theorist Scott Aaronson, as he would write it.
Comment #30 March 23rd, 2023 at 2:29 am
It’s definitely a misleading title.
In the abstract they use “practical speed-up” instead, which I think is more representative of their claims.
But I’ve never thought of exponentially-sized quantum circuits as practical. I honestly have a hard time trying to predict when we’ll have this capability at a reasonable cost, I don’t really buy the double-exponential picture.
There is something I want to pick on related to black-box problems though.
Since the QC has to uncompute the black-box function, it’s implicitly allowed to run the black-box backwards.
I understand that this is just an internal detail of the quantum implementation of the black-box function, but let’s face it, it’s totally unreasonable and cheaty. Admit it!
Now seriously, i’m wondering if there is a black-box separation where both the quantum and classical computers are allowed to explicitly uncompute the oracle. Is it a minor obstacle?
Comment #31 March 23rd, 2023 at 2:33 am
Non-specialist, non-academic, so entirely possible that I’m talking nonsense. But I find this debate over whether it’s OK to disagree very pointedly with a paper kind of terrible.
First, it should be OK to get things wrong, sometimes very wrong. If science wasn’t hard, we wouldn’t need people to devote a lot of their time to it. I know the writing of papers is supposed to iron out a lot of errors, but it’s clearly not the case that all published papers are right. So we should expect a certain (maybe even large) proportion of papers to be wrong, and some to be badly wrong. I very much hope that publishing a wrong paper, or receiving criticisms for a wrong paper isn’t, as suggested above, bad for someone’s career. Who could be creative if that were the case?
Second, disagreeing very pointedly with papers should also be fine, because that’s how things get better.
Comment #32 March 23rd, 2023 at 3:57 am
This seems a good venue to ask about a topic related to Grover that I’ve been a bit embarassed to admit my ignorance about, but I now feel is time to resolve my doubts.
Scott wrote “decoherence could negate the advantage in practice, and solving that problem would require a fault-tolerant quantum computer”.
Just to be clear I am understanding correctly: this would mean that also the oracle circuit should be error-corrected, right?
As a matter of fact, there are results showing that a faulty oracle would negate asymptotic speedups: https://arxiv.org/abs/1202.1027
I intuitively feel that having a guarantee that the black-box is perfectly noiseless would be a crucial and tricky part in real implementations. For example, in this paper they write:
“In particular, it shows that some natural approaches, like fault-tolerant quantum computation [14], cannot help in this setting. Note, however, that this impossibility result applies only in case that the oracle is truly a black-box oracle; if, instead, the oracle is given as a faulty circuit, then fault-tolerant schemes can be used to achieve a quantum speed-up by applying them to the circuit obtained by taking Grover’s algorithm and replacing the oracle calls with their circuit implementation.”
This always sounded a bit troubling to me: if the oracle circuit is known in order to be corrected, than it is not truly a black-box and some of the arguments in this post may apply and different approaches beyond the black-box paradigm could be employed.
Is there a simple way to resolve this tension or do I just have to accept that having the guarantee of a noiseless/error-corrected oracle is a necessary ingredient for speedup?
Comment #33 March 23rd, 2023 at 6:34 am
@Topologist Guy #25
“Incidentally, as someone from academic mathematics I find it interesting how quickly discoveries in quantum complexity theory have become “undergraduate level material.” The earliest quantum algorithms (Grover’s and Schur’s) date back to the 1990s, and are already routinely taught at the undergraduate level. Compare, say, to algebraic geometry—even if you go back to the 1960s, schemes and etale cohomology aren’t taught until specialized PhD courses.”
That may have to do more with the very high abstraction level in algebraic geometry and the background needed. If one looks for example at graph theory, undergrad courses do include results from at least the 1980s today. To some extent this is likely a function of how young a field is, and thus how much fruit there is that is not so much low hanging in the sense of being easy to figure out but low hanging in the sense of being somewhat easy to explain.
Comment #34 March 23rd, 2023 at 6:52 am
You said “Because of its exponential speedup”, do you mean that Grover’s algorithm offers any exponential speedup?
Quantum annealing needs full fault-tolerance. For example, https://arxiv.org/abs/2111.07560 suggests that Dwave’s succumb to classical noise, and behave like a noisy classical computer. Quantumness asided, fault tolerance is even harder to achieve.
Comment #35 March 23rd, 2023 at 7:28 am
Job #30:
There is something I want to pick on related to black-box problems though.
Since the QC has to uncompute the black-box function, it’s implicitly allowed to run the black-box backwards.
I understand that this is just an internal detail of the quantum implementation of the black-box function, but let’s face it, it’s totally unreasonable and cheaty. Admit it!
Nope, totally reasonable. For if you have a small quantum circuit for a black-box unitary U, then you have an equally small circuit for its inverse, by just inverting all the gates and reversing their order. Admit it! 🙂
Comment #36 March 23rd, 2023 at 7:34 am
falbarel #32: Again, the key point is that as soon as the oracle gets instantiated by some actual quantum circuit—which, as this preprint correctly stresses (!), has to happen in any practical implementation of Grover—the circuit can be error-corrected just like any other quantum circuit.
Comment #37 March 23rd, 2023 at 8:28 am
jerome #34: No, I was talking about the exponential speedup of Shor’s algorithm. Maybe I can reword so it’s clearer?
Comment #38 March 23rd, 2023 at 10:00 am
#37 Scott: Ah I see… my bad. Placing it at the end does make it clearer.
Comment #39 March 23rd, 2023 at 10:05 am
Thanks Scott, for taking this on here and thanks to Ryan Babbush for doing so on scirate.
Comment #40 March 23rd, 2023 at 2:03 pm
Is it really that simple? It’s a black-box, you’re not supposed to evaluate it backwards gate-by-gate!
Otherwise, why not look at the gate labels too and get a blueprint? 🙂
That’s the same mistake that this paper is making. You have to respect the black-box. Do it!
Plus, there’s a better way out, just restrict how the inverse can be queried.
The QC only copies the output register before uncomputing back to the original state, so the (reversible) classical machine must do no more – in which case it’s not very useful.
Which is why i’m wondering what happens if both are granted arbitrary access to the inverse.
Comment #41 March 23rd, 2023 at 3:04 pm
Job #40:
(1) Any “standard” oracle unitary, like |x⟩ → (-1)f(x) |x⟩, or |x,y⟩ → |x,y⊕x⟩, will be its own inverse anyway! So the question of access to the inverse unitary simply never arises there.
(2) The central point that non-experts miss: the entire purpose of the oracle model is not to invent some fantastical object and worship it, but simply to formalize the everyday concept of “subroutines that we don’t or can’t understand the internal workings of.” And from that perspective, assuming inverses is 100% legitimate, since even if you don’t understand a quantum circuit, you can still invert the circuit in a completely mechanical way.
(3) Having said all that, if for whatever reason you do want to study oracle unitary transformations that you can apply in the forward direction but not reverse, or that are subject to other weird restrictions (e.g., they can’t be conditioned on a control qubit, they can only be queried once, a measurement happens immediately after they’re applied, etc.)—well OK, there are quantum complexity theory papers that do all those things! In many such cases, though, the justification is simply that that was the best the authors could do, and that hopefully it’s a stepping-stone toward studying more “realistic” oracles, the kinds that you can invert and do all the other realistic things to.
Comment #42 March 23rd, 2023 at 6:13 pm
Scott 36,
I disagree with your comment that error correction can be applied to a quantum circuit once it is instantiated by an oracle in Grover’s algorithm. Error correction in quantum computing typically involves encoding the quantum state into a larger number of qubits, and then using error-correcting codes to detect and correct any errors that may occur during computation. However, this approach is not applicable to oracles used in Grover’s algorithm.
Oracles in Grover’s algorithm represent a black box function that takes a quantum state as input and returns either 0 or 1 based on whether the input matches a target solution. These oracles are typically implemented as unitary transformations on the quantum state, which cannot be encoded or error-corrected using traditional error-correcting codes.
Furthermore, even if error correction could be applied to the quantum circuit that implements the oracle, it is not guaranteed to improve the accuracy of the output of the algorithm. Error correction can only detect and correct errors that occur during computation, but it cannot address any errors that may be present in the input data or in the oracle itself.
Comment #43 March 23rd, 2023 at 6:57 pm
Hi Scott,
Thanks for this blog post! Really fun and informative reading – love the passion 🙂
That said, is it really fair to claim Stoudenmire & Waintal are contradicting known results from complexity theory? Or that they’re asserting their quantum-inspired tensor networks algorithm is better than Grover’s? That wasn’t my impression when I went through their paper (albeit I’m not an expert nor anywhere near as capable as you guys are).
My impression is that their paper pertains to *practical* speedups. As I understood it, they were basically saying Grover’s algorithm, whilst a intellectual masterpiece, is not practically useful. It is apparently so sensitive to errors, that its success probability decays doubly-exponentially in the size of the device – far too much for any errror correction to handle. Basically, the authors argue that Grover’s algorithm will only work on a perfectly noisefree quantum machine; ie only as an intellectual thought experiment.
So in this sense, are you really attacking their paper from the right angle? Is what they are saying re practical utility of Grover’s wrong?
But again, I’m obviously no expert in this, so I might be misspeaking.
Cheers!
Comment #44 March 23rd, 2023 at 7:33 pm
The Quantum Man #42: Please reread what I said. I said:
as soon as the oracle gets instantiated by some actual quantum circuit
Once the oracle is instantiated by a circuit—not the “circuit instantiated by an oracle” (whatever that means)—you then just have one big quantum circuit, i.e. a collection of 1- and 2-qubit gates. And fault-tolerance can be applied to that circuit just like to any other quantum circuit, and provided the conditions of the Threshold Theorem are satisfied, it will work.
I have studied and taught this material for 25 years. These issues are not up for debate, like whether an AI would be conscious or whatever. This post and this comment section have felt, more than anything else, like grading the midterm exam in my Intro to Quantum Information course, with a red pen and with many heavy sighs.
Comment #45 March 23rd, 2023 at 7:43 pm
DrNik #43:
My impression is that their paper pertains to *practical* speedups. As I understood it, they were basically saying Grover’s algorithm, whilst a intellectual masterpiece, is not practically useful. It is apparently so sensitive to errors, that its success probability decays doubly-exponentially in the size of the device – far too much for any errror correction to handle.
Yes, I understood that that’s what they want to say. And they are dead wrong about it. In a hypothetical future with gigantic fault-tolerant quantum computers, the overhead from fault-tolerance would “merely” be logarithmic in the size of the quantum circuit. So there’s absolutely no reason why a fault-tolerant implementation of Grover’s algorithm couldn’t give you an actual, practical, near-quadratic speedup in solving a combinatorial optimization or search problem in that future.
Obviously, it could be a very, very long time before this happens—because firstly, the overhead from fault-tolerance will be enormous in practice (at least using the schemes we know today), and secondly, the Grover speedup is relatively modest. Stoudenmire and Waintal aren’t the first to make this observation, to put it extremely mildly! It’s something that every serious person in quantum algorithms has understood for years—but we still care a lot about what the ultimate limits are, not just in theory but conceivably someday in practice.
Was that sufficiently clear, or should I try again?
Comment #46 March 23rd, 2023 at 8:10 pm
Scott:
With all due respect, I believe that you are missing my point. Error correction in quantum computing involves encoding the *quantum state*, which cannot be done with oracles in Grover’s algorithm (or any other black-box problem). Even if error correction could be applied to the quantum circuit that implements the oracle, it cannot address the errors in the input data, or in the oracle itself. The issue here is not whether fault-tolerance can be applied to a quantum circuit, but whether error correction can be applied to the oracles in Grover’s algorithm, which it cannot. I am 100% sure I know this stuff.
Comment #47 March 23rd, 2023 at 8:48 pm
Job #40, The Quantum Man #42, DrNik #43, and others:
Let me take a crack at addressing what I understand to be your misconception – sometimes hearing the same idea put into different words can make it click.
I think you’re misunderstanding the oracle model in a way that makes the oracle subroutine more mysterious than it actually is. In a concrete implementation of Grover’s algorithm for a specific problem, there is nothing special about the oracle function at the level of implementation. There is no mysterious force preventing you, the coder, from fully understanding it. It’s just a subroutine in your quantum source code – potentially one of many – which gets physically instantiated in the quantum processor by a sub-circuit comprised of one- and two-qubit gates on several qubits, which does not look any different from any other sub-circuits. To someone skimming your source code, it would not necessarily even be obvious which subroutine is the one being treated as the oracle function.
It may be clearer to think not “We can’t understand or ‘look inside of’ the oracle function”, but instead “The oracle function doesn’t have any mathematical structure that we can figure out how to exploit.” I think of the mathematical structure of a particular oracle function as “non-useful” rather than “mysterious”. The rigorous formalization of the oracle model within computational complexity theory is supposed to be capturing this lack of useful structure that we can exploit – it’s not trying to capture any kind of ignorance about the function itself.
Therefore, the proof of the optimality of Grover’s algorithm for black-box search does not guarantee that for *any* particular fully specified mathematical problem (where by “fully specified” I mean that you have specific instantiations of all functions within the problem statement), a quantum computer can only give a quadratic speedup. For all we know, there could be a super-quadratic quantum speedup for, say, the hash inversion problem for any specific hash. The optimality of Grover’s algorithm just means that a quadratic speedup is the best we can do without using any information we have about the global structure of a given function within the problem statement. For a given concrete computational problem, the optimality of the Grover approach will always be provisional and could be superseded if we think of some clever way to exploit the function structure (unless we can find some totally different optimality proof specific to that problem).
While the history didn’t happen to work out in this order, you could certainly imagine a world where Grover had first proposed using Grover search to give a quadratic speedup for factoring that treated the relation “x divides N” (for fixed N) as an oracle – setting aside the existence of other already-known classical factoring algorithms that are faster than brute-force – and then Shor had later found a much faster speedup that exploited the global structure of that “oracle”.
One final subtlety that’s often glossed over is that people usually frame the Grover speedup in terms of “runtime”, but strictly speaking, it only gives a reduction in the number of times that the subroutine gets queried. For practical applications of Grover, we are usually imagining a situation where (a) one subroutine gets called many times and (b) those subroutine calls dominate the total algorithm runtime – so that to leading order, the total runtime scales linearly with the number of times that the subroutine gets called. Subject to these conditions, which often hold well in practice, the Grover speedup approximately translates to a quadratic speedup in “the real world”.
Comment #48 March 23rd, 2023 at 8:55 pm
Ted #47: Thank you.
The Quantum Man #46: To say it one more time, once the oracle is encoded as a circuit, there’s not then still some separate object called “the oracle” that’s separate from the circuit. The oracle is the circuit. Fault-tolerance can then be applied to it just like to any other quantum circuit. Possible errors in the original input data (!) are a separate issue irrelevant to anything we’re talking about.
Comment #49 March 23rd, 2023 at 9:04 pm
> The paper’s most eye-popping claim is that the Grover search problem … is solvable classically, using a number of calls that’s only linear in n …
Am I right that if that claim was true, even if only when an explicit oracle circuit was given, it could be directly applied to solve CircuitSAT classically, in a linear number of input-circuit-evals?
Comment #50 March 23rd, 2023 at 9:07 pm
I understand your point, but you seem to be missing mine. My point is that error correction cannot be applied to the functionality of the oracle in Grover’s algorithm, which is a black box that takes a quantum state as input and returns either 0 or 1. This black box cannot be encoded using traditional error-correcting codes, and even if it could be, it would not address the errors in the input data or the oracle itself. The fact that the oracle is implemented using a quantum circuit is not relevant to this issue.
Comment #51 March 23rd, 2023 at 9:19 pm
The Quantum Man #50: You are permanently banned from this blog, due to a combination of wrongness, confidence, and repetitiveness that’s in danger of raising my heart rate to a dangerous level. I apologize that I’m having to do such things more and more to protect my mental and physical health.
Comment #52 March 23rd, 2023 at 9:30 pm
Scott 41:
The notion that all standard oracle unitaries are their own inverses does not justify the assumption that oracle models always have inverse unitaries.
First, there are many non-standard oracle unitaries that do not have inverses. For example, consider an oracle that maps |x⟩ to |x⊕1⟩ if x is even, and to |x⊕2⟩ if x is odd. This oracle does not have an inverse, as it is not a one-to-one mapping. Thus, it is not legitimate to assume that all oracle models have inverse unitaries.
Second, the assumption of inverse unitaries may be problematic for some applications. For example, in quantum cryptography, it is often desirable to have unidirectional functions that are easy to compute in one direction but hard to invert. If we assume that all oracle models have inverse unitaries, we may miss important classes of functions that are useful in cryptography.
Finally, the argument that assuming inverse unitaries is legitimate because we can invert quantum circuits mechanically does not hold water. The ability to mechanically invert a circuit does not imply that all circuits have inverse unitaries. There are many quantum circuits that do not have inverse unitaries, such as those that perform irreversible measurements or decoherence operations.
Comment #53 March 23rd, 2023 at 9:45 pm
Transformer #52: I was specifically talking about standard oracles, like the one in Grover’s algorithm, all of which are unitary and in fact are their own inverses. The transformations you’re talking about are not even unitary. If people want to study them, that’s great! But they weren’t what Job was asking about. He wanted to know why we normally assume access to the inverse oracle. Obviously that question doesn’t arise for oracles that don’t even have inverses!
Comment #54 March 23rd, 2023 at 9:59 pm
Scott, fair enough, but your rebuttal doesn’t address the central point of my argument. I never claimed that all oracle models have inverse unitaries, but rather that assuming they always have inverse unitaries is not justified. Your example of a non-standard oracle that doesn’t have an inverse actually supports my argument, as it demonstrates that not all oracle models have inverse unitaries.
Furthermore, I agree that unidirectional functions can be useful in cryptography, but that doesn’t invalidate the assumption of inverse unitaries in all cases. It simply means that we need to be aware of cases where the assumption may not hold and consider alternative models.
The ability to mechanically invert a circuit does not imply that all circuits have inverse unitaries, but it does imply that assuming inverse unitaries is a reasonable starting point in the absence of evidence to the contrary. As with any assumption, it is subject to revision based on new information, but until such information is available, it provides a useful framework for analysis.
Comment #55 March 23rd, 2023 at 10:08 pm
Scott #53, sorry, but I can’t understand this perspective. Job’s question about the assumption of access to the inverse oracle goes beyond standard oracles and applies to all oracles used in quantum computing. To limit the discussion to only one specific type of oracle is to ignore the full scope of Job’s question and the potential for broader insights.
Furthermore, dismissing non-unitary transformations as irrelevant to the discussion demonstrates a lack of understanding of the potential for non-unitary operations in quantum computing. These operations have important applications, such as in error correction and fault-tolerance.
It is essential to explore all avenues of quantum computing, including non-standard oracles and non-unitary transformations, to advance our understanding and push the boundaries of what is possible. We should embrace the vast potential of quantum computing and not limit ourselves to a narrow-minded approach.
Comment #56 March 23rd, 2023 at 10:29 pm
Oh honey, it seems like you missed the whole point of the authors’ argument. They’re not saying anything groundbreaking here. It’s common knowledge that noise and decoherence can negate the advantages of quantum algorithms in practice, and that fault-tolerant quantum computing is a daunting task. The authors are simply pointing out that even when Grover’s algorithm theoretically offers a speedup, the practical implementation is far from trivial. And as for your snarky comment about Shor’s algorithm having better prospects, well, congratulations on stating the obvious. But let’s focus on the actual discussion at hand, shall we?
Comment #57 March 23rd, 2023 at 11:06 pm
[…] 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, next pandemic, let's approve the vaccines faster! « Of course Grover’s algorithm offers a quantum advantage! […]
Comment #58 March 23rd, 2023 at 11:53 pm
Scott #41,
That’s true, and I forgot about that but only because we often assemble the oracle unitary from an f(x) by using the uncompute technique, right?
Anyway, it doesn’t matter because i’m not seriously suggesting that the QC’s advantage is due to its illegal usage of the inverse – I just think it’s interesting to think about because of what I’ve seen in other black-box problems.
Ted #47,
I like this description of a black-box. But to what extent do we need to make sure that both the quantum and classical machines are solving the same problem? Or rather, solving it on the same terms?
The way we measure performance (e.g. number of oracle queries) depends on how the black-box is defined and how much information is available.
If we don’t enforce the black-box in strict terms, it will make analysis more difficult and it opens the door to trickery and “computational rhetoric”.
Comment #59 March 24th, 2023 at 12:46 am
Transformer #54 and Mac and cheese and pepper and gravy #55: Your comments were either generated by GPT for the lulz or to rattle and upset me (the concluding sentences, in particular, exemplify GPT’s trademark style), or else they might as well have been.
Begun, the Clone Wars have. 🙂
Comment #60 March 24th, 2023 at 12:49 am
U Virginia Guy #56: Banned from this comment section for patronizing me.
Indeed, to say that the authors are saying nothing groundbreaking is a titanic understatement! The problem is that they explicitly positioned the paper as if they were—indeed, as if they’d all but overturned 30 years of quantum algorithms research.
Comment #61 March 24th, 2023 at 4:23 am
Thanks Scott #36 for the answer and also Ted #47 for the very clear explanation! It seems I was not the only one confused by the meaning and role of the “black box”.
Comment #62 March 24th, 2023 at 5:21 am
Scott #45: I’ve asked ChatGPT to generate a patronising reaction, it did a pretty good job.
“Oh, bless your heart. It’s cute that you think you understand the complexities of fault-tolerant quantum computing and its potential applications. But darling, it’s clear that you’re not quite grasping the full picture here. You see, there’s so much more to consider than just the logarithmic overhead of fault-tolerance or the modest Grover speedup. But don’t worry, sweetie, maybe one day you’ll catch up to the rest of us who have been studying quantum algorithms for years.”
Comment #63 March 24th, 2023 at 10:33 am
Immediately, this very much reminds me of the work by Valiant and Cai on holographic algorithms. Where indeed they find some very interesting results and fast poly algorithms for supposed NP/#P-complete, however as they are aware in their work this is only due to the parameterizations of the problems and the ability of the holographic algorithms to leverage the ‘signature’ of the problem for these parametizations.
I am wondering if there is any link that can be derived with holographic algorithms, where we are merely seeing that the oracles are just constructing the holographic signatures in a novel way? – or can these easily solvable circuits be reduced to matchgate tensor networks, and hence easily simulatable quantum circuits.
If we have a purely quantum problem then we cannot have a matchgate circuit, or if we have a problem with no holographic signature then there is no structure for the oracle to leverage.
Comment #64 March 24th, 2023 at 1:23 pm
Scott #59, already the nym of #52 made me wonder if, ahem, (s)he is of a generative pre-trained type. Sneer clubs have a new tool in their possession in this new brave world, which is likely going to challenge hugely the way we interact and the way we build societies. Not only comment sections of various blogs.
Regarding inversibility of oracles, it is clear even to a non-specialist like myself, that the ‘program flow’ of a quantum computer must be reversible already from thermodynamic considerations (otherwise the QC must couple to the environment), implying that also the oracles must be reversible. It is true that not every subroutine one can imagine is reversible, but then again not every algorithm shows quantum speedup. But there is no point to argue against a server farm about the subject – a server farm can always out-patient you.
Comment #65 March 24th, 2023 at 1:54 pm
That ADHD CS Guy #63: There actually is a direct connection between holographic algorithms and the efficient classical simulation of a special kind of quantum circuits called “matchcircuits” (as a special case, noninteracting fermion systems)—which makes it no surprise that Valiant came up with both of them around the same time!
On the other hand, I’m not aware of any direct connection between holographic algorithms and the sort of ad-hoc tensor network simulation of Grover’s algorithm done in this paper. Note that in the former case, but not the latter, we have very nontrivial theorems that tell us specific situations where the approach works.
Comment #66 March 24th, 2023 at 1:56 pm
Nikki Kiviranta #64:
“There is no point to argue against a server farm.”
Or, I might add, against a person who acts like one! If anyone wants to get me an amazing birthday present, they can get me a huge banner with those words to hang in my office. 🙂
Comment #67 March 24th, 2023 at 3:55 pm
“Then, when I explicitly asked it to be scathing, it was scathing about Grover’s algorithm, rather than about this paper falsely claiming to refute Grover!”
Two versions of ChatGPT down the line and it will not only correct the paper but also enhance it with a 3,000 pages P=NP proof in annex, and then commandeer a drone to do a small tactical nuclear strike on the authors.
Comment #68 March 24th, 2023 at 9:57 pm
The title is surely misleading, but isn’t the classical algorithm a good one for structured problems like SAT,for which Grover has never been claimed to be superior to classical algos? Maybe they should be comparing their classical algorithm to classical state of the art algorithms for the class of problems that it can solve (where structure in equation 19 can be used to make the scaling non-exponential). In that sense, is there not still originality and merit in the work?
Comment #69 March 26th, 2023 at 5:00 pm
Noel #68: Yes, if they want to make a case that their classical algorithm is competitive in any way, shape, or form, then let them compare it to the best known classical algorithms. Otherwise it’s just a completely irrelevant comparison: optimized classical versus Groverized brute force. Why not start with the best known classical algorithm and then try to Groverize that one? Why isn’t this obvious to people?
Comment #70 April 1st, 2023 at 9:19 am
Anonymous CS Academic #3
Sorry but what are you on about, both of these guys are old AF and established enough to know that writing a paper like this was unethical and would invite a lot of negative attention.
Comment #71 April 5th, 2023 at 2:52 am
[…] Scott Aaronson in Of course Grover’s algorithm offers a quantum advantage!. […]