How to construct this oracle quantum gate?

Question

I was reading the paper Quantum Computational Complexity in the Presence of Closed Timelike Curves.
In this the author mentions that following quantum oracle gate which operates on $n+1$ qubits, can be constructed with $p(n)$ gates, where $p(n)$ is some polynomial in $n$.
$$U_{f}=\sum_{i=0} ^{2^{n-1}}|i\rangle \langle i| \otimes \sigma_{x}^{f(i)}$$ Where $\sigma_{x}$ is Pauli matrix $X$ and $f:\{0,1\}^{n} \to \{0,1\}.$

How do I go about proving it. And what does polynomial number of gates mean. If suppose I prove that the above gate can be achieved using $n^2$ gates, I can club all the gates into one big gate and say it is done in a constant gate (i.e. one gate).

Answer 1

Good look trying to prove what is the specific polynomial, not even the author was capable to do it. Usually what you can show, and is important, is that that the number of gates, or the time to compute, or something else grows at most at a polynomial rate, as opposed to an exponential rate which in computer science means is a tractable problem (that is, the complexity does not grow too fast with the number of variables and is thus not a "hard" problem). Regarding the issue of clubbing the gates, that is incorrect, clubing many quantum gates does not result into "one" gate.