LogoQCoder Programming Contest 004
Sign in
← Previous ProblemNext Problem →

A7: Zeta / Moebius Transform II

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 300

Writer: fortoobye

Editorial

In this problem, you can apply the idea from problem A6.

Let's consider the exampleof n=2n = 2 below.

It is important to treat the first and third qubits as one pair and the second and fourth qubits as another pair, as shown in the figure above. Same type of quantum gate is applied to each pair.

From here, let's examine the state transitions induced by each quantum gate.

Consider the superposition state of ∣0000⟩,∣1000⟩,∣0100⟩,∣1100⟩\ket{0000}, \ket{1000}, \ket{0100}, \ket{1100}, where a0,a1,a2,a3a_0, a_1, a_2, a_3 are the probability amplitudes of each state.

a0∣0000⟩+a1∣1000⟩+a2∣0100⟩+a3∣1100⟩=(a0∣00⟩+a1∣10⟩+a2∣01⟩+a3∣11⟩)∣00⟩\begin{equation} a_0 \ket{0000} + a_1 \ket{1000} + a_2 \ket{0100} + a_3 \ket{1100} = (a_0 \ket{00} + a_1 \ket{10} + a_2 \ket{01} + a_3 \ket{11}) \ket{00} \end{equation}

First, apply RyRy gate with θ=2arctan⁡(2)\theta = 2 \arctan{(\sqrt{2})}.

(a0∣00⟩+a1∣10⟩+a2∣01⟩+a3∣11⟩)∣00⟩→Ry(θ,2)→Ry(θ,3)(a0∣00⟩+a1∣10⟩+a2∣01⟩+a3∣11⟩)(13∣0⟩+23∣1⟩)(13∣0⟩+23∣1⟩)\begin{align} &(a_0 \ket{00} + a_1 \ket{10} + a_2 \ket{01} + a_3 \ket{11}) \ket{00} \nonumber \\ &\xrightarrow{Ry(\theta, 2)} \xrightarrow{Ry(\theta, 3)} (a_0 \ket{00} + a_1 \ket{10} + a_2 \ket{01} + a_3 \ket{11}) \left( \frac{1}{\sqrt{3}} \ket{0} + \frac{\sqrt{2}}{\sqrt{3}} \ket{1}\right) \left( \frac{1}{\sqrt{3}} \ket{0} + \frac{\sqrt{2}}{\sqrt{3}} \ket{1}\right) \end{align}

Next, generate a state that can be enclosed in 1/31/3 by applying the controlled HH gate.

(a0∣00⟩+a1∣10⟩+a2∣01⟩+a3∣11⟩)(13∣0⟩+23∣1⟩)(13∣0⟩+23∣1⟩)→CH(2,0)→CH(3,1)13(a0∣0000⟩+a1∣1000⟩+a2∣0100⟩+a3∣1100⟩+(a0+a1)∣0010⟩+(a0−a1)∣1010⟩+(a2+a3)∣0110⟩+(a2−a3)∣1110⟩+(a1+a3)∣1001⟩+(a1−a3)∣1101⟩+(a0+a2)∣0001⟩+(a0−a2)∣0101⟩+(a0+a1+a2+a3)∣0011⟩+(a0−a1+a2−a3)∣1011⟩+(a0+a1−a2−a3)∣0111⟩+(a0−a1−a2+a3)∣1111⟩)\begin{align} &(a_0 \ket{00} + a_1 \ket{10} + a_2 \ket{01} + a_3 \ket{11}) \left( \frac{1}{\sqrt{3}} \ket{0} + \frac{\sqrt{2}}{\sqrt{3}} \ket{1}\right) \left( \frac{1}{\sqrt{3}} \ket{0} + \frac{\sqrt{2}}{\sqrt{3}} \ket{1}\right) \nonumber \\ &\xrightarrow{CH(2, 0)} \xrightarrow{CH(3, 1)} \frac{1}{3} (a_0 \ket{0000} + a_1 \ket{1000} + a_2 \ket{0100} + a_3 \ket{1100} \nonumber \\ &\hspace{30mm} + (a_0 + a_1) \ket{0010} + (a_0 - a_1) \ket{1010} + (a_2 + a_3) \ket{0110} + (a_2 - a_3) \ket{1110} \nonumber \\ &\hspace{30mm} + (a_1 + a_3) \ket{1001} + (a_1 - a_3) \ket{1101} + (a_0 + a_2) \ket{0001} + (a_0 - a_2) \ket{0101} \nonumber \\ &\hspace{30mm} + (a_0 + a_1 + a_2 + a_3) \ket{0011} + (a_0 - a_1 + a_2 - a_3) \ket{1011} \nonumber \\ &\hspace{30mm} + (a_0 + a_1 - a_2 - a_3) \ket{0111} + (a_0 - a_1 - a_2 + a_3) \ket{1111}) \end{align}

Then, apply the XX gate and the controlled XX gate to swap the probability amplitudes.

13(a0∣0000⟩+a1∣1000⟩+a2∣0100⟩+a3∣1100⟩+(a0+a1)∣0010⟩+(a0−a1)∣1010⟩+(a2+a3)∣0110⟩+(a2−a3)∣1110⟩+(a1+a3)∣1001⟩+(a1−a3)∣1101⟩+(a0+a2)∣0001⟩+(a0−a2)∣0101⟩+(a0+a1+a2+a3)∣0011⟩+(a0−a1+a2−a3)∣1011⟩+(a0+a1−a2−a3)∣0111⟩+(a0−a1−a2+a3)∣1111⟩)→X(0)→CX(0,2)→X(0)→X(1)→CX(1,3)→X(1)13((a0+a1+a2+a3)∣0000⟩+(a1+a3)∣1000⟩+(a2+a3)∣0100⟩+a3∣1100⟩+(a0+a2)∣0010⟩+(a0−a1+a2−a3)∣1010⟩+a2∣0110⟩+(a2−a3)∣1110⟩+(a0+a1)∣0001⟩+(a0+a1−a2−a3)∣0101⟩+a1∣1001⟩+(a1−a3)∣1101⟩+a0∣0011⟩+(a0−a1)∣1011⟩+(a0−a2)∣0111⟩+(a0−a1−a2+a3)∣1111⟩)\begin{align} &\frac{1}{3} (a_0 \ket{0000} + a_1 \ket{1000} + a_2 \ket{0100} + a_3 \ket{1100} \nonumber \\ &\hspace{10mm} + (a_0 + a_1) \ket{0010} + (a_0 - a_1) \ket{1010} + (a_2 + a_3) \ket{0110} + (a_2 - a_3) \ket{1110} \nonumber \\ &\hspace{10mm} + (a_1 + a_3) \ket{1001} + (a_1 - a_3) \ket{1101} + (a_0 + a_2) \ket{0001} + (a_0 - a_2) \ket{0101} \nonumber \\ &\hspace{10mm} + (a_0 + a_1 + a_2 + a_3) \ket{0011} + (a_0 - a_1 + a_2 - a_3) \ket{1011} \nonumber \\ &\hspace{10mm} + (a_0 + a_1 - a_2 - a_3) \ket{0111} + (a_0 - a_1 - a_2 + a_3) \ket{1111}) \nonumber \\ &\xrightarrow{X(0)} \xrightarrow{CX(0, 2)} \xrightarrow{X(0)} \xrightarrow{X(1)} \xrightarrow{CX(1, 3)} \xrightarrow{X(1)} \nonumber \\ &\frac{1}{3} ((a_0 + a_1 + a_2 + a_3) \ket{0000} + (a_1 + a_3) \ket{1000} + (a_2 + a_3) \ket{0100} + a_3 \ket{1100} \nonumber \\ &\hspace{10mm} + (a_0 + a_2) \ket{0010} + (a_0 - a_1 + a_2 - a_3) \ket{1010} + a_2 \ket{0110} + (a_2 - a_3) \ket{1110} \nonumber \\ &\hspace{10mm} + (a_0 + a_1) \ket{0001} + (a_0 + a_1 - a_2 - a_3) \ket{0101} + a_1 \ket{1001} + (a_1 - a_3) \ket{1101} \nonumber \\ &\hspace{10mm} + a_0 \ket{0011} + (a_0 - a_1) \ket{1011} + (a_0 - a_2) \ket{0111} + (a_0 - a_1 - a_2 + a_3) \ket{1111}) \end{align}

Finally, by applying the CZCZ gate, the sign of the probability amplitudes of the state where "the first and third qubits are both 11" or "the second and fourth qubits are both 11" is reversed.

13((a0+a1+a2+a3)∣0000⟩+(a1+a3)∣1000⟩+(a2+a3)∣0100⟩+a3∣1100⟩+(a0+a2)∣0010⟩+(a0−a1+a2−a3)∣1010⟩+a2∣0110⟩+(a2−a3)∣1110⟩+(a0+a1)∣0001⟩+(a0+a1−a2−a3)∣0101⟩+a1∣1001⟩+(a1−a3)∣1101⟩+a0∣0011⟩+(a0−a1)∣1011⟩+(a0−a2)∣0111⟩+(a0−a1−a2+a3)∣1111⟩)→CZ(2,0)→CZ(3,1)13((a0+a1+a2+a3)∣0000⟩+(a1+a3)∣1000⟩+(a2+a3)∣0100⟩+a3∣1100⟩+(a0+a2)∣0010⟩−(a0−a1+a2−a3)∣1010⟩+a2∣0110⟩−(a2−a3)∣1110⟩+(a0+a1)∣0001⟩−(a0+a1−a2−a3)∣0101⟩+a1∣1001⟩−(a1−a3)∣1101⟩+a0∣0011⟩−(a0−a1)∣1011⟩−(a0−a2)∣0111⟩+(a0−a1−a2+a3)∣1111⟩)\begin{align} &\frac{1}{3} ((a_0 + a_1 + a_2 + a_3) \ket{0000} + (a_1 + a_3) \ket{1000} + (a_2 + a_3) \ket{0100} + a_3 \ket{1100} \nonumber \\ &\hspace{10mm} + (a_0 + a_2) \ket{0010} + (a_0 - a_1 + a_2 - a_3) \ket{1010} + a_2 \ket{0110} + (a_2 - a_3) \ket{1110} \nonumber \\ &\hspace{10mm} + (a_0 + a_1) \ket{0001} + (a_0 + a_1 - a_2 - a_3) \ket{0101} + a_1 \ket{1001} + (a_1 - a_3) \ket{1101} \nonumber \\ &\hspace{10mm} + a_0 \ket{0011} + (a_0 - a_1) \ket{1011} + (a_0 - a_2) \ket{0111} + (a_0 - a_1 - a_2 + a_3) \ket{1111}) \nonumber \\ &\xrightarrow{CZ(2, 0)} \xrightarrow{CZ(3, 1)} \nonumber \\ &\frac{1}{3} ((a_0 + a_1 + a_2 + a_3) \ket{0000} + (a_1 + a_3) \ket{1000} + (a_2 + a_3) \ket{0100} + a_3 \ket{1100} \nonumber \\ &\hspace{10mm} + (a_0 + a_2) \ket{0010} - (a_0 - a_1 + a_2 - a_3) \ket{1010} + a_2 \ket{0110} - (a_2 - a_3) \ket{1110} \nonumber \\ &\hspace{10mm} + (a_0 + a_1) \ket{0001} - (a_0 + a_1 - a_2 - a_3) \ket{0101} + a_1 \ket{1001} - (a_1 - a_3) \ket{1101} \nonumber \\ &\hspace{10mm} + a_0 \ket{0011} - (a_0 - a_1) \ket{1011} - (a_0 - a_2) \ket{0111} + (a_0 - a_1 - a_2 + a_3) \ket{1111}) \end{align}

By summarizing the operations above, the state transitions are as follows. However, the states where both the third and fourth qubits are both 00 or both 11 are omitted because their probability amplitudes do not matter in this problem.

a0∣0000⟩+a1∣1000⟩+a2∣0100⟩+a3∣1100⟩→qc13((a0+a1+a2+a3)∣0000⟩+(a1+a3)∣1000⟩+(a2+a3)∣0100⟩+a3∣1100⟩+a0∣0011⟩−(a0−a1)∣1011⟩−(a0−a2)∣0111⟩+(a0−a1−a2+a3)∣1111⟩)\begin{align} &a_0 \ket{0000} + a_1 \ket{1000} + a_2 \ket{0100} + a_3 \ket{1100} \nonumber\\ &\xrightarrow{\mathrm{qc}} \frac{1}{3} ((a_0 + a_1 + a_2 + a_3) \ket{0000} + (a_1 + a_3) \ket{1000} + (a_2 + a_3) \ket{0100} + a_3 \ket{1100} \nonumber \\ &\hspace{10mm} + a_0 \ket{0011} - (a_0 - a_1) \ket{1011} - (a_0 - a_2) \ket{0111} + (a_0 - a_1 - a_2 + a_3) \ket{1111}) \end{align}

When n=2n = 2, the formula shown in the problem statement is given by

13n∑S⊆T⊆[n]aT∣S⟩n∣0⟩n+13n∑T⊆S⊆[n](−1)(∣S∣−∣T∣)aT∣S⟩n∣2n−1⟩n=13((a0+a1+a2+a3)∣0000⟩+(a1+a3)∣1000⟩+(a2+a3)∣0100⟩+a3∣1100⟩+a0∣0011⟩−(a0−a1)∣1011⟩−(a0−a2)∣0111⟩+(a0−a1−a2+a3)∣1111⟩).\begin{align} &\sqrt{\frac{1}{3^n}} \sum_{S \subseteq T \subseteq [n]} a_T \ket{S}_n \ket{0}_n + \sqrt{\frac{1}{3^n}} \sum_{T \subseteq S \subseteq [n]} (-1)^{(|S| - |T|)} a_T \ket{S}_n \ket{2^n - 1}_n \nonumber\\ &= \frac{1}{3} ((a_0 + a_1 + a_2 + a_3) \ket{0000} + (a_1 + a_3) \ket{1000} + (a_2 + a_3) \ket{0100} + a_3 \ket{1100} \nonumber \\ &\hspace{10mm} + a_0 \ket{0011} - (a_0 - a_1) \ket{1011} - (a_0 - a_2) \ket{0111} + (a_0 - a_1 - a_2 + a_3) \ket{1111}). \end{align}

By comparing the equations (6)(6) and (7)(7), it is confirmed that the desired quantum state is prepared by the operations.

By performing this operation for general nn, the problem can be solved.

Follow-up

As the problem name suggests, the probability amplitudes of each state in

13n∑S⊆T⊆[n]aT∣S⟩n∣0⟩n\begin{equation} \sqrt{\frac{1}{3^n}} \sum_{S \subseteq T \subseteq [n]} a_T \ket{S}_n \ket{0}_n \end{equation}

corredpond to the Zeta transform, and those in

13n∑T⊆S⊆[n](−1)(∣S∣−∣T∣)aT∣S⟩n∣2n−1⟩n\begin{equation} \sqrt{\frac{1}{3^n}} \sum_{T \subseteq S \subseteq [n]} (-1)^{(|S| - |T|)} a_T \ket{S}_n \ket{2^n - 1}_n \end{equation}

correspond to the Mobius transform.

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(2 * n)
 
    theta = 2 * math.atan(math.sqrt(2))
 
    for i in range(n):
        qc.ry(theta, i + n)
        qc.ch(n + i, i)
        qc.x(i)
        qc.cx(i, n + i)
        qc.x(i)
        qc.cz(n + i, i)
 
    return qc