I've been beating my head against this problem for three days now and I just can't seem to crack it. To construct an N-qubit controlled Unitary gate, I can do something like this (note I'm using Qiskit syntax here):
q_upper = QuantumRegister(n - 1)
q_lower = QuantumRegister(1)
q_out = QuantumRegister(1)
circ = QuantumCircuit(q_upper, q_lower, q_out)
# Setup u on the output line: |((1 << (n - 1)) - 1) 01> * u/2, |n0 11> * u/2, |((1 << n) - 1) 1> * u
circ.cnv(q_upper, q_out)
circ.cv(q_lower, q_out)
# Cancel out the terms that aren't all ones
circ.cnx(q_upper, q_lower)
circ.vdg(q_lower, q_out)
circ.cnx(q_upper, q_lower)
This circuit requires a little explanation. Here, I'm attempting to build an n-qubit u-gate using an (n-1)-qubit controlled v-gate (which will be half the rotation of u) and a a controlled v-gate. Then I use an (n-1)-qubit controlled x-gate in conjunction with another controlled v-gate to cancel out the terms that aren't all one.
As an example of the implementation, consider the Controlled-S (CS) gate:
q_lower = QuantumRegister(1)
q_out = QuantumRegister(1)
circ = QuantumCircuit(q_lower, q_out)
# Add a pi/2 rotation for 11, pi/4 for 01 and 10
circ.t(q_lower)
circ.t(q_out)
# Cancel out the pi/4 for 01 and 10
circ.cx(q_lower, q_out)
circ.tdg(q_out)
circ.cx(q_lower, q_out)
I can expand on this to produce a Toffoli-S (CCS) gate:
q_upper = QuantumRegister(1)
q_lower = QuantumRegister(1)
q_out = QuantumRegister(1)
circ = QuantumCircuit(q_upper, q_lower, q_out)
# Construct a pi/2 rotation for 111 and pi/4 rotations for 011 and 101
circ.cu1(pi / 4, q_upper, q_out)
circ.cu1(pi / 4, q_lower, q_out)
# Cancel out the pi/4 rotations on 011 and 101
circ.cx(q_upper, q_lower)
circ.cu1(pi / -4, q_lower, q_out)
circ.cx(q_upper, q_lower)
I can expand it again to produce a CCCS gate:
q_upper = QuantumRegister(2)
q_lower = QuantumRegister(1)
q_out = QuantumRegister(1)
circ = QuantumCircuit(q_upper, q_lower, q_out)
# Construct a pi/2 rotation for 1111 and pi/4 rotations for 1101 and 0011
circ.ccu1(pi / 4, q_upper[0], q_upper[1], q_out[0])
circ.cu1(pi / 4, q_lower, q_out)
# Cancel out the pi/4 rotations for 1101 and 0011
circ.ccx(q_upper[0], q_upper[1], q_lower[0])
circ.cu1(pi / -4, q_lower, q_out)
circ.ccx(q_upper[0], q_upper[1], q_lower[0])
Now, this circuit presents a problem: there is no ccu1
gate. Now, I could construct one that looks like this:
circ.cu1(pi / 8, q_upper[0], q_out)
circ.cu1(pi / 8, q_upper[1], q_out)
circ.cx(q_upper[0], q_upper[1])
circ.cu1(pi / -8, q_upper[1], q_out)
circ.cx(q_upper[0], q_upper[1])
But this means that an N-qubit Controlled-S gate would require an (N-1)-qubit Controlled-T gate which would require an (N-2)-qubit Controlled pi / 8
gate and so on and so forth, resulting in increasingly small rotations. Given the current state of quantum hardware (and probably the future of quantum hardware), this implementation doesn't seem practical but I haven't been able to find a better one.
Could anyone suggest a way to break this recursion at either the S-gate or T-gate level or will I have to just deal with the recursion?