LogoQCoder Programming Contest 004
Sign in
← Previous ProblemNext Problem →

C4: Modular Arithmetic III

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 400

Writer: PSL

Editorial

By combining the operation in problem C3 and the SWAP gate, you can achieve the desired transition.

∣x⟩n∣0⟩n+1→C3(a)∣x⟩n∣0+ax mod L⟩n+1=∣x⟩n∣ax mod L⟩n+1→SWAP∣ax mod L⟩n∣x⟩n+1→C3(−a−1)∣ax mod L⟩n∣x+(−a−1)ax mod L⟩n+1=∣ax mod L⟩n∣0⟩n+1\begin{align} &\ket{x}_{n} \ket{0}_{n+1} \nonumber\\ &\xrightarrow{\mathrm{C3}(a)} \ket{x}_{n} \ket{0 + ax \ \text{mod} \ L}_{n+1} = \ket{x}_n \ket{ax \ \text{mod} \ L}_{n+1} \nonumber\\ &\xrightarrow{\mathrm{SWAP}} \ket{ax \ \text{mod} \ L}_n \ket{x}_{n+1} \nonumber\\ &\xrightarrow{\mathrm{C3}(-a^{-1})} \ket{ax \ \text{mod} \ L}_n \ket{x + (-a^{-1})ax \ \text{mod} \ L}_{n+1} = \ket{ax \ \text{mod} \ L}_{n} \ket{0}_{n+1} \end{align}

You can use the solution to problem C2 to calculate the inverse element a−1 mod La^{-1} \bmod L.

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 add_ax_mod(n: int, L: int, a: 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
 
 
def inv_mod(a: int, L: int) -> int:
    def extended_euclidean(a: int, b: int) -> tuple[int, int, int]:
        if b == 0:
            return a, 1, 0
 
        gcd, x1, y1 = extended_euclidean(b, a % b)
 
        x = y1
        y = x1 - (a // b) * y1
 
        return gcd, x, y
 
    _, x, _ = extended_euclidean(a, L)
 
    return x % L
 
 
def solve(n: int, a: int, L: int) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(n + 1)
    qc = QuantumCircuit(x, y)
 
    qc.compose(add_ax_mod(n, L, a), qubits=range(2 * n + 1), inplace=True)
 
    for i in range(n):
        qc.swap(x[i], y[i])
 
    b = -inv_mod(a, L) % L
    qc.compose(add_ax_mod(n, L, b), qubits=range(2 * n + 1), inplace=True)
 
    return qc