For physical $d$-dimensional qudits we can define $$X= \sum_{i=0}^{d-1} |i+1\rangle \langle i |$$ and $$Z = \sum_{i=0}^{d-1} \omega^i |i\rangle \langle i |,$$ with $\omega=e^{2\pi i/d}$. The Fourier gate $$F=\frac{1}{\sqrt{d}} \sum_{i,j=0}^{d-1} \omega^{ij} |i\rangle \langle j|$$ transforms one basis into the other, i.e. $F X F^\dagger = Z$.

Now consider a stabilizer error correction code. One can choose the logical $Z_L$ operator such that it commutes with all stabilizer generators, and one can choose $X_L$ such that it commutes with the stabilizer generators plus it fulfills $Z_L X_L = \omega X_L Z_L$. That should fix our logical qudit space. Now we can choose any operator that maps $X_L$ to $Z_L$ as our $F_L$, but is there any canonical way to construct it? I was hoping that there is some compact formula for $F_L$ in terms of $Z_L$ and $X_L$, but I couldn't find it.

To be clear, I am not asking for a decomposition of $F_L$ in terms of a circuit (even though that is interesting as well), but I am "only" looking for a canonical way to construct the unitary operator itself.

  • $\begingroup$ I'm slightly confused - are you looking for one-dimensional qudit codes (i.e. the logical Hadamard operator?) Or for the Fourier transform of general d-dimensional stabilizers? $\endgroup$
    – JSdJ
    Mar 26, 2021 at 11:27
  • $\begingroup$ @JSdJ yes F is the qudit equivalent of Hadamard for qubits $\endgroup$
    – M. Stern
    Mar 26, 2021 at 11:57
  • $\begingroup$ Yes, but that's not what I meant - are you interested in the logical Fourier transform of a 1-qubit codespace built from d-dimensional physical qudits, or are you interested in the Fourier transform of a d-dimensional codespace, built from physical qudits? $\endgroup$
    – JSdJ
    Mar 26, 2021 at 13:30
  • 1
    $\begingroup$ Usually, generalized Pauli $X$ is defined as $\sum_{i=0}^{d-1}|i+1\rangle\langle i|$. Perhaps the first equation contains a typo? $\endgroup$ Mar 26, 2021 at 20:01
  • 1
    $\begingroup$ I think we also need a $\frac{1}{\sqrt{d}}$ in front of the sum for $F$. Otherwise, $F$ is not unitary and $FXF^\dagger = dZ \ne Z$. $\endgroup$ Mar 28, 2021 at 16:24

1 Answer 1


There is no circuit for $F$ in terms of $X$ and $Z$, because $\{X, Z\}$ is not a universal set of gates and $F\notin\langle X,Z\rangle$. The first assertion follows from the fact that the action of any product of $X$ and $Z$ on a state in the computational basis is in the computational basis. The second one follows from the observation that the action of $F$ on any computational basis state is a uniform superposition of computational basis states.

That said, we can express $F$ as a polynomial in $X$ and $Z$. First note that

$$ \frac1d\sum_{k=0}^{d-1}Z^k = \frac1d\sum_{k=0}^{d-1}\left(\sum_{l=0}^{d-1}\omega^l|l\rangle\langle l|\right)^k = \frac1d\sum_{l=0}^{d-1}\left(\sum_{k=0}^{d-1}\omega^{kl}\right)|l\rangle\langle l| = |0\rangle\langle 0|. $$


$$ \frac1d\sum_{k=0}^{d-1}X^iZ^kX^{-j} = X^i|0\rangle\langle 0|X^{-j} = |i\rangle\langle j| $$

which provides a convenient means of expressing any matrix in terms of $X$ and $Z$. Substituting into the formula for $F$, we get

$$ F = \frac{1}{\sqrt{d}}\sum_{i,j=0}^{d-1}\omega^{ij}|i\rangle\langle j| = \frac{1}{d\sqrt{d}}\sum_{i,j,k=0}^{d-1}\omega^{ij} X^iZ^kX^{-j}. $$

If desired we can also eliminate the powers of $\omega$ using $\omega = X^{-1}ZXZ^{-1}$.

  • $\begingroup$ Thanks for your input. Regarding your first paragraph: The circuit is using multiple qudits. Replacing all gates by their logical pendants will give a circuit that acts on multiple logical qudits. But $F_L$ acts on a single qudit. Also I don't think it is really easier to find all the logical pendants. Regarding your second paragraph: That is good to note. However, with formula I do not mean circuit, but just a formula in the mathematical sense. $\endgroup$
    – M. Stern
    Mar 26, 2021 at 20:07
  • $\begingroup$ Thanks for the additional explanation! I did initially misunderstand the question. Just made some changes in response to your comment. $\endgroup$ Mar 27, 2021 at 0:03
  • $\begingroup$ I apologize if my question is not clear enough. I edited it to emphasize that I am not primarily interested in some decompositions of this gate (or doing it in a fault-tolerant way), but really just the operator itself. $\endgroup$
    – M. Stern
    Mar 28, 2021 at 9:12
  • $\begingroup$ What I don't understand is the significance of the error correcting code in the question. If we just want to express $F$ in terms of $X$ and $Z$ (already done in the answer) then can't we just consider an abstract qudit (whether formed using an error correcting code or not)? If the code is relevant, does it matter that it is a stabilizer code? $\endgroup$ Mar 28, 2021 at 16:23
  • $\begingroup$ Yes you are probably right that the code does not really matter, however the question arises only for codes, as for physical qudits the definition of F is clear (and unique). I do not see where F is expressed in terms of X and Z. $\endgroup$
    – M. Stern
    Mar 28, 2021 at 17:06

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.