Quantum Advantage for Computer Scientists

A Second Estimation Technique

In my article titled, “Benchmarking Quantum Advantage,” I wrote about a non-mathematical way to determine if your quantum algorithm can outperform its classical counterparts. TL;DR: notwithstanding queue times, quantum processors have a range of minimum-to-maximum runtimes; the classical algorithms need to at least be slower than these benchmarks. To impress anybody, they probably need to be much, much slower, but, again, you can initialize the maximum number of qubits and add a ridiculous amount of circuit…