To say it one more time: no evidence has been offered, here or elsewhere, that QAOA should give *any* speedup compared to just running Schnorr’s algorithm on a classical computer. This is the actual core of the matter. No number of irrelevant experiments and papers—not 2, not 100, not a million—let the hypesters “win by attrition” without answering it!

This alternative is called “Digitized-counterdiabatic quantum factorization” DCQF. Although using trapped-ions appears to currently reach limits for factoring around 128 bit numbers, they suggest current neutral atom systems have promise for DCQF and larger numbers.

Sure, we still are not seeing a quantum speedup of Schnorr’s compared to running Schnorr’s on a PC. But, the point is understanding if benefits from DCQF can scale as NISQ systems grow. The authors, based on their understanding, seem convinced on the potential.

]]>Is this something that one can be genuinely excited about, for a change? (I mean, excited in a positive way!) ]]>

“I am a square Humanities person who’s discovered a love of math in the last year”

Looks like I caught the same disease some years ago, and if you’re interested these are some of the resources that helped me a lot:

https://webspace.science.uu.nl/~hooft101/theorist.html

https://theoreticalminimum.com/

https://www.feynmanlectures.caltech.edu/

Would you mind giving me a minimum idea of the prerequisites for your book on Quantum Computing since Democritus? I was rather keen on giving it a go this year – New Year’s Resolutions.

As to my background, I am a square Humanities person who’s discovered a love of math in the last year, but am still catching up. Right now, I have self-taught myself all high school math and starting with some of the undergraduate stuff (some basic set theory, logic and very elementary abstract algebra and number systems).

Best greetings,

M.

]]>That is, I take a factoring problem P1 and write it as a combinatorial optimization problem P2 (say, 3-coloring). I then can certainly solve P2 much faster with a quantum computer, by first extracting the underlying factoring problem P1, applying Shor’s algorithm, and putting the answer back into P2-form. There is an implication that, since my quantum computer can solve all of these P2 problems, I’ve demonstrated that quantum computers are super-polynomially better at 3-coloring than classical computers.

The authors do not quite make such a claim, but they come very close:

> we prove that fault-tolerant quantum computers feature a super-polynomial advantage over classical computers in approximating solutions to combinatorial optimization problems.

Is this cargo cult combinatorial optimization? Or something else?

]]>“Although “Cargo Cult” is an excellent descriptive adjective for results where there is actually nothing there, it does lack that certain “Latin sound” traditional in scholarly words”

Well both cargo and cult are words that come from latin tbh… cargo is from “carricare” (italian “caricare”,to carry, first person “io carico”, with the same spelling but as a noun “carico”= payload). Cultus is also a latin word 😉

It seems to me that it is a widely accepted expression in science, given its origin 🙂

]]>