LogoQCoder Programming Contest 002
Sign in
← Previous EditorialNext Editorial →

B8: Quantum Arithmetic IV

Time Limit: 3 seconds

Memory Limit: 512 MiB

Score: 200 points

Writer:PSL

Editorial

This problem can be solved by utilizing the solutions from problems B2 and B6.

The quantum circuit diagram for the case where n=2, m=2n = 2,\ m = 2 is shown as follows

,

where B6 and B2 in the quantum circuit diagram represent the quantum circuits from the solutions to problems B6 and B2, respectively. The notation B6_dg represents the inverse operation of B6.

Let's walk through the state transitions.

First, we apply the quantum phase estimation quantum circuit, which is the solution to problem B6.

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

Next, we apply the oracle, which is the solution to problem B2.

∣x⟩n∣f(x) mod 2m⟩m→B2{eiθ∣x⟩n∣f(x) mod 2m⟩mf(x)=L (mod 2m)eiθ∣x⟩n∣f(x) mod 2m⟩mf(x)≠L (mod 2m)\begin{equation} \ket{x}_{n}\ket{f(x)\ \mathrm{mod}\ 2^m}_{m} \xrightarrow{B2} \begin{cases} e^{i\theta} \ket{x}_{n}\ket{f(x)\ \mathrm{mod}\ 2^m}_{m} & f(x) = L\ (\mathrm{mod}\ 2^m )\\ \phantom{e^{i\theta}} \ket{x}_{n}\ket{f(x)\ \mathrm{mod}\ 2^m}_{m} & f(x) \neq L \ (\mathrm{mod}\ 2^m) \end{cases} \end{equation}

Finally, we apply the inverse operation of the quantum phase estimation quantum circuit, which is the solution to problem B6.

{eiθ∣x⟩n∣f(x) mod 2m⟩mf(x)=L (mod 2m)eiθ∣x⟩n∣f(x) mod 2m⟩mf(x)≠L (mod 2m)→B6†{eiθ∣x⟩n∣0⟩mf(x)=L (mod 2m)eiθ∣x⟩n∣0⟩mf(x)≠L (mod 2m)\begin{equation} \begin{cases} e^{i\theta} \ket{x}_{n}\ket{f(x)\ \mathrm{mod}\ 2^m}_{m} & f(x) = L\ (\mathrm{mod}\ 2^m )\\ \phantom{e^{i\theta}} \ket{x}_{n}\ket{f(x)\ \mathrm{mod}\ 2^m}_{m} & f(x) \neq L \ (\mathrm{mod}\ 2^m) \end{cases} \xrightarrow{{B6}^\dagger} \begin{cases} e^{i\theta} \ket{x}_{n}\ket{0}_{m} & f(x) = L\ (\mathrm{mod}\ 2^m )\\ \phantom{e^{i\theta}} \ket{x}_{n}\ket{0}_{m} & f(x) \neq L \ (\mathrm{mod}\ 2^m) \end{cases} \end{equation}

The quantum circuit depth is 4m+2 max(n,m)+54m + 2\ \mathrm{max}(n, m) + 5.

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit, QuantumRegister
 
 
def phase_estimation(n: int, m: int, S: list[int]) -> QuantumCircuit:
    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
 
    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
 
 
def rotation_L(n: int, L: int, theta: float) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    for i in range(n):
        if not (1 << i) & L:
            qc.x(i)
 
    if n == 1:
        qc.p(theta, n - 1)
    else:
        qc.mcp(theta, list(range(n - 1)), n - 1)
 
    for i in range(n):
        if not (1 << i) & L:
            qc.x(i)
 
    return qc
 
 
def solve(n: int, m: int, L: int, S: list[int], theta: float) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(m)
    qc = QuantumCircuit(x, y)
 
    oracle = phase_estimation(n, m, S)
 
    qc.compose(oracle, inplace=True)
    qc.compose(rotation_L(m, L, theta), y, inplace=True)
    qc.compose(oracle.inverse(), inplace=True)
 
    return qc