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

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.)

1. 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.

• Is there more underlying structure to be exploited? (E.g. is this guaranteed to be a ring, or could it be a series of pairs or multiple rings...) Nov 14, 2020 at 19:04
• Can you write down a classical function $f(x)$ that describes how to map input basis elements to outputs? Nov 14, 2020 at 21:09
• There's no more underlying structure or a functional representation. This is all for near-term purposes. Nov 15, 2020 at 1:47
• As mentioned DaftWullie, you need only classical logical function. Are you familiar with construction of such function based on truth tables? Then you can use Toffoli gate as it is effectively NAND gate which is the universal one for classical logical functions. Nov 15, 2020 at 7:44
• Let us assume that the basis vectors not belonging to the subset of interest map to themselves. Then, you expect to perform a permutation within the set of basis vectors of interest. Does this sound right? Dec 24, 2020 at 19:01

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.

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

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)

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

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