Does a fully working quantum computer solve a specific problem at varying speeds every time?

Question

Lets say we have a fully working quantum computer. I give it a problem to solve and measure how long it takes to solve it. I repeat the process. Would it take the exact same time to solve the same problem?

I have read that a quantum computer's solution process could be seen as all the potential answers are already calculated but to get it out of an entangled state without changing the result, you would use Grover's algorithm that reduces the answer set. You then repeat Grover's algorithm to keep on reducing the answer set. Now you could repeat Grover's algorithm to get a single answer or just start up classical computing to test answers once the answer set is small enough.

This could possibly mean that the same problem could have a different answer set on first iteration of Grover's algorithm which could cascade on how many times it needs to run to get to a reasonably small answer set to test with classical computing.

Did I misunderstand something or is it reasonable that same problem could have varying calculation time on same hardware?

Answer 1

It depends upon the algorithm that you're running as to whether it will always take the same length of time to run or not. Many of the well-known (often oracle-based) algorithms, such as Deutsch-Jozsa have fixed running times, i.e. they will always take the same time to run because it is exactly the same steps that have to be run every time.

Other algorithms (Simon's, Shor, HHL, Grover...) have some probability of failure, but a way of easily recognising a correct answer. So, if it fails, you just repeat. This means that there's a discrete set of running times, and an expected running time.

However, I must emphasise that your understanding of how quantum algorithms work is not very accurate.

I have read that a quantum computer's solution process could be seen as all the potential answers are already calculated but to get it out of an entangled state without changing the result, you would use Grover's algorithm that reduces the answer set.

Usually, you do not use Grover's algorithm, unless the specific thing you're doing is a quantum search (or a related set of applications). Even Grover's is almost deterministic (if the number of solutions is known). As the size of the set you're searching over increases, the probability of failure tends to 0 so, to all intents and purposes, you run the algorithm exactly once and effectively have a deterministic running time.

While the first step of a quantum function can generally be thought of as calculating all possible answers in parallel, the secret sauce of quantum algorithms is very much the special tricks that can be leveraged to get a sensible answer out (for the very limited set of problems for which we know such tricks). But these depend extensively on the specific structure of the problem being solved. Grover's search is kind of the brute force option: if all you know about the problem structure is that you'll be able to recognise an answer when you get it, Grover's the one you want, but the point of quantum algorithms generally is to use further properties of the problem structure and get much greater speed-ups.