# How to generate a superposition of m-level n-particle states $|j_{0} ,j_{1}, …,j_{n-1}\rangle$ with $\sum_{k=0}^{n-1} j_k \mathrm{mod}\ m \ = \ 0$?

The m level n-particle state $$|X_{N}\rangle$$ is defined as

$$\boxed{|X_{N}\rangle = \frac{1} {m^\frac{n-1}{2}}\sum_{\sum_{k=0}^{n-1} j_k \mathrm{mod}\ m \ = \ 0}|j_{0}\rangle |j_{1}\rangle ....|j_{n-1}\rangle}$$

How can this state be prepared?

To get you started, the $$m = 2$$ (qubit) case:

Start with n qubits all in the 0 state. Apply Hadamard gates to the first n-1 qubits. Apply n-1 controlled nots, each one controlled by a different one of the hadamarded qubits, and each targeting the nth qubit (the one we didn’t hadamard).

Here's an example circuit for $$n=3$$:

To understand how this works, recall how a controlled-not functions:

So, if after applying the Hadamard gates we have the state $$\frac{1}{\sqrt{2^{n-1}}}\sum_{x\in\{0,1\}^{n-1}}|x\rangle|0\rangle,$$ then after all the controlled-nots I'm suggesting, the final bit is in the state $$x_1\oplus x_2\oplus x_3\oplus\ldots \oplus x_{n-1}.$$ The overall parity of the final $$n$$-bit string is $$x_1\oplus x_2\oplus x_3\oplus\ldots \oplus x_{n-1}\oplus (x_1\oplus x_2\oplus x_3\oplus\ldots \oplus x_{n-1})=0,$$ as required.

As ChainedSymmetry pointed out, the $$m$$-dimensional generalisation is near-identical. You apply a gate $$|0\rangle\mapsto \frac{1}{\sqrt{m}}\sum_{i=0}^{m-1}|i\rangle$$ on the first $$n-1$$ spins. The controlled from each of these spins, targeting the $$n^{th}$$ spin, you apply a generalisation of the controlled-not of the form $$|j\rangle|k\rangle\mapsto|j\rangle|-j+k\text{ mod }m\rangle.$$

• For m = 3, we have $$x_1\oplus x_2\oplus x_3\oplus\ldots \oplus x_{n-1}\oplus ((x_1\oplus x_2\oplus x_3\oplus\ldots \oplus x_{n-1}) \oplus (x_1\oplus x_2\oplus x_3\oplus\ldots \oplus x_{n-1}))=0,$$ Am I correct? – Chaitanya Reddy Nov 1 '19 at 13:00
• @ChaitanyaReddy No, you have exactly what I wrote: $x_1\oplus x_2\oplus(x_1\oplus x_2)=0$ – DaftWullie Nov 1 '19 at 13:20
• Sir, I think you considered n = 3 in the above comment. Please consider n (as variable) and m = 3 (m > 2) . – Chaitanya Reddy Nov 1 '19 at 16:51
• @ChaitanyaReddy ah yes, so I did, but mainly because you used the standard notation for addition modulo 2. What you wrote does not work for m=3 either. Just think about the case that I wrote down, but for addition mod 3. – DaftWullie Nov 1 '19 at 20:17
• Sir can I consider this as an example of quantum circuit which follows inherent parallelism?! – Chaitanya Reddy Nov 4 '19 at 8:48

For the general case, $$m>2$$, do what DaftWullie said, except apply gates corresponding to the $$m$$-point DFT matrix instead of the Hadamard gate (which is the 2-point DFT matrix).

Edit Per Request

For the $$m=3$$, $$n=3$$ use a gate ($$M$$) corresponding to the 3-point DFT matrix instead of the Hadamard gate to effect the transformation $$\vert j \rangle =\tfrac{1}{\sqrt{3}} \sum \limits_{n=0}^2 e^{\frac{i 2 \pi jk}{k}} \vert k \rangle$$. Define $$\omega \equiv e^{\frac{i 2\pi}{3}} = -\tfrac{1}{2} + i\tfrac{\sqrt{3}}{2}$$, and $$M$$ is explicitly $$M = \frac{1}{\sqrt{3}} \begin{bmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega \end{bmatrix}$$ (note that $$\omega^4=\omega$$). The relevant circuit is almost identical to DaftWullie's except $$H$$ is replaced with $$M$$ and the computational basis now has three states. Any other changes are superficial to aid the explanation.

You can see that $$M \vert 0 \rangle = \tfrac{1}{\sqrt{3}}(\vert 0 \rangle + \vert 1 \rangle + \vert 2 \rangle)$$, so trivially $$\vert \psi_0 \rangle= \tfrac{1}{3}(\vert 0 \rangle + \vert 1 \rangle + \vert 2 \rangle)\otimes (\vert 0 \rangle + \vert 1 \rangle + \vert 2 \rangle) \otimes \vert 0 \rangle.$$

Application of $$\text{CNOT}$$ between the bottom two registers gives $$\text{CNOT} (\tfrac{1}{\sqrt{3}}(\vert 0 \rangle + \vert 1 \rangle + \vert 2 \rangle) \otimes \vert 0 \rangle)=\tfrac{1}{3}(\vert 0 \rangle + \vert 1 \rangle + \vert 2 \rangle) \otimes (\vert 0 \oplus 0 \rangle + \vert 0 \oplus 1 \rangle + \vert 0 \oplus 2 \rangle),$$ where $$\oplus$$ is addition modulo 3. This gives $$\vert\psi_1 \rangle = \tfrac{1}{3\sqrt{3}}(\vert 0 \rangle + \vert 1 \rangle + \vert 2 \rangle)\otimes (\vert 00 \rangle + \vert 01 \rangle + \vert 02 \rangle + \vert 10 \rangle + \vert 11 \rangle + \vert 12 \rangle + \vert 20 \rangle + \vert 21 \rangle + \vert 22 \rangle).$$

The same $$\text{CNOT}$$ process is repeated between the first and third register to get to $$\vert \psi_2 \rangle$$ and arrive at the desired result $$\vert \psi_2 \rangle = \tfrac{1}{3 \sqrt{3}} \sum \limits_{p,q,r=0}^2 \vert p \, q \, r \rangle.$$

• Could you please give me some reference (link/textbook/example) for this concept. – Chaitanya Reddy Oct 31 '19 at 13:47
• @ChaitanyaReddy The DFT (Discrete Fourier Transform) is a generalization of the Walsh-Hadamard transform. You may check this Wikipedia page. For a more pedagogical approach to the DFT (and subsequently QFT), you may refer to Ryan O'Donnell's lecture(s). – Sanchayan Dutta Oct 31 '19 at 14:13
• @ChainedSymmetry could you please edit the answer for the case of n = 3 and m = 3. I understood DaftWullie's explanation for n = 3 and m = 2 but I am unable to proceed for n = 3 and m =3. – Chaitanya Reddy Nov 1 '19 at 16:54
• @ChaitanyaReddy Sure, I just edited my answer to explicitly walk through the case of $n=3$, $m=3$. – Jonathan Trousdale Nov 2 '19 at 11:27
• @ChainedSymmetry In the transformation - M|0>, M is a 3x3 matrix and What should be the size of |0>? Is it 3x1? If it is 3x1 then how to generate it? – Chaitanya Reddy Nov 3 '19 at 5:24