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


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

  • $\begingroup$ Thanks for the response! I will definitely look into Givens rotations for a fuller understanding. I have two followup questions: 1. If the oracle for a known function f can be implemented with no ancilla qubits, then what importance does Bennett's $O(N)$ upper bound have? 2. I don't quite understand what you mean by "[know] only how to calculate using any given input". Could you please elaborate? $\endgroup$
    – 이희원
    Sep 16, 2023 at 3:36
  • 1
    $\begingroup$ Well, there's a big difference between knowing the full truth table of an oracle (which you need to apply this technique), and knowing the algorithm by which you calculate $f(x)$ for an $x$ that I give you. Think about something like the 3-SAT problem. I can construct an oracle to determine if a specific x is a solution without having explicitly written out the truth table of what $f(x)$ is for every $x$. $\endgroup$
    – DaftWullie
    Sep 18, 2023 at 6:21
  • $\begingroup$ Ah, I see! So if a precomputation of all $2^n$ outputs of $f$ is possible, then the argument holds; if not, then using Bennett algorithm, the computing procedure of $f$ can be translated using at most $O(N)$ ancillae. Thank you so much! $\endgroup$
    – 이희원
    Sep 18, 2023 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.