3
$\begingroup$

Curious to understand if I run for loop within a quantum algorithm, and lets say I want the quantum algorithm to run in classical run time of O(1). Can this be done?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

No, quantum computers can't run for-loops faster in general.

There are certain specific tasks that can be done using a for-loop that can instead be done in a different way on a quantum computer, with fewer total operations. For example, Grover search can replace the loop for x in range(N): if predicate(x): y = x with something that uses $O(\sqrt{N})$ calls to predicate instead of the $N$ that the for loop is using.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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