Would quantum computers be more efficient at solving circular reference problems than classical computers?

Question

A circular reference is when a certain value either refers to itself or a value refers to a value that refers to it. An example of a circular reference problem would be $x=f(x)$. One way to solve such a circular reference problem would be to start with a random guess for x, find the value of f(x), and then have $x_{n+1}=f(x_n)$ until a certain numerical condition is met. Using this method it's possible that the first guess for x would satisfy the given numerical condition and going onto another iteration would be unnecessary.

I understand that quantum computers could solve some problems more efficiently than classical computers as they can perform multiple calculations at the same time, but in order for that to be useful the wrong answers need to destructively interfere with each other.

Would circular reference problems be something that quantum computers could solve more efficiently than classical computers?

Answer 1

Yes - you can use Grover search to speed up finding an element $x$ which satisfies $x=f(x)$.

It is clear that for an unstructured function, this cannot be done faster than by $O(N)$ queries classically, and it is also clear that this can be solved using Grover search in $O(\sqrt N)$ steps.

On the other hand, for an unstructured function $x$ I'd argue that this is optimal, since being able to find an element $x=f(x)$ can be used to find a "marked" element $g(x)=1$ in a database (by building a suitable function $x$).