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

  • 2
    $\begingroup$ 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/… $\endgroup$ Commented May 6, 2019 at 8:02
  • $\begingroup$ 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. $\endgroup$
    – Marsl
    Commented May 6, 2019 at 8:20
  • 2
    $\begingroup$ @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. $\endgroup$ Commented May 6, 2019 at 15:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Marsl
    Commented May 6, 2019 at 15:21
  • 3
    $\begingroup$ @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 $\endgroup$ Commented May 7, 2019 at 9:07

1 Answer 1


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.


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.