LogoQCoder Programming Contest 005
Sign in
← Previous Problem

Ex: Reverse and Shift

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 600

Writer: PSL

Editorial

Let us first rewrite the problem into a more manageable form.

We define

X=(0110),R=(exp⁡(−2πi2n)00exp⁡(2πi2n)).\begin{equation} X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad R = \begin{pmatrix} \exp\left(- \frac{2\pi i}{2 ^n}\right) & 0 \\ 0 & \exp\left(\frac{2\pi i}{2 ^n}\right) \end{pmatrix}. \end{equation}

In fact, the operation g(m,k)g(m,k) can be represented by the matrix

XmRk.\begin{equation} X^{m} R^{k}. \end{equation}

Thus, we can rewrite the problem as follows.

  • Implement an oracle OO satisfying the following transition on a quantum circuit qc\mathrm{qc} with nn qubits.

    For any pair of integers (m,k)(m, k) satisfying 0≤m<20 \leq m < 2 and 0≤k<2n0 \leq k < 2^n, the oracle satisfies

    ∣m⟩∣k⟩n→O∣m′⟩∣k′⟩n.\ket{m}\ket{k}_n \xrightarrow{O} \ket{m'}\ket{k'}_n.

    Here, 0≤m′<20 \leq m' < 2 and 0≤k′<2n0 \leq k' < 2^n must satisfy

    Xm′Rk′=XmafterRkafterXmRkXmbeforeRkbefore.X^{m'}R^{k'} = X^{m_{\text{after}}}R^{k_{\text{after}}} X^{m}R^{k} X^{m_{\text{before}}}R^{k_{\text{before}}}.

Now, let us think about how to solve this problem.

We define the oracle EE as the transformation to the state defined in B2 and B3:

∣m⟩∣k⟩→EE(m,k)\begin{equation} \ket{m}\ket{k} \xrightarrow{E} E(m,k) \end{equation}

If we can construct such an oracle, we can solve the problem as follows.

∣m⟩∣k⟩→EE(m,k)→B2→B3E(m′,k′)→E†∣m′⟩∣k′⟩\begin{equation} \ket{m}\ket{k} \xrightarrow{E} E(m,k) \xrightarrow{\mathrm{B2}} \xrightarrow{\mathrm{B3}} E(m',k') \xrightarrow{E^{\dagger}} \ket{m'}\ket{k'} \end{equation}

By using the quantum circuits for QFT\text{QFT}, A4, and A5, we can construct a quantum state that closely resembles E(m,k)E(m,k). Finally, we apply circuits such as A2 and A3 to make minor adjustments.

The overall state transition is as follows:

∣m⟩∣k⟩n→QFT12n∑0≤c<2n−1∑0≤b<2exp⁡(2πi2n(c+2n−1b)k)∣m⟩∣c⟩n−1∣b⟩=12n∑0≤c<2n−1∑0≤b<2(−1)bkexp⁡(2πi2nck)∣m⟩∣c⟩n−1∣b⟩→A412n∑0≤b<2∑0≤c<2n−1(−1)bkexp⁡(2πi2nck)∣m⟩∣b⟩∣c⟩n−1=12n∑0≤b<2(−1)bk∣m⟩∣b⟩∣0⟩n−1+12n∑1≤c<2n−1exp⁡(2πi2nck)∣m⟩∣0⟩∣c⟩n−1+12n∑1≤c<2n−1(−1)kexp⁡(2πi2nck)∣m⟩∣1⟩∣c⟩n−1→Control - A512n∑0≤b<2(−1)bk∣m⟩∣b⟩∣0⟩n−1+12n∑1≤c<2n−1exp⁡(2πi2nck)∣m⟩∣0⟩∣c⟩n−1+12n∑1≤c<2n−1(−1)kexp⁡(2πi2nck)∣m⟩∣1⟩∣2n−1−c⟩n−1=12n∑0≤b<2(−1)bk∣m⟩∣b⟩∣0⟩n−1+12n∑1≤c<2n−1exp⁡(2πi2nck)∣m⟩∣0⟩∣c⟩n−1+12n∑1≤c<2n−1(−1)kexp⁡(2πi2n(2n−1−c)k)∣m⟩∣1⟩∣c⟩n−1=12n∑0≤b<2(−1)bk∣m⟩∣b⟩∣0⟩n−1+12n∑1≤c<2n−1exp⁡(2πi2nck)∣m⟩∣0⟩∣c⟩n−1+12n∑1≤c<2n−1exp⁡(−2πi2nck)∣m⟩∣1⟩∣c⟩n−1=12n∑0≤b<2(−1)bk∣m⟩∣b⟩∣0⟩n−1+12n∑1≤c<2n−1{exp⁡(2πi2nck)∣m⟩∣0⟩+exp⁡(−2πi2nck)∣m⟩∣1⟩}∣c⟩n−1→A212n+1∑0≤a<2∑0≤b<2(−1)am+bk∣a⟩∣b⟩∣0⟩n−1+12n∑1≤c<2n−1{exp⁡(2πi2nck)∣m⟩∣0⟩+exp⁡(−2πi2nck)∣m⟩∣1⟩}∣c⟩n−1→A312n+1∑0≤a<2∑0≤b<2(−1)am+bk∣a⟩∣b⟩∣0⟩n−1+12n∑1≤c<2n−1{exp⁡(2πi2nck)∣m⟩∣1⟩+exp⁡(−2πi2nck)∣m⟩∣0⟩}∣c⟩n−1→Adjustment12n+1∑0≤a<2∑0≤b<2(−1)am+bk∣a⟩∣b⟩∣0⟩n−1+12n∑1≤c<2n−1{exp⁡(2πi2nck)∣m⊕1⟩∣1⟩+exp⁡(−2πi2nck)∣m⟩∣0⟩}∣c⟩n−1=12n+1∑0≤a<2∑0≤b<2(−1)am+bk∣a⟩∣b⟩∣0⟩n−1+12n∑1≤c<2n−1(XmRck⊗I1⊗In−1)(∣0⟩∣0⟩+∣1⟩∣1⟩)∣c⟩n−1\begin{align} \ket{m}\ket{k}_{n} &\xrightarrow{\text{QFT}} \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq c < 2^{n-1}} \sum_{0 \leq b < 2} \exp\left(\frac{2\pi i}{2 ^n}(c+2^{n-1}b)k\right) \ket{m} \ket{c}_{n-1} \ket{b} \\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq c < 2^{n-1}} \sum_{0 \leq b < 2} (-1)^{bk} \exp\left({\frac{2\pi i}{2 ^n}ck}\right) \ket{m} \ket{c}_{n-1} \ket{b} \\ &\xrightarrow{\mathrm{A4}} \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} \sum_{0 \leq c < 2^{n-1}} (-1)^{bk} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{b} \ket{c}_{n-1} \\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} \ket{c}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} (-1)^{k} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1} \ket{c}_{n-1} \\ &\xrightarrow{\text{Control} \ \text{-} \ \mathrm{A5}} \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} \ket{c}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} (-1)^{k} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1} \ket{2^{n-1}-c}_{n-1} \\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} \ket{c}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} (-1)^{k} \exp\left(\frac{2\pi i}{2 ^n}(2^{n-1}-c)k\right) \ket{m} \ket{1} \ket{c}_{n-1}\\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} \ket{c}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1} \ket{c}_{n-1}\\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \left\lbrace\exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} + \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1}\right\rbrace\ket{c}_{n-1} \\ &\xrightarrow{\mathrm{A2}} \sqrt{\frac{1}{2^{n+1}}} \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am+bk} \ket{a} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \left\lbrace\exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} + \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1}\right\rbrace\ket{c}_{n-1} \\ &\xrightarrow{\mathrm{A3}} \sqrt{\frac{1}{2^{n+1}}} \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am+bk} \ket{a} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \left\lbrace\exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1} + \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0}\right\rbrace\ket{c}_{n-1} \\ &\xrightarrow{\text{Adjustment}} \sqrt{\frac{1}{2^{n+1}}} \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am+bk} \ket{a} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \left\lbrace\exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m \oplus 1} \ket{1} + \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0}\right\rbrace\ket{c}_{n-1} \\ &= \sqrt{\frac{1}{2^{n+1}}} \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am+bk} \ket{a} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} (X^{m}R^{ck} \otimes I_1 \otimes I_{n-1}) ( \ket{0} \ket{0} + \ket{1} \ket{1})\ket{c}_{n-1} \\ \end{align}

Therefore, we can solve this problem.

The circuit depth is O(n)O(n).

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit, QuantumRegister
from qiskit.circuit.library import ZGate, RZGate, HGate, XGate
 
 
def A2(n: int) -> QuantumCircuit:
    m, k = QuantumRegister(1), QuantumRegister(n)
    qc = QuantumCircuit(m, k)
 
    qc.x(k)
 
    qc.compose(HGate().control(len(k)), [*k, m[0]], inplace=True)
 
    qc.x(k)
 
    return qc
 
 
def A3(n: int) -> QuantumCircuit:
    m, k = QuantumRegister(1), QuantumRegister(n)
    qc = QuantumCircuit(m, k)
 
    qc.x(m[0])
 
    qc.x(k)
 
    qc.compose(XGate().control(len(k)), [*k, m[0]], inplace=True)
 
    qc.x(k)
 
    return qc
 
 
def A3_alt(n: int) -> QuantumCircuit:
    a, b, c = QuantumRegister(1), QuantumRegister(1), QuantumRegister(n - 1)
    qc = QuantumCircuit(a, b, c)
 
    qc.cx(b[0], a[0])
 
    qc.x(c)
 
    qc.compose(XGate().control(len(c) + 1), [*c, *b, *a], inplace=True)
 
    qc.x(c)
 
    return qc
 
 
def A4(n: int) -> QuantumCircuit:
    L = n + 1
    qc = QuantumCircuit(L)
 
    for i in range(L.bit_length()):
        for j in range(0, L - (2 ** i), 2 ** (i + 1)):
            qc.swap(j, j + (2 ** i))
 
    return qc
 
 
def A5_alt(n: int) -> QuantumCircuit:
    b, c = QuantumRegister(1), QuantumRegister(n - 1)
    qc = QuantumCircuit(b, c)
 
    for i in range(n-1):
        qc.compose(XGate().control(1), [b[0], c[i]], inplace=True)
 
    for i in reversed(range(1, n-1)):
        qc.compose(XGate().control(i+1), [b[0]] + [c[j]
                   for j in range(i)] + [c[i]], inplace=True)
 
    qc.compose(XGate().control(1), [b[0], c[0]], inplace=True)
 
    return qc
 
 
def B2(n: int, m_left: int, k_left: int) -> QuantumCircuit:
    a, b, c = QuantumRegister(1), QuantumRegister(1), QuantumRegister(n - 1)
    qc = QuantumCircuit(a, b, c)
 
    qc.x(c)
 
    if m_left:
        qc.compose(ZGate().control(len(c)), [*c, a[0]], inplace=True)
    if k_left % 2:
        qc.compose(ZGate().control(len(c)), [*c, b[0]], inplace=True)
 
    qc.x(c)
 
    theta = 2 * math.pi / 2 ** (n - 1)
    for i in range(n - 1):
        angle = theta * k_left * (2 ** i)
        qc.compose(RZGate(angle).control(1),
                   [c[i], a[0]], inplace=True)
 
    if m_left:
        qc.compose(A3(n - 1), [a[0], *c], inplace=True)
 
    return qc
 
 
def B3(n: int, m_right: int, k_right: int) -> QuantumCircuit:
    a, b, c = QuantumRegister(1), QuantumRegister(1), QuantumRegister(n - 1)
    qc = QuantumCircuit(a, b, c)
 
    qc.x(c)
 
    if m_right:
        qc.compose(ZGate().control(len(c)), [*c, a[0]], inplace=True)
    if k_right % 2:
        qc.compose(ZGate().control(len(c)), [*c, b[0]], inplace=True)
 
    qc.x(c)
 
    if m_right:
        qc.compose(A3(n - 1), [b[0], *c], inplace=True)
 
    theta = 2 * math.pi / 2 ** (n - 1)
    for i in range(n - 1):
        angle = theta * k_right * (2 ** i)
        qc.compose(RZGate(angle).control(1),
                   [c[i], b[0]], inplace=True)
 
    return qc
 
 
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 dqft(n: int) -> QuantumCircuit:
    a, b, c = QuantumRegister(1), QuantumRegister(1), QuantumRegister(n-1)
    qc = QuantumCircuit(a, b, c)
 
    qc.compose(qft(n), qubits=[*b, *c], inplace=True)
    qc.compose(A4(n - 1), qubits=[*b, *c], inplace=True)
    qc.compose(A5_alt(n), qubits=[*b, *c], inplace=True)
    qc.compose(A2(n - 1), qubits=[*a, *c], inplace=True)
    qc.compose(A3(n - 1), qubits=[*b, *c], inplace=True)
    qc.compose(A3_alt(n), qubits=[*a, *b, *c], inplace=True)
 
    return qc
 
 
def solve(n: int, m_before: int, k_before: int, m_after: int, k_after: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1)
 
    qc.compose(dqft(n), inplace=True)
    qc.compose(B3(n, m_before, k_before), inplace=True)
    qc.compose(B2(n, m_after, k_after), inplace=True)
    qc.compose(dqft(n).inverse(), inplace=True)
 
    return qc

Follow-up

Background for problems B and Ex

Problem B1 is based on the following fundamental idea:

  • To transform the state ∣k⟩\ket{k} into ∣k+a⟩\ket{k + a}, it suffices to apply the Fourier transform to ∣k⟩\ket{k}, then apply the phase gate, and finally perform the inverse Fourier transform to return to the computational basis.

Here, the addition "++" refers to the group operation in the cyclic group Z/2nZ\mathbb{Z} / 2^n \mathbb{Z}.

Now, the theme of this contest is to explore whether a similar approach is possible for a more structurally complex group: the dihedral group D2nD_{2^n}. The key difference between the dihedral group and the cyclic group is that the dihedral group is non-commutative in general.

Interestingly, there exists an operation analogous to the Fourier transform in the context of the dihedral group. This is the oracle EE. If you look closely at the formula for E(m,k)E(m,k), you will notice that both mm and kk appear entirely in the exponent, which strongly resembles the structure of a standard Fourier transform.

In this contest, we encourage you to focus on the following key insights:

  • Problem B2: To compute left multiplication by a group element, it suffices to apply an operation to the left bit even in the Fourier basis.
  • Problem B3: To compute right multiplication, applying an operation to the right bit in the Fourier basis is sufficient.

If you're wondering where the expression for E(m,k)E(m, k) comes from, we encourage you to look into group representation. And if you think, “I’d never come up with a circuit for oracle EE," we suggest taking a look at the hints provided below.