On the complexity of an oracle for a classical function

Question

Let us assume that we have a classical function $f:\{0\,;\,1\}^n\to\{0\,;\,1\}^m$ which is efficiently computable. Then, its oracle is defined with $\mathbf{U}_f\,|x\rangle\,|y\rangle=|x\rangle\,|y\oplus f(x)\rangle$. I quite often read that if $f$ is efficiently computable, then so is $\mathbf{U}_f$. Why is it the case? Where is the computational cost of evaluating $f$ taken into account?

Since $\mathbf{U}_f$ is a permutation matrix, one can implement it with at most $2^{n+m}$ SWAP gates, but this is not very efficient. What am I missing?

Another related question is: given a permutation matrix, how can one find the appropriate CNOT/SWAP gates succession to implement it? Even if an efficient solution exists, how does one find it?

Answer 1

There are several different issues all bundled together here.

First is the concept of classical universality: whatever gate set you choose to specify your classical algorithm in terms of, there's a polynomial conversion to any other gate set. This includes a gate set that comprises reversible classical gates (such as Toffoli). For this, you just need to find a constructive conversion between the two gate sets. So, you can efficiently implement the reversible computation. It also means that you can efficiently implement it on a quantum computer, just by using the quantum computer's version of Toffoli as compared to the classical version (the only difference being that the quantum version accepts superpositions as inputs).

However, the terminology that you're using is one of oracles. The oracle model is different. There, each use of the oracle counts as "1", and you don't count any other gates. You're accepting that the cost of implementing the oracle is (relatively) high to the extent that it's the dominant source, and so the only relevant question is how many times you use the oracle. Part of the point here being that somebody could come up with a different gate sequence for the oracle that takes a different running time, but that doesn't affect the oracle-based analysis.