LogoQCoder Programming Contest 004
Sign in
← Previous ProblemNext Problem →

B4: Left and Right Aligned

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 400

Writer: PSL

Editorial

First, expand kk in binary representation:

k=k0+2k1+⋯+2n−1kn(k0,k1,…,kn∈{0,1})\begin{equation} k = k_0 + 2k_1 + \cdots + 2^{n-1}k_{n} \quad (k_0, k_1, \ldots, k_n \in \{0, 1\}) \end{equation}

Then, the condition s≤k<2ns \leq k < 2^n can be rewritten as s≤ks \leq k and kn=0k_n = 0, and the condition 2n≤k<t2^n \leq k < t can be rewritten as kn=1k_n = 1 and k<tk < t.

Therefore, this problem can be solved by applying the operation in B3 twice with ∣kn⟩1\ket{k_n}_1 as the control bit:

∣k⟩n→O∣k−s⟩n(∣kn⟩=∣1⟩)\begin{equation} \ket{k}_{n} \xrightarrow{O} \ket{k - s}_{n} \quad (\ket{k_n} = \ket{1}) \end{equation} ∣k⟩n→O∣k+2n+1−t⟩n(∣kn⟩=∣0⟩)\begin{equation} \ket{k}_{n} \xrightarrow{O} \ket{k + 2^{n+1} - t}_{n} \quad (\ket{k_n} = \ket{0}) \end{equation}

For computational basis states ∣k⟩\ket{k} that satisfy k<sk < s or k≥tk \geq t, the problem does not specify the transition, so any transition is acceptable.

Sample Code

Below is a sample program:

import math
 
from qiskit import 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
 
 
# 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
 
 
# B3
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 solve(n: int, s: int, t: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1)
 
    # when k_{n-1} = 1
    qc.compose(cadd(n, 2 ** (n + 1) - t), qubits=range(n + 1), inplace=True)
 
    # when k_{n-1} = 0
    qc.x(n)
    qc.compose(cadd(n, -s), qubits=range(n + 1), inplace=True)
    qc.x(n)
 
    return qc