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


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

  • $\begingroup$ I know the author has not proved it,thats why i asked otherwise i would have understood froom the paper.And never mind i showed it equivalent to another unitary transformation which is polynomial in execution time $\endgroup$ Sep 19, 2014 at 9:41

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.