There’s more than one kind of “quantum advantage.”
The recent paper “SupercheQ: Quantum Advantage for Distributed Databases” left me headscratching, but I thank the Infleqtion team for helping me sort my synapses.
Dazed and Confused
I focused too much on phrases like: “the quantum advantage is achieved by random circuit sampling, thereby endowing circuits from recent quantum supremacy and quantum volume experiments with a practical application.” My impression was that you take classical bits, classically compress them, classically encode them, and then quantumly compare them (my favorite quantum thing to do, actually). But, compression and encoding take time. It seems it would be faster and easier to just compare the bits as they come in. It’s one of the quickest things a CPU can do, and you might as well correct errors on the fly while you’re at it. The whole quantum aspect of it seemed unnecessary, including the Google-inspired circuit upon which I thought “advantage” was being claimed.