I would like to write a code to demonstrate an advantage of QC over classic computations. However, I'm really struggling to find the simplest example for a broad audience. Can someone suggest an example? For instance, will implementation of the Grover's algorithm for finding number 3 in randomly reshuffled list of numbers 1..100 be a good example? Not sure, but maybe some other simple(er) examples already exist.
1$\begingroup$ But QCs do not have an advantage over classical computations. A classical computer would find the number 3 in the randomly shuffled list of numbers 1..100 much faster than any existing quantum computer. $\endgroup$– user1271772Feb 28 at 17:35
1$\begingroup$ Hi qwerty, I think you mean an speedup in principle right? Rather than actual advantage achievable with current technology? You can show on paper that Grover's algorithm offers a speedup over classical search algorithms. However you can't yet beat classical computers with Grover's algorithm as the quantum computers themselves are not advanced enough to run it for a large enough search problem. $\endgroup$– CallumFeb 28 at 18:28
$\begingroup$ I'd think Quantum Teleportation might catch your audience's attention. Not only does the algorithm have a super cool name, entanglement itself is sure to amaze. It amazes me every time I think about it. $\endgroup$– rhundtMar 1 at 1:55
$\begingroup$ @rhundt how does it demonstrate the advantage of QC over classical computers though? $\endgroup$– user1271772Mar 1 at 2:41
$\begingroup$ Yeah... it is still cool and sure to impress the audience, though. $\endgroup$– rhundtMar 1 at 15:51
On current noisy QC it is hard to show any advantage over classical computers. Concerning Grover algorithm, it was shown (see here) that any algorithm promising quadratic speed up cannot reach it on a noisy device. Consequently, algorithms promising exponential speed ups like Shor or HHL will not work either
For you demonstration however I would recommend Deutsch-Jozsa algorithm. Although of a little practical importance it nicely shows power of quantum computers in some tasks.