How do I construct a circuit to reshuffle some computational basis vectors?

Question

I would like to construct a quantum circuit s.t.

1. It maps a certain (relatively small) subset of computational basis vectors onto a different subset of those, e.g.

$$ |0101001\rangle \to |1000010\rangle, \; |1001011\rangle \to |0111011\rangle, \ldots $$

(I was tempted to call such action "a permutation", but I guess it not necessarily is one.)

2. I don't care what circuit's action is on the rest of the basis vectors.

How can I do that? Of course, ideally I would like to achieve this with a minimum number of single-qubit gates and CNOTs.

Answer 1

As mentioned in the comment above there is a relevant section of Nielsen and Chuang that discusses circuits which perform this sort of action (p191-193, 10th aniversary edition). The dersired transformation can be done using a classical reversible circuit with the {X, CnX} gateset.

I'm going to show how to implement such permutation circuits in pytket using the ToffoliBox construction. This implementation uses multiplexor operations to reduce the number of multi-qubit gates required.

Here is an example from the user manual.

Let's perform the following permutation of basis states

\begin{gather} |001\rangle \longmapsto |111\rangle \\ |111\rangle \longmapsto |001\rangle \\ |100\rangle \longmapsto |000\rangle \\ |000\rangle \longmapsto |100\rangle \end{gather}

We can construct this permutation as a dictionary of key-value pairs.

from pytket.circuit import ToffoliBox

# Specify the desired permutation of the basis states
mapping = {
    (0, 0, 1): (1, 1, 1),
    (1, 1, 1): (0, 0, 1),
    (1, 0, 0): (0, 0, 0),
    (0, 0, 0): (1, 0, 0),
}

# Define box to perform the permutation
perm_box = ToffoliBox(permutation=mapping)

For correctness if a basis state appears as a key in the dictionary then it must also appear as a value.

Let's now test this out by preparing the three qubit Werner state $|W\rangle$ and see if our ToffoliBox shuffles our basis states as expected.

\begin{equation} |W\rangle = \frac{1}{\sqrt{3}} \big(|001\rangle + |010\rangle + |100\rangle \big) \end{equation}

from pytket.circuit import Circuit, StatePreparationBox
import numpy as np

werner_state = 1 / np.sqrt(3) * np.array([0, 1, 1, 0, 1, 0, 0, 0])

werner_state_box = StatePreparationBox(werner_state)

state_circ = Circuit(3)
state_circ.add_gate(werner_state_box, [0, 1, 2])

This is not the most efficent way to prepare $|W\rangle$ but will serve for illustration purposes.

# Verify state preperation
np.round(state_circ.get_statevector().real, 3) # 1/sqrt(3) approx 0.577

As expected we get

array([-0.   ,  0.577,  0.577,  0.   ,  0.577,  0.   ,  0.   ,  0.   ])

Now lets add our ToffoliBox which we defined in the first code block to our state preparation circuit and check our statevector again

state_circ.add_gate(perm_box, [0, 1, 2])
np.round(state_circ.get_statevector().real, 3)

After the permutation box is applied we now get...

array([0.577, 0.   , 0.577, 0.   , 0.   , 0.   , 0.   , 0.577])

corresponding to the modified state $|W'\rangle$ \begin{equation} |W'\rangle = \frac{1}{\sqrt{3}} \big(|000\rangle + |010\rangle + |111\rangle \big) \end{equation}

We see that our ToffoliBox has performed the desired permutation.