Reading the Register in a Mirror

The circuit for the quantum Fourier transform produces its result with the qubits in the opposite order, so it ends by putting them back: it swaps qubit 0 with qubit n-1, qubit 1 with qubit n-2, and so on. Together these swaps reverse the bit string of every basis state: the amplitude of |b_0 b_1 \dots b_{n-1}\rangle moves to |b_{n-1} \dots b_1 b_0\rangle.

Bit order: basis state |b_0 b_1 \dots b_{n-1}\rangle has index int("b0b1...", 2), so qubit 0 is the leftmost bit, the most significant. In 3 qubits, |011\rangle is index 3.

Write bit_reversal(n) that returns a pair (perm, swaps):

• perm is a list of 2^n indices: perm[i] is the index whose n-bit string is the string of i written backwards (leading zeros count: in 3 qubits, 1 is 001, which reversed is 100, so perm[1] = 4);
• swaps is the list of qubit pairs that the circuit swaps, (q, n - 1 - q) for every q with q < n - 1 - q, in increasing order of q. When n is odd, the middle qubit stays where it is.

Examples

Input:  n = 3
Output: ([0, 4, 2, 6, 1, 5, 3, 7], [(0, 2)])
Explanation: 001 -> 100, 011 -> 110, 010 stays 010. Swapping qubits 0 and 2 is enough.

Input:  n = 2
Output: ([0, 2, 1, 3], [(0, 1)])

Input:  n = 1
Output: ([0, 1], [])

Goals

• Reverse the n-bit string of every basis index
• List the swap gates that reverse the order of the qubits