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$: 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$ – Chaitanya Reddy Nov 1 '19 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 Nov 1 '19 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$ – Chaitanya Reddy Nov 1 '19 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 Nov 1 '19 at 20:17
  • $\begingroup$ Sir can I consider this as an example of quantum circuit which follows inherent parallelism?! $\endgroup$ – 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.

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$ – Chaitanya Reddy Oct 31 '19 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$ – Sanchayan Dutta Oct 31 '19 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$ – Chaitanya Reddy Nov 1 '19 at 16:54
  • $\begingroup$ @ChaitanyaReddy Sure, I just edited my answer to explicitly walk through the case of $n=3$, $m=3$. $\endgroup$ – Jonathan Trousdale Nov 2 '19 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$ – Chaitanya Reddy Nov 3 '19 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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