LogoQCoder Programming Contest 004
Sign in
← Previous ProblemNext Problem →

C3: Modular Arithmetic II

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 300

Writer: PSL

Editorial

First, expand xx in binary representation:

x=x0+2x1+⋯+2n−1xn−1(x0,x1,…,xn−1∈{0,1})\begin{equation} x = x_0 + 2x_1 + \cdots + 2^{n-1}x_{n-1} \quad (x_0, x_1, \ldots, x_{n-1} \in \{0, 1\}) \end{equation}

Then, ∣x⟩n∣y+ax mod L⟩n\ket{x}_n \ket{y + ax \ \text{mod} \ L}_n can be expanded as follows:

∣x⟩n∣y+ax mod L⟩n=∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+a(x0+2x1+⋯+2n−1xn−1) mod L⟩=∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+ax0+(2a)x1+⋯+(2n−1a)xn−1 mod L⟩\begin{align} &\ket{x}_n \ket{y + ax \ \text{mod} \ L}_n \nonumber\\ &= \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + a(x_0 + 2x_1 + \cdots + 2^{n-1}x_{n-1}) \ \text{mod} \ L} \nonumber\\ &= \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + ax_0 + (2a)x_1 + \cdots + (2^{n-1}a)x_{n-1} \ \text{mod} \ L} \end{align}

Therefore, by using the operation of problem B5 with ∣xi⟩\ket{x_i} as the control bit, the problem can be solved by repeatedly applying the controlled circuit CB5\mathrm{CB5} of problem B5.

∣x⟩n∣y mod L⟩n∣0⟩1→CB5(a)∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+ax0 mod L⟩∣0⟩→CB5(2a)∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+ax0+(2a)x1 mod L⟩∣0⟩⋯→CB5(2n−1a)∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+ax0+(2a)x1+⋯+(2n−1a)xn−1 mod L⟩∣0⟩\begin{align} &\ket{x}_n \ket{y \ \text{mod} \ L}_n \ket{0}_1 \nonumber\\ &\xrightarrow{\mathrm{CB5}(a)} \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + ax_0 \ \text{mod} \ L} \ket{0} \nonumber\\ &\xrightarrow{\mathrm{CB5}(2a)} \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + ax_0 + (2a)x_1 \ \text{mod} \ L} \ket{0} \nonumber\\ &\cdots \nonumber\\ &\xrightarrow{\mathrm{CB5}(2^{n-1}a)} \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + ax_0 + (2a)x_1 + \cdots + (2^{n-1}a)x_{n-1} \ \text{mod} \ L} \ket{0} \end{align}

Please note that the input of CB5(⋅)\mathrm{CB5}(\cdot) must be taken modulo LL.

The circuit depth is O(n2)O(n^2).

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 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 cadd(n: int, a: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1)
 
    qc.compose(qft(n), qubits=range(n), inplace=True)
    qc.compose(crot(n, a), qubits=range(n + 1), inplace=True)
    qc.compose(qft(n).inverse(), qubits=range(n), inplace=True)
 
    return qc
 
 
def ccrot(n: int, a: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 2)
 
    for i in range(n):
        theta = 2 * math.pi * a * 2**i / 2**n
        qc.mcp(theta, [n, n + 1], i)
 
    return qc
 
 
def ccadd(n: int, a: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 2)
 
    qc.compose(qft(n), qubits=range(n), inplace=True)
    qc.compose(ccrot(n, a), qubits=range(n + 2), inplace=True)
    qc.compose(qft(n).inverse(), qubits=range(n), inplace=True)
 
    return qc
 
 
def cpack(n: int, s: int, t: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 2)
 
    qc.compose(ccadd(n, 2 ** (n + 1) - t), qubits=range(n + 2), inplace=True)
    qc.x(n)
    qc.compose(ccadd(n, -s), qubits=range(n + 2), inplace=True)
    qc.x(n)
 
    return qc
 
 
def solve(n: int, a: int, L: int) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(n + 1)
    qc = QuantumCircuit(x, y)
 
    for i in range(n):
        b = (2**i * a) % L
        targets = [*y, x[i]]
        qc.compose(cadd(n + 1, 2**n - L), qubits=targets, inplace=True)
        qc.compose(cadd(n + 1, b), qubits=targets, inplace=True)
        qc.compose(cpack(n, 2**n - L + b, 2**n + b), qubits=targets, inplace=True)
        qc.compose(cadd(n + 1, b), qubits=targets, inplace=True)
 
    return qc