Quantum Fourier Transform (QFT) of a Single Qubit is Hadamard Transform

Below is the definition of QFT as illustrated in the YouTube lecture by Abraham Asfaw.

The LaTex code for the equation is as follows and also available here.

Latex
| \tilde{x} \rangle \equiv ~ QFT ~ |x \rangle ~ \equiv \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}{e^{\frac{2\pi ix y}{N}}} ~| y \rangle

For the one qubit case, N = 21 = 2:

Latex
| \tilde{x} \rangle \equiv ~ QFT ~ |x \rangle ~ \equiv \frac{1}{\sqrt{}N}\sum_{y=0}^{N-1}{e^{\frac{2\pi ix y}{N}}} ~| y \rangle

Latex
\frac{1}{\sqrt{2}}\sum_{y=0}^{1}{e^{\pi ix y}} ~| y \rangle = \frac{1}{\sqrt{2}}[~e^{i \pi x 0}~ | 0 \rangle ~ + ~ e^{i \pi x 1}~| 1 \rangle] = \frac{1}{\sqrt{2}}[~|0\rangle ~+~e^{i \pi x}~|1 \rangle~]

When x = 0:

Latex
QFT~| 0 \rangle = \frac{1}{\sqrt{2}}[~|0\rangle ~+~e^{i \pi 0}~|1 \rangle~] = \frac{1}{\sqrt{2}}[~| 0 \rangle + |1 \rangle~] = |+\rangle

When x = 1:


Latex
QFT~| 1 \rangle = \frac{1}{\sqrt{2}}[~|0\rangle ~+~e^{i \pi 1}~|1 \rangle~] = \frac{1}{\sqrt{2}}[~| 0 \rangle - |1 \rangle~] = |-\rangle

Hence the QFT of a single qubit is essentially the Hadamard transform.

Reductions among number theoretic problems – ScienceDirect

https://www.sciencedirect.com/science/article/pii/0890540187900307

The 1987 paper of Heather Woll, Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179 looks at the reduction between many problems in number theory, including primality, factorization, order-finding, discrete logarithm.

In particular the paper shows that order-finding deterministically reduces to factorization, and that factorization probabilistically reduces to order-finding (see the trick used by Shor’s algorithm).