What level of "confidence" of the result from a quantum computer is possible?

Question

At a very basic level, reading or measuring a qubit forces it to be in one state or the other, so the operation of a quantum computer to gain a result collapses the state into one of many possibilities.

But as the state of each qubit is probabilistic, surely this means the result can actually be any of those possibilities, with varying likelihood. If I re-run the programme - should I expect to see different results?

How can I be sure I have the "best" result? What provides that confidence? I assume it cannot be the interim measurements as described in this question as they do not collapse the output.

Answer 1

The majority of useful/relatively efficient algorithms¹ for quantum computers belong to the 'bounded-error quantum polynomial time' (BQP) complexity class. By this definition, you want the 'failure rate' of any quantum algorithm to be $\leq\frac{1}{3}$, or $\mathbb{P}\left(\text{success}\right) \geq \frac{2}{3}$, although the result may still be within some small error. A non-probabilistic algorithm (that can run in polynomial time) will still be in this complexity class, with the only difference being that it always returns the correct result².

However, as you can run an algorithm an arbitrary number of times, this is equivalent to having a success probability of at least $\frac{1}{2} + n^{-c}$ for an input of length $n$ and any positive constant $c$.

So, the 'correct' result is the one that appears at least two thirds of the time, unless you want a 'one-shot' computation such as if you want to generate random numbers, or if you want to do something such as benchmark the quantum chip, where the statistics matter and are part of the 'result'.

Aside from these (or other algorithms that don't have a single 'correct result'), if you find an algorithm with a success rate below a half, it is no longer 'bounded error' and it may not be possible for the user to know the correct result - there may simply be a wrong answer with a higher probability of occurring than the correct one.

Yes, you may see a different result each time you run a calculation. The confidence in the result is provided by:

1. The quantum algorithm itself ensuring that the correct result happens with high probability and;
2. Repeating the algorithm a number of times in order to find the most probable result.

---

^{1 Here, algorithms that can be computed in polynomial time to give a solution with 'high probability', although for the purposes of this answer, the time complexity is of lesser importance}

^{2 Well, idealistically, at least}

Answer 2

Elaborating somewhat on Mithrandir24601's response —

The feature you're worried about, that a quantum computer might produce a different answer on the next run of the computation, is also a feature of randomised computation. It is good in some ways to be able to obtain a single answer repeatably, but in the end it is enough to be able to obtain a correct answer with high enough confidence. Just as with a randomised algorithm, what is important is that you can be sure of the chances of getting the correct answer in any given run of the computation.

For instance, your quantum computer might give you the correct answer to a YES / NO question two times out of every three. This might seem like a poor performance, but what this means is that if you run it many times, you can simply take the majority answer and be very confident that the majority rule gives you the correct answer. (The same is true for normal randomised computation as well.) The way that the confidence increases with the number of rune, means that so long as any one run gives an answer which has significantly more than just a 50% chance of being correct, you can make your confidence as high as you like just by doing a modest number of repeated runs (though more runs are required, the closer the chances of a correct answer in any one run are to 50%).

In theoretical terms, we give the name BQP to the collection of problems which are solvable in $\mathrm{poly}(n)$ computational steps by a quantum computer, for input sizes which can be specified by an $n$-bit string, where the answer is correct with probability at least 2/3; by the argument above, the exact same set of problems is given if you demand that the answer be correct with probability 999/1000, or (1 − 1e-8).

For problems which have more elaborate answers than YES / NO questions, we can't necessarily assume that the same answer will be produced more than once so that we can take a majority vote. (If you are using a quantum computer to sample from an exponential number of outcomes, it is possible that there are some smaller but still exponentially many quantity of answers which are correct and useful!) Suppose that you are trying to solve an optimisation problem: it might not be easy to verify that you have found the optimal solution, or a nearly-optimal solution — or that the answer that you've gotten is even the best that the quantum computer can do (what if the next run gives you a better answer by chance?). In this case, what is important is to determine what you know about the problem, whether there is an independent way to verify a solution (is your problem in NP, meaning that you can in principle efficiently check any answer you're given?), and what quality of solution you would be happy with.

Again, this is all true for randomised algorithms as well — the difference being that we expect quantum computers to be able to solve problems that a randomised computer alone could not easily solve.

Answer 3

After introducing Shor's algorithm to an audience, in many of Scott Aaronson's publicly available lectures from the mid-2000's until the early-mid 2010's he would often emphasize the gap between the theoretical capabilities of a quantum computer vs. the engineering difficulties of constructing a quantum computer by stating something to the effect of "a quantum computer has determined that $15$ factors into $3\times5$... with high probability."

It's a good line especially with Aaronson's well-timed beat, and the audience always seemed to chuckle at least a little bit, but of course we all know that that's a small oversimplification of the probabilistic nature of Shor's algorithm.

That is, it's rather that Shor's algorithm would tell us that "a factor of $15$ is $3$ with high probability, and another factor of $15$ is $5$ with high probability." We can classically confirm that $15=3\times 5$, now that Shor's algorithm has told us what some factors are (with high probability).

In other words, as suggested in Niel de Beaudrap's answer, $\mathsf{FACTORING}$, like many problems to which we believe a quantum computer will be useful, are in $\mathrm{BQP}\cap\mathrm{NP}$. We might rely on the randomness of $\mathrm{BQP}$ to generate candidate solutions but we can always test classically whether the quantum computer's putative solutions are correct.

There are, however, many problems which are in $\mathrm{BQP}$ but are not known to be, and are suspected not to be, in $\mathrm{NP}$ - for example, evaluating a Jones polynomial of a knot diagram.

(I know that there are two great answers already; however, the question does allow exposition/clarification on Aaronson's quote/anectdote.)