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$
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.

| improve this answer | |
$\endgroup$

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.