How is it possible to perform a c-not on 4 qubits using the same control qubits on IBM Q computers?

Question

I was wondering after seeing ibmq_16_melbourne layout how it is possible to perform this circuit :

It seems when looking at ibm q computers that a qubits can at max target 3 qubits because the arrow representing connectivity between qubits (which mean the possible cnots) doesn't allow more.

So how does the compiler map virtual qubits to physical quits in this case?

Answer 1

You will need to use some trickery.

SWAP gates are the conceptually easiest method. For example, let's use qubit 5 as $a_0$, and then 5, 6 and 9 as $a_1$, $a_2$ and $a_3$. Finally, let's use qubit 3 as $a_4$.

In this case, the only difficult cnot is cx(5,3), between $a_0$ and $a_4$, which cannot be implemented directly. So we could apply a SWAP gate between qubits 3 and 4, which swaps their states. Implementing cx(4,3), which is allowed by the device, then has much the same effect as cx(5,3) would have. To complete the effect, a final SWAP is applied.

Since a SWAP is implemented using three cnot gates, the above process requires 7 cnots to reproduce the effect of just one. It would therefore be good to find a more efficient option.

One possibility is the following

qc.cx(4,3)
qc.cx(5,4)
qc.cx(4,3)
qc.cx(5,4)

The end effect of this is to perform qc.cx(5,3). It does this by making use of qubit 4. However, it does not matter what the state of qubit 4 was before the process is applied, and it leaves qubit 4 completely unchanged at the end.

A further option could be to encode the state of $a_0$ in many of the physical qubits on the device. For example, you could associate the $|0\rangle$/$|1\rangle$ state of $a_0$ with the $|000000\rangle$/$|111111\rangle$ states of qubits 1-6. Then a desired state $a |0\rangle+b|1\rangle$ would be encoded as $a |000000\rangle+b|111111\rangle$. A cnot can then be applied between this logical qubit and any of the 8 qubits it is connected to (0 and 7-13).