# Given $f: \{0, 1\}^n\to\{0, 1\}^m$, how many qubits are needed to implement the oracle $\mathcal U|x,0\rangle^{\otimes m}=|x,f(x)\rangle$?

Suppose I am given a function $$f: \{0, 1\}^n \to \{0, 1\}^m$$. A standard oracle would be of the form $$\mathcal{U}|x\rangle|0\rangle^{\otimes m} = |x\rangle|f(x)\rangle$$.

I would suspect that this encoding of the function is not always possible with exactly $$n+m$$ qubits, so my question is how many qubits are needed for it. (Though I know that any such function can be expressed using NAND gates and translated to Toffoli gates, so there is one loose upper bound of one ancilla qubit for each NAND gate.)

I hope to possibly see some upper bounds for either general or constrained cases of $$f$$.

Usually, saying that there is access to an oracle compute $$f$$ is equivalence to saying that you assume a model in which it is given that $$f$$ can be computed for free, Namely, In your case $$f :\{0,1\}^m \rightarrow \{0,1\}^n$$ one has to pay only $$n +m$$ space for storing the state.

Yet, if you indeed consider the complexity in the general model, then the space complexity might be arbitrarily large. For example, consider a function $$f:\{0,1\}^m \rightarrow \{0,1\}$$ that decides if an $$n$$-length binary string belongs to some language $$L$$ such that $$L \in$$ EXPSPACE, where EXPSPACE stands for all the languages that can be decided using at most exponential, in the length of the given, memory. Then the gate $$\ \mathcal{U} \$$ might use $$\Theta(2^m)$$ anciles, which can be thought of as exactly as the working memory needed by the classical machine to decide $$f$$. Furthermore, if $$f$$ is strictly in EXPSPACE, then any implementation of $$\ \mathcal{U} \$$ must use an exponential number of anciles.

• Ah, so the complexity class of the function does matter after all! Thank you for the detailed answer!
– 이희원
Commented Sep 5, 2023 at 15:05

We usually define the BQP complexity class to limit the number of gates, and hence the number of ancilla qubits, to be polynomial in the number of input qubits $$n$$ (which is also polynomial in the number of output qubits $$m$$).

The good news is that, for example, if $$f$$ was a (classical) Boolean function then for almost any reasonable problem you can think of (such as for a 3SAT problem), the number of added ancilla qubits would also be polynomial in the number of inputs. Otherwise your problem could be arbitrarily difficult.

For example, imagine your input register to be a matrix - such as an adjacency matrix of a small graph - and your oracle were to determine the permanent of the matrix. In this case there's no known simple way to describe the oracle with a polynomial number of gates, which I think also means that the number of ancilla qubits would likewise blow up. But, if you were determining the determinant of the graph then the number of gates and the number of ancilla qubits is polynomial as well.

Thinking some more, if your function $$f$$ is a permutation, then my intuition is that you may be able to get by with fewer ancilla qubits than if $$f$$ is not a permutation. My reasoning is that a permutation necessarily is reversible and hence you might not need to bring in extra ancilla qubits (especially if your gate set includes Fredkin/CSWAP gates). But I wouldn't know how to prove this yet.

• Thank you for the great answer! It seems I would need to study the BQP class deeper to fully formulate an answer.
– 이희원
Commented Sep 5, 2023 at 14:40