Herstellung der Gleichverteilung

Jedes Bit des ersten Registers wird mittels einer Hadamard-Transformation auf $\frac{1}{\sqrt{2}}(\vert\rangle + \vert 1\rangle )$ gesetzt, um die Zahlen $a \bmod q$ zu repräsentieren:

$$H_1 = \frac{1}{\sqrt{2}} \left( \begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array}\right) .$$ (8)

Für mehrere Bits ergibt sich somit

$$H_n = \otimes_n H_1 .$$ (9)

Dies läßt sich gut rekursiv implementieren:

$$H_n = \left( \begin{array}{rr} H_{n-1} & H_{n-1} \\ H_{n-1} & -H_{n-1} \end{array}\right) .$$ (10)

Somit erhält man, wenn man diese Transformation auf ein $x \in \{0,1\}^n$ anwendet

$$H_n \vert x\rangle \mapsto \vert\varphi\rangle = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1} (-1)^{x\cdot i} \vert i\rangle$$ (11)

($\cdot$ bezeichne hier das Standardskalarprodukt über $\mathbbm{F}_2^n$) und unser Quantencomputer zur Faktorisierung ist nach der Anwendung der Hadamard-Transformation nun in folgendem Zustand:

$$\frac{1}{\sqrt{q}} \sum_{a=0}^{q-1} \vert a\rangle \vert\rangle .$$ (12)