7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It seems like you wrote "Shor's algorithm" (whose purpose is to factor an integer) instead of "Grover's algorithm" or "amplitude amplification" (which seems to fit better with your explanation). $\endgroup$ – Nelimee Jul 12 '18 at 12:26
  • $\begingroup$ @Nelimee Let me read op on the differences and correct them in question if need be. $\endgroup$ – Nightwolf Jul 12 '18 at 12:39
  • $\begingroup$ @Nelimee It seems you are right will update question. $\endgroup$ – Nightwolf Jul 12 '18 at 12:40
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What I did not mention in the question was that I wanted to know if a quantum computer could brute force today's public and private key crypto-security at a constant speed. Marked as correct because you answered the question as is, thoroughly. $\endgroup$ – Nightwolf Jul 16 '18 at 6:19
  • $\begingroup$ @Nightwolf It's essentially the same answer. There, you're generally talking about Shor's algorithm, which will have a deterministic running time. However, there are a couple of places in the algorithm that only work with high probability. So you do have to repeat until success, potentially requiring a small number of repetitions. $\endgroup$ – DaftWullie Jul 16 '18 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.