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 depth and IBM Quantum, anyway, will give you the maximum runtime for any circuit run on that particular device. Simply compare that maximum runtime to the classical runtime.

This second technique is even simpler: it is the number 50.

In my article titled, “Maximum Quantum Classification,” I tried to really push the limits of the IBM Quantum simulator. TL;DR again: a circuit with 23 qubits and 51 Fredkin gates took 2 hours, 18 minutes, 5.9 seconds to run. A circuit with 24 qubits and 54 Fredkin gates resulted in a runtime error.

But, that’s just a free, online quantum computing simulator using 23 simulated qubits and using reset gates to simulate having more simulated qubits. It is estimated that the world’s most powerful supercomputers can only simulate quantum systems with up to around 50 qubits. Google’s “Quantum Supremacy” experiment used 53 qubits and fell just short of its goal. However, the consensus (outside Google) is that 54 or 55 qubits would’ve made the outcome indisputable.

Going back to my favorite quantum classification algorithm, I have read an estimate by MIT and Xanadu researchers that quantum advantage may be demonstratable at around 101 qubits, with 1 ancilla qubit being used to compare 2 50-qubit systems.

There is that number 50 again. And, if that isn’t enough, 50 Fredkin gates would be required.

Putting it all together, if your classical algorithm runs in less than a minute and your quantum algorithm uses five qubits, you can probably save yourself some time doing the calculations. If your classical algorithm, however, is slower than 200 seconds (using Google’s runtime) and your quantum state needs at least 50 qubits, I look forward to reading your paper!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store