Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Assume $f(x)$ is n-bit to n-bit function. Let $F(x)$ be defined as $T$ iterations of $f(x)$, i.e. $F(x) = f^T(x)$.
Quantum algorithm relies on $F(x)$; it calls it $R$ times. What is the best query complexity of the algorithm in terms of calls to $f(x)$:
Can we do better than $R \cdot T$ queries while maintaining negligible quantum memory complexity?
Can we do better than $R \cdot T$ queries with additional quantum memory? If so, then how much? Can we do less than $T$?
That really depends on the function $f$ and the size of $R\cdot T$. Generically, I don't think that you can expect improvements over $R\cdot T$, but improvements are possible in some special cases.
For example, with the function $f$, there's a similar question in classical, and there are instances where speedups are possible, such as modular exponentiation: $f(x)=x\text{ mod }N$. There are better ways of calculating $x^a\text{ mod }N$ than just calculating $F^a(x)$, but it's specific to that function.
If you want really large $R\cdot T$, or non-integer values, there are quantum algorithms based on phase estimation. You want to have a look at this paper.
