LogoQCoder Programming Contest 002
Sign in
← Previous EditorialNext Editorial →

B4: Quantum Fourier Transform

Time Limit: 3 seconds

Memory Limit: 512 MiB

Score: 200 points

Writer:PSL

Editorial

As described in the problem, the quantum Fourier transform (QFT) is defined as an oracle that satisfies

∣j⟩n→QFT12n∑k=02n−1exp⁡(2πijk2n)∣k⟩n\begin{equation} \ket{j}_n \xrightarrow{\mathrm{QFT}} \sqrt{\frac{1}{2^n}} \sum_{k=0}^{2^n-1} \exp{\left(\frac{2\pi i j k}{2^n}\right)} \ket{k}_n \end{equation}

Here, apart from the normalization factor 1/2n1/\sqrt{2^n}, the right-hand term can be represented as a product of independent states for each qubit:

∑k=02n−1exp⁡(2πijk2n)∣k⟩n=∑k0=01⋯∑kn−1=01exp⁡(2πij∑l=0n−1(2lkl)2n)∣k0⋯kn−1⟩=∑k0=01⋯∑kn−1=01exp⁡(2πij∑l=0n−1(2l−nkl))∣k0⋯kn−1⟩=(∑k0=01e2πij2−nk0∣k0⟩)⊗(∑k1=01e2πij21−nk1∣k1⟩)⊗⋯⊗(∑kn−1=01e2πij2−1kn−1∣kn−1⟩)=(∣0⟩+e2πi0.jn−1⋯j0∣1⟩)⊗(∣0⟩+e2πi0.jn−2⋯j0∣1⟩)⊗⋯⊗(∣0⟩+e2πi0.j0∣1⟩)\begin{align} \sum_{k=0}^{2^n-1} \exp{\left(\frac{2\pi i j k}{2^n}\right)} \ket{k}_n &= \sum_{k_0=0}^{1} \cdots \sum_{k_{n-1}=0}^{1} \exp{\left(\frac{2\pi i j \sum_{l=0}^{n-1} (2^l k_l)}{2^n}\right)} \ket{k_0 \cdots k_{n-1}} \nonumber\\ &= \sum_{k_0=0}^{1} \cdots \sum_{k_{n-1}=0}^{1} \exp{\left(2\pi i j \sum_{l=0}^{n-1} (2^{l-n} k_l)\right)} \ket{k_0 \cdots k_{n-1}} \nonumber\\ &= \left(\sum_{k_0=0}^{1} e^{2\pi i j 2^{-n} k_0}\ket{k_0}\right) \otimes \left(\sum_{k_1=0}^{1} e^{2\pi i j 2^{1-n} k_1}\ket{k_1}\right)\otimes \cdots \otimes \left(\sum_{k_{n-1}=0}^{1} e^{2\pi i j 2^{-1} k_{n-1}}\ket{k_{n-1}}\right) \nonumber\\ &= (\ket{0} + e^{2\pi i 0.j_{n-1} \cdots j_0}\ket{1}) \otimes (\ket{0} + e^{2\pi i 0.j_{n-2} \cdots j_0}\ket{1}) \otimes \cdots \otimes (\ket{0} + e^{2\pi i 0.j_{0}}\ket{1}) \end{align}

where 0.x0x1⋯xm=∑k=0m2−(k+1)xk0.x_0x_1 \cdots x_m = \sum_{k=0}^{m} 2^{-(k+1)} x_k represents a binary fraction.

Given the Equation (2), QFT can be implemented using Hadamard gates, controlled phase gates, and swap gates.

The quantum circuit diagram for the case where n=3n=3 is shown as follows.

Note that since QCoder and Qiskit use little-endian notation, the order of the qubits is reversed compared to the standard quantum circuit diagrams.

For example, in this diagram, the state of the 33rd qubit transitions as follows:

∣j2⟩→H(∣0⟩+e2πi0.j2∣1⟩)/2→CP(π/2,1,2)(∣0⟩+e2πi0.j2j1∣1⟩)/2→CP(π/4,0,2)(∣0⟩+e2πi0.j2j1j0∣1⟩)/2\begin{align} \ket{j_2} &\xrightarrow{H} (\ket{0} + e^{2\pi i 0.j_2}\ket{1})/\sqrt{2}\nonumber\\ &\xrightarrow{CP(\pi/2, 1, 2)} (\ket{0} + e^{2\pi i 0.j_2j_1}\ket{1})/\sqrt{2}\nonumber\\ &\xrightarrow{CP(\pi/4, 0, 2)} (\ket{0} + e^{2\pi i 0.j_2j_1j_0}\ket{1})/\sqrt{2} \end{align}

Finally, a swap gate exchanges this state with that of the 11st qubit, and, as a result, the final state of the 11st qubit becomes (∣0⟩+e2πi0.j2j1j0∣1⟩)/2(\ket{0} + e^{2\pi i 0.j_2j_1j_0}\ket{1})/\sqrt{2}. You can verify that the final states of the other qubits also match the expression in Equation (2).

By pushing the gates to the left, you can see that the depth of this quantum circuit is 2n2n.

The QFT is a crucial subroutine in quantum algorithms like Shor's algorithm and quantum phase estimation.

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    for i in reversed(range(n)):
        qc.h(i)
        for j in reversed(range(i)):
            qc.cp(math.pi / 2 ** (i - j), j, i)
 
    for i in range(n // 2):
        qc.swap(i, n - i - 1)
 
    return qc