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?