How do you CNOT between qubits faraway from each other?

Question

I'm just curious. Say I have 3 qubits on a straight line 0-1-2. How do you guys (on the IBMQ or Rigetti team for example, or anyone who actually works on quantum computer) entangle 0-2 if I, say, am busy on the 1 qubit already (maybe I already have a CNOT between 0-1)? Is there a circuit for it, or is it purely hardware technique with no circuit equivalent? Say if I have:

2-1-0-3
    | |
    4-5

would it be better to CNOT 0 with 2, or 0 with 5, given that they have the same distance? Thank you!

Answer 1

If you don't have the ability to perform the controlled-not directly between a pair of qubits, then you simply need to swap the qubits to place them onto a pair of qubits which can have a controlled-not applied to them.

Answer 2

For interactions between non-nearest neighbour qubits, ancilla qubits are required, together with SWAP gates. The state of one of the (in this case) two qubits is swapped with the ancilla. This operation is repeated until the qubits are NN, and then the interaction can take place. After this is done, then the state of the ancilla is swapped back with the desired qubit, which from this point on will now have the resultant state from the interaction encoded on it.

It is due to the NN restrictions on must current QC's that circuit depth can explode relative to the amount of qubits or interactions, and then the overall runtime becomes and issue due to decoherence.