QCoder

Editorial

The quantum Fourier transform (QFT) is defined as follows:

An $n$ -qubit quantum oracle that satisfies the following transition for any integer $j$ from $0$ (inclusive) to $2^n$ (exclusive).

\begin{equation} \ket{k}_n \xrightarrow{\mathrm{QFT}} \sqrt{\frac{1}{2^n}} \sum_{j=0}^{2^n-1} \exp{\left(\frac{2\pi i j k}{2^n}\right)} \ket{j}_n \end{equation}

Therefore, you can solve this problem by using QFT, the operation in Problem B2 (controlled phase shift) and the inverse QFT.

\begin{align} \ket{k}_n\ket{c}_1 &\xrightarrow{\mathrm{QFT}} \sqrt{\frac{1}{2^n}} \sum_{j=0}^{2^n-1} \exp{\left(\frac{2\pi i j k}{2^n}\right)} \ket{j}_n\ket{c}_1 \nonumber\\ &\xrightarrow{\text{operation from Problem B2}} \sqrt{\frac{1}{2^n}} \sum_{j=0}^{2^n-1} \exp{\left(\frac{2\pi i(k + ca)j}{2^n}\right)} \ket{j}_n\ket{c}_1 \nonumber\\ &\xrightarrow{\mathrm{IQFT}} \ket{(k + ca) \bmod 2^n}_n \ket{c}_1 \end{align}

You don't have to make $\mathrm{QFT}$ and $\mathrm{IQFT}$ as controlled gates. The quantum circuit depth is $O(n)$ .

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit, QuantumRegister
 
 
def qft(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
 
 
# B2
def crot(n: int, a: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1)
 
    for i in range(n):
        theta = 2 * math.pi * a * 2**i / 2**n
        qc.cp(theta, n, i)
 
    return qc
 
 
def solve(n: int, a: int) -> QuantumCircuit:
    k, c = QuantumRegister(n), QuantumRegister(1)
    qc = QuantumCircuit(k, c)
 
    qc.compose(qft(n), qubits=k, inplace=True)
    qc.compose(crot(n, a), qubits=[*k, *c], inplace=True)
    qc.compose(qft(n).inverse(), qubits=k, inplace=True)
 
    return qc

B3: Controlled Constant Addition

Editorial

Sample Code