In cirq, you can get decompositions like this from cirq.two_qubit_matrix_to_operations
. It will use CZs instead of CNOTs, but a few Hadamards around the CZs fixes that.
This is a swap:
This is a square-root-of-swap:
There's a standard way to decompose a controlled phase rotation into two CNOTs and single qubit phase rotations by half the amount. To do a controlled X rotation you just use that construction but swap the target's X and Z roles:
Now there's a CZ next to a CX. This can be fused into a CY with an S on the control (becayse XZ = -iY):
Now insert single qubit gates to make all the two qubit gates into CNOTs:
Lastly you'd fuse some of the single qubit gates, but this depends on your gate set. At the very least you'd combine the T gate and the S^-1 gate into a T^-1 gate because they commute across the control. For a harder challenge, see if you can figure out how to merge the S^-1 in the top right with the X^(1/4) in the top left creating an X^(-1/4) without increasing the number of other gates.
It's not possible to perform a square root of swap using fewer than three CNOTs, because the KAK decomposition of the square root of swap has three non-zero coupling coefficients.