The Exercise

A register of $n$ qubits is prepared in the state $|00\ldots0\rangle$ , every qubit in $|0\rangle$ . The exercise asks for the state the quantum Fourier transform makes of it, written out explicitly in the computational basis of the register.

The library answers it for a system with any number $d$ of levels, the register being the case $d = 2^n$ .

A Quantum System

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space; any such space $H$ is the state space of a system, the one modelled on $H$ . A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$ , $\lVert \psi \rVert = 1$ , determined physically up to a global phase.^✦ A unitary $U$ of $S$ , an evolution of $S$ as a closed system, is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$ .^✦ It carries a pure state $|\psi\rangle$ of $S$ to the pure state $U|\psi\rangle$ .^✦

The qudit with $d$ levels is the system modelled on $\mathbb{C}^d$ with its standard inner product.^✦ A qubit is the qudit with two levels. For a level $i \in \{0, \ldots, d-1\}$ , the computational basis state $|i\rangle$ of the qudit is the pure state whose vector is the standard basis vector of $\mathbb{C}^d$ with entry $1$ at $i$ and $0$ elsewhere.^✦ On the register, $|0\rangle$ is the state $|00\ldots0\rangle$ of the exercise.

For $d \geq 1$ , the uniform superposition $|s\rangle$ of the qudit with $d$ levels is the pure state $|s\rangle = \frac{1}{\sqrt d} \sum_{k=0}^{d-1} |k\rangle .$ (1)^✦

The Fourier Transform

Let $\omega = e^{2\pi i/d}$ be the primitive $d$ th root of unity.^✦ The Fourier matrix of dimension $d$ is the $d \times d$ complex matrix $F$ with entries $F_{kj} = \frac{1}{\sqrt d}\, \omega^{jk}, \qquad j, k = 0, \ldots, d-1 .$ (2)^✦ For $d \geq 1$ , the quantum Fourier transform $F$ of the qudit with $d$ levels is the unitary of the qudit whose matrix in the computational basis is the Fourier matrix: it carries $|j\rangle$ to $\sum_k F_{kj} |k\rangle$ .^✦

The Claim

Theorem 1. Let $d \geq 1$ . The quantum Fourier transform of the qudit with $d$ levels carries the basis state $|0\rangle$ to the uniform superposition: $F|0\rangle = |s\rangle .$ (3)^✦ For every $n$ , the quantum Fourier transform of a register of $n$ qubits carries $|00\ldots0\rangle$ to the uniform superposition of its $2^n$ basis states: $F|00\ldots0\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} |k\rangle .$ (4)^✦

What Is Checked

The claim is stated over the quantum Fourier transform $F$ of the qudit, built from the Fourier matrix (2) and the root $\omega$ and applied to the basis state $|0\rangle$ , and over the uniform superposition (1).

The library proves that the Fourier matrix is unitary, which makes the transform a unitary of the qudit. It proves that the uniform superposition has unit norm, since the sum of the $d$ basis vectors has norm $\sqrt d$ .