# Is it possible to make N-way Controlled-NOTs out of Toffoli gates, without extra work bits?

I'm working on exercise 4.29 of Nielsen and Chuang:

Find a circuit containing O(n^2) Toffoli, CNOT, and single qubit gates which implements a $C^n(X)$ gate (for n >3), using no work qubits.

As part of solving this exercise, I'm trying to figure out if the task of making a NOT-controlled-by-N-bits is possible classically (i.e. without using single qubit gates, except the NOT gate).

This is trivial to do if you have work bits initialized to 0 available, but I haven't been able to figure out how to do it without work bits. I'm also not sure how to approach an impossibility proof.

The main thing I've figured out is that, if I could make $Increment$ and $Decrement$ gates, then I could do it like this:

   ____    ____
--|    |--|    |---    --•--
--|    |--|    |---    --•--
--| +1 |--| -1 |--- == --•--
--|    |--|    |---    --•--
--|    |--|____|---    --•--
--|____|-----------    --X--


But I also can't figure out how to make those gates, at least not without the many-controlled-not gate I'm trying to make.

Is this even possible (the limited-to-classical case, not the exercise)?

It's not possible.

A reversible computation always corresponds to a permutation. When working on four bits, a Toffoli gate always corresponds to two inversions. A chain of Toffoli gates applies an even number of inversions.

The parity of a permutation is preserved when you apply an even number of inversions. Odd permutations can't be reached from even permutations by performing an even number of inversions.

Therefore the Toffoli gate can't get us from an even permutation, like (0, 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15), to an odd permutation, like (0,1,2,3,4,5,6,7,8,9,10,11,12,13,15,14). The function we want performs exactly that inversion, but Toffoli can't do it. The single CNOT and NOT gates have the same problem.

Therefore you can't use Toffoli gates to implement the 3C-NOT (unless you have work bits, or single-bit quantum gates).

... Actually, I'm a bit worried I made a mistake because this proves too much. It would mean any finite classical gate set with limited fan-in operating in binary must not be universal for no-garbage reversible computing, since adding a bit to the system doubles the number of inversions a gate applies and thus forces it to be even...

Slight twist on this not being possible.

If you have any ancilla bits, even ones in an unknown state that you don't own, you can create a $C^3$NOT from $C^2$NOTs. Do this:

C1 ─•───•─── C1
│   │
C2 ─•───•─── C2
│   │
C3 ─┼─•─┼─•─ C3
│ │ │ │
T ─┼─X─┼─X─ T + (C1 * C2 * C3)
│ │ │ │
E ─X─•─X─•─ E


So in practice you can make higher CNOT gates out of Toffoli gates. You just use any other bits that happen to be in the circuit as working space. You don't need the extra bits to be initialized to 0, and you won't trash them, but they do need to be present (they're catalysts).

So, in an $M$ bit circuit, you can at least make up to $C^\left\lceil \frac{M}{2} \right\rceil$NOT gates out of Toffoli gates by using the other half of the bits as workspace. You can also keep re-using one extra bit and the target bit as alternating workspaces, letting you get up to $C^{M-1}$NOTs, but that seems to require a quadratic number of gates.