LogoQCoder Programming Contest 002
Sign in
← Previous ProblemNext Problem →

B4: Quantum Fourier Transform

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 200

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, 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⟩)⊗(∑k0=01e2πij21−nk1∣k1⟩)⊗⋯⊗(∑k0=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_0=0}^{1} e^{2\pi i j 2^{1-n} k_1}\ket{k_1}\right)\otimes \cdots \otimes \left(\sum_{k_0=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=0m−12−(k+1)xk0.x_0x_1 \cdots x_m = \sum_{k=0}^{m-1} 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 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 circuit diagrams.

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

∣j2⟩→H(∣0⟩+e2πi0.j2∣1⟩)/2→CP(π/2,1,0)(∣0⟩+e2πi0.j2j1∣1⟩)/2→CP(π/4,2,0)(∣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, 0)} (\ket{0} + e^{2\pi i 0.j_2j_1}\ket{1})/\sqrt{2}\nonumber\\ &\xrightarrow{CP(\pi/4, 2, 0)} (\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 first qubit, and, as a result, the final state of the first 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 circuit is 2n2n.

The Quantum Fourier Transform 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