Cost of implementing Boolean function quantumly?

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$$?

• I would say that this depends on what your function will do it. For example, you function f(x) can be just a toffoli gate, i.e., it performs a "and" operation with a xor operation. Can you give more details about the function $f$? You can give a look at this presentation: vlsicad.eecs.umich.edu/BK/Slots/cache/www.eecs.umich.edu/… – Gustavo Banegas May 6 '19 at 8:02
• I am not interested in any function in particular and I think the question is well defined as is. In particular, I would like to know if one is assured that $U_f$ could be implemented in polynomial time, too and if so why. – Marsl May 6 '19 at 8:20
• @Marsl if $f$ is implemented with a polynomial number of irreversible gates (from, say, $\mathsf{NAND},\mathsf{NOR}$, etc.), it can also be implementable also with a polynomial number of reversible gates (from, say, $\mathsf{CNOT},\mathsf{CCNOT}$, etc.) Is that your question? If $f$ is, instead, defined recursively, it has been a bit tricky; however, this Quanta article on Craig Gentry's recent breakthrough on such recursive functions. – Mark S May 6 '19 at 15:03
• Yes, the first part is exactly what I am interested in. Can you argue this a little more? The second part is indeed very interesting, thx for the reference. – Marsl May 6 '19 at 15:21
• @Marsl In fact, there are several papers showing that you can make any function reversible. See [1], where Bennett shows how to do it. Also, in terms of karatsuba multiplication, there are papers showing how to do it and the costs for it, see [2]. However, this is just logical gates. One of the only papers that I know that go deep in terms of costs is [3]. [1] dl.acm.org/citation.cfm?id=73186 [2] arxiv.org/abs/1706.03419 [3] arxiv.org/abs/1603.09383 – Gustavo Banegas May 7 '19 at 9:07

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.