Sigh, this paper is extremely misguided. It gets two things egregiously wrong (not in the sense of a math error, although the math is barely worth reading), but in the sense of fundamentally misunderstanding what it's talking about.<p>1. A quantum computer is not a magic exponentially parallel computer. There's a fairly common misunderstanding of quantum computers that goes like this: a quantum state is a superposition of classical states. So a classical number with n bits of RAM is in one of 2^n states, but a quantum computer is in <i>all of them at once</i>, with an "amplitude" that takes the form of a complex number associated with each state. And you can compute things exponentially faster because you can compute with this whole 2^n-element vector at once!<p>This is just a tiny bit true (you can, in fact, write the state of a quantum computer like that), but quantum computers do discrete operations, you can't read the vector directly and, in general, you can't actually get this magic factor-of-2^n speedup naively, nor can you get any speedup at all unless you are doing something clever.<p>But, for some reason, this paper buys into this myth with its quantum-inspired classical algorithm. It's magic! You compute the Grover oracle and get:<p>|s> - sum over all n-bit "winner" strings w_i (|w_i>)<p>And the form of that expression barely matters, nor does whether I transcribed it right or whether you read it right. Because, if you can literally just look at the coefficients (of which there are 2^n!), you can easily find all the "winners". And that would take, shocker, 2^n guesses on a regular computer, or O(2^(n/2)) on a quantum computer with Grover's algorithm. So they've invented a really stunningly bad way to implement brute-force search on a classical computer using fancy math, and you would do much better trying to solve SAT by simply checking each possible input one-by-one. News at 11.<p>2. They have entirely missed the point of quantum error correction. Here's the classical analogue, as observed by John von Neumann in 1956 [0]: if you build a computer (or a brain!) out of unreliable components, then, as you do a longer an longer computation, the chance that you get the right answer seems like it would decay exponentially or worse. But our brains work pretty well and computers work pretty well! von Neumann proved that it is possible to design an computer out of unreliable parts that is nonetheless reliable by inserting error correction steps regularly in a carefully arranged way. (Of course, modern semiconductor technology is so amazingly good that you can get quite far with no error correction. Although we're at the point that you need ECC RAM for really good results.) What you <i>cannot</i> do is run a computer that screws up each gate with, say, probability 0.001%, carelessly run a calculation of any appreciable length, and expect any reasonable chance of getting the right answer.<p>Again, news at 11 -- this stuff has been known since at least the 1950s.<p>In quantum computing, the situation is exactly the same, except the numbers are worse and the error correction is a lot harder. No one expects quantum gates to ever be nearly as good as a CMOS gate. Nonetheless, Peter Shor and others proved the threshold theorem [1], which shows that you can take a quantum circuit and implement it (with more memory and more gates!) in a way that increases complexity only by a polynomial factor and gets the right answer arbitrarily close to 100% of the time. This is really cool! But you have to error correct your memory, and you have to error correct the calculation as you do it.<p>So this paper somehow missed the entire point, computes the degree to which the algorithm is sensitive to noise if you run the whole thing without error correction, determines that the output is not even close to correct, and gives up. No kidding! The fact that this doesn't work has been known for about as long as anyone has been thinking about quantum computers at all. It would be like running a year-long calculation without ECC memory and expecting that you can make up for the lack of ECC memory by simply repeating the calculation until you get lucky and get no errors. Nope, doesn't work.<p>edit: Huh, Appendix C of this paper acknowledges the existence of something vaguely resembling the threshold theorem, and then proceeds to do a calculation showing that a particular (asymptotically suboptimal) construction isn't good enough to make Grover's algorithm useful. I'm not impressed. Maybe paper's title should be changed: "A badly implemented quantum algorithm may not outperform an totally ridiculous classical algorithm, but we didn't bother to analyze the classical algorithm very well and we are merely hypothesizing that there exist problems for which it's better than exhaustive search."<p>[0] <a href="https://www.degruyter.com/document/doi/10.1515/9781400882618-003/html" rel="nofollow">https://www.degruyter.com/document/doi/10.1515/9781400882618...</a><p>[1] <a href="https://en.wikipedia.org/wiki/Threshold_theorem" rel="nofollow">https://en.wikipedia.org/wiki/Threshold_theorem</a>