Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace

Question

Exercise 4.29 from Quantum Computation and Quantum Information by Nielsen and Chuang has me stumped.

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.

I've figured out that this can't be done classically.

I've figured out how to do it with $O(2^n)$ exponentially precise gates (nest the double-control-from-single-controls-and-square-root-of-operation construction inside itself $n-2$ times).

I've tried generalizing the above construction into accumulating a linear combination of controlled operations. For example, if I have 3 controls called A and B and C and make a vector of the various cases [0, A, B, C, AB, BC, AC, ABC] then:

• Applying an operation unconditionally adds [1, 1, 1, 1, 1, 1, 1, 1]
• Controlling an operation on A adds [0, 1, 0, 0, 1, 1, 0, 1]
• Xoring A into C then controlling an operation on C (then undoing the xor) would add [0, 1, 0, 1, 1, 1, 0, 0]
• Xoring (A and B) into C via a toffoli gate then controlling an operation on C would add [0, 0, 0, 1, 1, 1, 1, 0]

Then I would try to add (apply a root of X) and subtract (apply inverse square root) the various vectors I can make until the result comes out as [0, 0, 0, 0, 0, 0, 0, N].

But I keep hitting various walls, such as solutions ending up with large multiples (i.e. the gates I'm using become exponentially precise, which I think is a no-no) or just not being able to solve the system due to the interplay between generating elements with AND/XOR then solving with +/* being non-standard or creating exponential numbers of gates.

What are some other approaches to try?

Answer 1

Eventually I ended up solving this for $O(n)$ gates. I wrote up a trilogy of blog posts on it.

1. Constructing Large Controlled Nots (classically, with an ancilla)

2. Constructing Large Increments (classically, with an ancilla)

3. Using Quantum Gates instead of Ancilla Bits

Of course it would suck if you found this twenty years from now and my website was long gone, so the basic steps follow in quickly-described image form.

1. Bootstrap a Borrowable Ancilla Bit

Use a square root and its inverse to reduce the maximum number of controls by one, creating an uninvolved wire for each operation. Then iteratively move controls off of non-Not operations, and re-arrange the cruft that results into large increment gates and single-qubit phase gates.

2. Use Single Ancilla Bit to Cut Operations in Half

For each large operation, use the uninvolved wire as a borrowed ancilla bit. Use it to transform the huge increment and controlled-not gates into smaller operations that each have approximately half of the wires uninvolved. Repeat twice, if required for the next step to have enough working space.

3. Use Many Ancilla Bits to Finish

For each still-too-large operation, borrow the many uninvolved wires as ancilla bits. Use them to get all the way down to Toffoli-or-smaller gates.

Those three steps will get you all the way from a fully-controlled-not to linearly many Toffoli, CNOT, and single-qubit gates. There's a few implied pieces, like how to merge a control into an increment gate, but they're pretty simple.

(Sorry for the inconsistent style of the diagrams.)