Concerning the Hadamard gate and the Pauli $X$ and $Z$ gates for qubits, it is straightforward to show the following relationship via direct substitution:

$$ HXH = Z.\tag{1}$$

And I would like to demonstrate this relationship for higher dimensions (I know that this still holds for higher dimensions but I haven't found a proof for it anywhere).

I know that the $d$-dimension generalization of the X and Z Pauli gates for qudits are given by $X_d\lvert j\rangle = \lvert j\bigoplus1 \rangle$ and $Z_d\lvert j\rangle = \exp^{\frac{i2\pi j}{d}}\lvert j\rangle$ (where $j = 0,1,2,\dots,d-1 $). My approach to finding the d-dimension generalization of equation $(1)$ is to make use of these operators, but unfortunately I cannot find a $d$-dimensional analogue of the Hadamard gate like I have for the $X$ and $Z$ Pauli gates. I have considered using the relationship $H = \frac{1}{\sqrt2}(X + Z)$ but I don't know for certain if this is just true for qubits.

If anyone could provide any suggestions or hints as to how I should prove the generalization of equation $(1)$, it will be much appreciated (my biggest problem specifically is expressing H in an alternate form).


The appropriate $d$-dimensional analogue of $H$ turns out to be the Quantum Fourier Transform. This is obscured by the fact that even though $(1)$ is conjugation the inverse is written implicitly since $H^\dagger = H$. Thus, $d$-dimensional generalization of $(1)$ is

$$ QFT \circ X_d \circ QFT^\dagger = Z_d.\tag{1'} $$


The following calculation shows that both sides of $(1')$ agree on the computational basis and therefore are equal

$$ \begin{align} QFT \circ X_d \circ QFT^\dagger |j\rangle &= QFT \circ X_d \left(\frac{1}{\sqrt{d}}\sum_{k=0}^{d-1} \exp\left(-\frac{2\pi ijk}{d}\right)|k\rangle\right) \\ & = QFT \left(\frac{1}{\sqrt{d}}\sum_{k=0}^{d-1} \exp\left(-\frac{2\pi ijk}{d}\right)|k\oplus 1\rangle\right) \\ & = QFT \left(\frac{1}{\sqrt{d}}\sum_{k=0}^{d-1} \exp\left(-\frac{2\pi ij(k-1)}{d}\right)|k\rangle\right) \\ & = \frac{1}{d}\sum_{k=0}^{d-1} \exp\left(-\frac{2\pi ij(k-1)}{d}\right)\sum_{l=0}^{d-1}\exp\left(\frac{2\pi ikl}{d}\right)|l\rangle \\ & = \frac{1}{d}\exp\left(\frac{2\pi ij}{d}\right)\sum_{k,l=0}^{d-1} \exp\left(\frac{2\pi ik(l-j)}{d}\right)|l\rangle \\ & = \frac{1}{d}\exp\left(\frac{2\pi ij}{d}\right)\cdot d\,|j\rangle \\ & = Z_d |j\rangle. \end{align} $$

  • $\begingroup$ Thank you for your answer, Adam. The quantum fourier is a new concept to me, but I understand the general approach of your answer. Could you explain why you decided to use the hermitian conjugate of the right-handside QFT on the first line? How is this different from the regular QFT? And also may you explain how from your second line to the third line the state |k ⨁ 1> becomes |k> ? I assumed some change of variable at first but then I remembered it's the direct sum symbol and not the conventional addition operator. Thank you $\endgroup$ – Coconut Jan 28 at 1:18
  • $\begingroup$ I used Hermitian conjugate to effect the inverse QFT on the right. It appears like I added it to your equation $(1)$, but in reality the inverse was there all along - invisible due to the fact that Hadamard is self-inverse. The reason for the inverse is that the relationship you have in mind is a case of matrix similarity. $\endgroup$ – Adam Zalcman Jan 28 at 2:01
  • $\begingroup$ The difference between the regular and inverse QFT is just the sign of the exponents. You can see this by looking at the coefficients in the two sums that appear in the calculation as we expand $QFT^\dagger$ and then $QFT$. In the first case the coefficients are $\exp\left(-\frac{2\pi ijk}{d}\right)$ while in the second case they are $\exp\left(+\frac{2\pi ikl}{d}\right)$. $\endgroup$ – Adam Zalcman Jan 28 at 2:08
  • $\begingroup$ One simple way to see that changing signs of the exponents turns $QFT$ into $QFT^\dagger$ is by writing down a matrix for the QFT. You'll notice that the matrix is symmetric, i.e. $QFT^T = QFT$. Since QFT (like all quantum gates) is unitary it means that replacing each entry with its complex conjugate turns $QFT$ into $QFT^\dagger$. However, complex conjugate of $\exp(ia)$ is $\exp(-ia)$. $\endgroup$ – Adam Zalcman Jan 28 at 2:10
  • $\begingroup$ From second to the third line I changed the index from $k$ to $k'=k \oplus 1$ (and then renamed back to $k$). This step exploits two facts. First, $\oplus$ denotes addition modulo $d$, i.e. we map the computational basis vectors cyclically (this is needed for unitarity in finite dimensions). Second, addition in the exponents also happens modulo $d$, because $\exp(\frac{2\pi i d}{d}) = 1$. $\endgroup$ – Adam Zalcman Jan 28 at 2:14

The correct generalization is the discrete Fourier transform $F_d$ over $d$ dimensions defined as

$$ F_d = \sum_{jk} e^{i2\pi jk / d} |j\rangle \langle k| $$

up to a sign convention. I'll show $F_d^\dagger Z_d F_d = X_d$ since its equivalent and a bit easier. Letting $\omega_d \equiv \exp(i2\pi/d)$ we have \begin{align} F_d^\dagger Z_d F_d &= \left(\sum_{j,k}\omega^{jk}|j\rangle \langle k|\right)^\dagger \left(\sum_\ell \omega^\ell |\ell \rangle \langle \ell |\right) \left(\sum_{m,n}\omega^{mn}|m\rangle \langle n|\right) \\ &= \sum_{j,k,\ell, m,n} \omega^{-jk}\omega^\ell \omega^{mn} \delta_j^\ell \delta_\ell^m |k \rangle \langle n| \\ &= \sum_{k,n} |k \rangle \langle n| \left(\sum_\ell \omega^{\ell(1 + n - k)} \right) \\ &= \sum_{k,n}|k \rangle \langle n| \delta_k^{n+1 \text{ mod d}} \\ &= \sum_{k,n}|n+1 \text{ mod d}\rangle \langle n| \end{align}

where in the third line I used an identity for the sum over roots of unity, and for simplicity I've left out a host of factors of $\frac{1}{\sqrt{d}}$ that are required for unitarity. That last operator is $X_d$, and so the same proof shows that $F_d X_d F_d^\dagger = Z_d$.


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.