QCoder

Editorial

This problem can be solved by applying a quantum algorithm known as quantum phase estimation, using the oracle from Problem B5.

The circuit diagram for the case where $n = 2$ and $m = 2$ is shown as follows.

Next, we will look at the state transition of the register $\ket{y}_m$ with the computational basis state $\ket{x}_n$ in the upper $n$ qubits.

First, we apply the Hadamard gate to each qubit of the register $\ket{y}_m = \ket{0}$ to create a uniform superposition state.

\begin{align} \ket{0}_m &\xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \ket{k}_m \nonumber\\ &= \frac{1}{\sqrt{2^m}} (\ket{0} + \ket{1}) \otimes (\ket{0} + \ket{1}) \otimes \cdots \otimes (\ket{0} + \ket{1}) \end{align}

In Problem B5, we implemented an oracle that realizes the transition given by

\begin{equation} \ket{x} \xrightarrow{O} \exp{\left(\frac{2\pi i f(x)}{2^m}\right)}\ket{x}. \end{equation}

Here, we define an oracle $P_{S}^{2^j}$ that realizes a transition where the phase of this oracle is multiplied by $2^j$ .

\begin{equation} \ket{x} \xrightarrow{P_{S}^{2^j}} \exp{\left(\frac{2\pi i f(x)}{2^m} \cdot 2^j\right)}\ket{x} \end{equation}

Next, we apply the oracles $P_{S}^{2^j}$ to $\ket{x}$ using the $j$ th qubit of the register $\ket{y}_m$ as the control bit.

\begin{align} &\frac{1}{\sqrt{2^m}} (\ket{0} + \ket{1}) \otimes (\ket{0} + \ket{1}) \otimes \cdots \otimes (\ket{0} + \ket{1}) \nonumber \\ \xrightarrow{P_S^{2^0}, P_S^{2^1}, \cdots, P_S^{2^{m-1}}} &\frac{1}{\sqrt{2^m}} (\ket{0} + e^{\frac{2\pi i f(x)\cdot 2^0}{2^m}}\ket{1}) \otimes (\ket{0} + e^{\frac{2\pi i f(x)\cdot 2^1}{2^m}}\ket{1}) \otimes \cdots \otimes (\ket{0} + e^{\frac{2\pi i f(x)\cdot 2^{m-1}}{2^m}}\ket{1}) \nonumber\\ = &\frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} e^{\frac{2\pi i f(x)k}{2^m}} \ket{k}_m \end{align}

Finally, by applying the inverse quantum Fourier transform (which was implemented in Problem B4) to the register $\ket{y}_m$ , we can transition the register to the desired state.

\begin{align} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} e^{\frac{2\pi i f(x)k}{2^m}} \ket{k}_m \xrightarrow{\mathrm{IQFT}} \ket{f(x)}_m \end{align}

The transition in Equation (5) is clear from the definition of the quantum Fourier transform given by

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

With these steps, we can implement a quantum circuit that realizes the following state transition.

\begin{equation} \ket{x}_{n}\ket{0}_{m} \xrightarrow{\mathrm{qc}} \ket{x}_{n}\ket{f(x)\ \mathrm{mod}\ 2^m}_{m} \end{equation}

The circuit depth is $1 + \mathrm{max}(n, m) + 2m$ .

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
 
 
def solve(n: int, m: int, S: list[int]) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(m)
    qc = QuantumCircuit(x, y)
 
    qc.h(y)
 
    for j in range(m):
        for i in range(n):
            theta = (2 * math.pi * S[i] / 2**m) * 2**j
            qc.cp(theta, x[i], y[j])
 
    qc.compose(qft(m).inverse(), y, inplace=True)
 
    return qc

B6: Quantum Arithmetic II

Editorial

Sample Code