Building an N-qubit Controlled S Gate

Question

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?

Answer 1

The angles getting smaller is not a problem. The actual problem is that you are generating a ton of gates. To produce one gate with N controls, you're recursing on the producing of 3 gates with N-1 controls. Follow the logic to the end, and you'll see that you end up with $3^N$ gates!

It is possible to reduce the number of gates from exponential to linear. In the ideal case, you have $N$ ancillae available and can use Toffoli gates to compute the AND of your control qubits. You apply the S gate to the qubit storing the AND, then uncompute.

If you don't have any workspace, it gets a lot more complicated. You have to do stuff like this:

and this