Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
The counterpart of a NOT gate is the CNOT gate. They make use of ancilla qubits to achieve this.
Given an arbitrary non-unitary transformation what are the minimum number of ancilla qubits required to make a transformation unitary? (Any bounds will do as well)
The procedure I use e.g. in this answer works in the general case as well.
The minimum number of ancillae that you need depends on how much "non-injective" the function is. By this I mean that, given a function $f$, the property that matters is the number of elements in the preimages of $f$: $|f^{-1}(y)|$, where $f^{-1}(y)\equiv\{x : f(x)=y\}$. More specifically, you need to look at the greatest such number: $$I\equiv \max_{y\in\operatorname{im} f} |f^{-1}(y)|,$$ where the maximum is taken over all elements in the image of $f$. Then, the necessary and sufficient number of ancillary qubits required to make the operation unitary (i.e. to make $f$ bijective) is $\lceil\log_2 I\rceil$, where $\lceil x\rceil$ denotes the smallest integer greater than $x$.
The reason is simple: you are looking for a function $\tilde f$ which extends $f$ and is injective. For this to be the case you need the set of inputs that all go to the same output to now "become distinguishable". This means that given any $y\in\operatorname{im}(f)$ for which there are $\ell$ elements in $f^{-1}(y)$, call them $x_1,...,x_\ell$, the extension $\tilde f$ must instead give $\ell$ different outputs $y_1,...,y_\ell$.
This is just a generic way to build an injective function out of a generic function, but now we need something more: we want $\tilde f$ to also be such that partial tracing the ancillary qubits gives back the original function. This means that all the additional outputs must be in the form of ancillary qubits, which converts the question into: "what is the smallest number of ancillary qubits I need to get an injective function?" To answer this you need only focus on the "least injective output", as if there are enough ancillary modes to separate $\max_y f^{-1}(y)$ then they are also enough to make the whole function injective. The number of qubits required to have $I$ distinct modes is the smallest $n$ such that $2^n\ge I$, hence the result $n=\lceil\log_2 I\rceil$.
I should note that there is nothing quantum about this: it is just a result about the number of ancillary bits required to make a classical operation reversible.
For a classical function $f:\{0,1\}^n\rightarrow\{0,1\}^m$, there is always a reversibile implementation (and hence corresponding unitary implementation) on $n+m$ bits. There could be one on as few as $n$ bits depending on the function. For example, when you say that controlled not is the reversible implementation of not (it corresponds to the upper bound), not is itself reversible and hence unitary, corresponding to the lower bound.
Your question asks more generally about a non-unitary transformation. You may be interested in the following questions/answers:
Essentially, if it can be extended, yo only need one qubit.
