Can the oracle for $f:\{0,1\}^n \rightarrow \{0,1\}^m$ be implemented with only $n+m$ qubits?

Question

(Part 1: Required ancilla qubits for a given function's oracle)

The question is that given a Boolean function $f:\{0,1\}^n \rightarrow \{0,1\}^m$, how many ancilla qubits are required to build its standard oracle $\mathcal{U}_f$, that is, $\mathcal{U}_f|x\rangle|y\rangle = |x\rangle |y\oplus f(x)\rangle$.

Last time, the answer I was given was $O(N)$, where $N$ is the number of gates required to build a circuit calculating $f$. This is shown by Bennett's algorithm for circuit construction, where every NAND gate is transformed into a Fredkin gate and ancilla qubits.

Thinking about it more, however, I concluded that NO ancilla qubits are required, that is, the above oracle can be implemented using exactly $n+m$ qubits. Here's why:
Any unitary matrix can be implemented (or arbitrarily approximated) with universal gate set. For the oracle described above, $\mathcal{U}_f|x\rangle|0\rangle = |x\rangle|f(x)\rangle$ and $\mathcal{U}_f|x\rangle|1\rangle = |x\rangle |\neg f(x)\rangle$. Thus, every column in $\mathcal{U}_f$, which corresponds to the output of the circuit given the input, has a $1$ in a unique and distinct row. Therefore, $\mathcal{U}_f$ is unitary, and hence, could be implemented without the use of any ancilla qubits.

I would like somebody to verify whether the above reasoning is correct or flawed, and if flawed, I would like to see a concrete example of a function whose oracle cannot be implemented without ancilla qubits. I am guessing that I do not understand universallity and made a mistake somewhere, but I cannot see where.

Answer 1

Your argument is correct, but needs to be made with a little care. The way that a universality proof often goes is that you decompose the target unitary into a series of Givens rotations. Each such rotation is essentially a controlled-controlled-...-controlled-$U$. So you need to know how to build that gate. The most obvious construction involves ancillas (see Fig. 10 in Nielsen & Chuang). However, Nielsen & Chuang in Exercise 4.29 state that it can be done without ancillas. Thus, your universal construction can be done without ancillas, and so your reversible function can be made without ancillas.

One possible issue with the argument is that we have proven there exists a gate decomposition with no ancillas. But we needed to know the answer of the oracle to be able to find it. There could be some gap if you don't know the full truth table of the oracle, but only how to calculate using any given input.