Best query and memory complexity for iterated function

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)$$:

1. Can we do better than $$R \cdot T$$ queries while maintaining negligible quantum memory complexity?

2. Can we do better than $$R \cdot T$$ queries with additional quantum memory? If so, then how much? Can we do less than $$T$$?

1 Answer

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.

• thanks. how about 2. ? Jun 3, 2019 at 3:47
• @la_guesso34 I am not aware of any results in that direction. It is easy to imagine time improvements via parallelism, but probably using the same number of queries. Jun 3, 2019 at 5:37
• The logic is as follows: Unitary operator describing $f$ is simply a matrix M. Then $f^T$ is $M^T$. So, to apply $F$ we just need to apply $\tilde{M} = M^T$. Jun 4, 2019 at 2:38