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.

  • $\begingroup$ 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...) $\endgroup$
    – C. Kang
    Commented Nov 14, 2020 at 19:04
  • 1
    $\begingroup$ Can you write down a classical function $f(x)$ that describes how to map input basis elements to outputs? $\endgroup$
    – DaftWullie
    Commented Nov 14, 2020 at 21:09
  • $\begingroup$ There's no more underlying structure or a functional representation. This is all for near-term purposes. $\endgroup$
    – mavzolej
    Commented Nov 15, 2020 at 1:47
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 15, 2020 at 7:44
  • $\begingroup$ 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? $\endgroup$ Commented Dec 24, 2020 at 19:01

1 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 anniversary edition). The desired transformation can be done using a classical reversible circuit with the {X, CnX} gate set.

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 $W$ state 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

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

w_state_box = StatePreparationBox(w_state)

state_circ = Circuit(3)
state_circ.add_gate(w_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

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.