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
Say, I wanted to implement a unitary $U_f$ to compute a Boolean function $f:B_n \to B_n$. This is done by the unitary $$U_f|x\rangle | y \rangle = |x\rangle|y\oplus f(x)\rangle$$ which one can construct even if $f$ itself is not invertible. Now, suppose $f$ can classically be computed in polynomial time.
What is the cost of implementing $U_f$?
As to the question of how to convert a function performed iteratively using irreversible gates to the same function performed iteratively using reversible gates, you should probably accept that any boolean function from $\{0,1\}^n$ to $\{0,1\}$ can be written in $\mathsf{3CNF}$-normal form with a polynomial number of $\mathsf{AND, OR, NOT}$ gates (i.e. $\lor$, $\land$, and $\lnot$ gates). Of these three, only $\lnot$ is reversible; the other two, $\land$ and $\lor$ are not.
You should probably also accept that you can convert any function written in $\mathsf{3CNF}$ having $\{\lnot,\lor,\land\}$ gates to the same function written with a polynomial number of clauses using only $\uparrow$, the Sheffer stroke (for $\mathsf{NAND}$). The Sheffer stroke $\uparrow$ is not reversible.
It would suffice to replace the Sheffer stroke $\{\uparrow\}$, or the $\mathsf{3CNF}$ gates $\{\lor,\land,\lnot\}$, with some reversible gates.
Enter the Toffoli gate, aka the $\mathsf{CCNOT}$ gate.
Quoting from Wikipedia:
[The Toffoli gate] preserves two of its inputs a,b and replaces the third c by $c\oplus (a\cdot b)$. With $c=0$, this gives the $\mathsf{AND}$ function, and with $a\cdot b=1$ this gives the $\mathsf{NOT}$ function. Thus, the Toffoli gate is universal and can implement any reversible boolean function (given enough zero-initialized ancillary bits).
Thus, you can implement $\mathsf{AND}$ and $\mathsf{NOT}$ with Toffoli gates, and hence implement $\mathsf{NAND}$ with two Toffoli gates. The implication is that the "enough zero-initialized ancillary bits" is not more than polynomial in $n$.
I don't expect that real synthesis of boolean functions uses only Toffoli gates - but at least there's an outline of how you could convert a function written in $\mathsf{3CNF}$-normal form into some other normal form using nothing but Toffoli gates.
