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?


2 Answers 2


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$: enter image description here

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

enter image description here

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

  • $\begingroup$ 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? $\endgroup$ Commented Nov 1, 2019 at 13:00
  • $\begingroup$ @ChaitanyaReddy No, you have exactly what I wrote: $x_1\oplus x_2\oplus(x_1\oplus x_2)=0$ $\endgroup$
    – DaftWullie
    Commented Nov 1, 2019 at 13:20
  • $\begingroup$ Sir, I think you considered n = 3 in the above comment. Please consider n (as variable) and m = 3 (m > 2) . $\endgroup$ Commented Nov 1, 2019 at 16:51
  • $\begingroup$ @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. $\endgroup$
    – DaftWullie
    Commented Nov 1, 2019 at 20:17
  • $\begingroup$ Sir can I consider this as an example of quantum circuit which follows inherent parallelism?! $\endgroup$ Commented Nov 4, 2019 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.

enter image description here

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

  • $\begingroup$ Could you please give me some reference (link/textbook/example) for this concept. $\endgroup$ Commented Oct 31, 2019 at 13:47
  • $\begingroup$ @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). $\endgroup$ Commented Oct 31, 2019 at 14:13
  • $\begingroup$ @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. $\endgroup$ Commented Nov 1, 2019 at 16:54
  • $\begingroup$ @ChaitanyaReddy Sure, I just edited my answer to explicitly walk through the case of $n=3$, $m=3$. $\endgroup$ Commented Nov 2, 2019 at 11:27
  • $\begingroup$ @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? $\endgroup$ Commented Nov 3, 2019 at 5:24

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.