Hi Frank! This is a great question; the answer is sometimes simple and sometimes baffling.
Frank Röber wrote: For the following, let's ignore the noise of real existing systems. Im talking of an ideally QPU.
I agree that this is useful. Considering a fault-tolerant QPU lets you focus on the issue, not the noise. And we'll have those soon enough. Here's a
link to the company I work for, which is building one such device.
Frank Röber wrote:For the following, let's ignore the noise of real existing systems. Im talking of an ideally QPU.
If I know there is only one result, the candidate should be clear after let#s say 10 cycles. But this is just a feeling, I cannot evaluate the error rate.
If there're two expected results (e.g. root-finding like Newton), how many cycles would I need to become confident about the result? It gets worse if there are more roots I didn't expect...
My statistics is also patchy, but if you know there's one correct answer, and a 98% chance of getting the right answer with one run, then there's a 1.0 - 0.02*0.02 = 99.96% chance that at least one of two runs will be correct. So that's also about the probability (seat-of-the-pants leap of logic here, someone please correct me) that if you do see two identical results, the answer you see is correct.
However there's a big (huge) help when it comes to many common algorithms: I's often hard to find the answer, but easy to verify it. For example, in the
Shor chapter of the
octopus book, the program produces factors of a number, so simple multiplication will tell you whether or not you need to re-run it.
In Figure 10-8 of the
Quantum Search chapter you can also check the answer, but doing so requires possibly getting eaten by a tiger.
Frank Röber wrote:As a QPU programmer, will I have to code that cycles explicitly or is this hidden by the device?
Both. For example, when using the IBM 5Q (as in the
Quantum Teleportation chapter of the
octopus book) you can specify a number of runs, and it will aggregate the results for you (see Figure 4.5). If you need to modify the program based on output from each previous run, then you'll need to run them one at a time.