LogoQCoder Programming Contest 004
Sign in
← Previous EditorialNext Editorial →

A7: Zeta / Moebius Transform II

Time Limit: 3 seconds

Memory Limit: 512 MiB

Score: 300 points

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 11st and 33rd qubits as one pair and the 22nd and 44th 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 complex 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 complex 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 controlled ZZ gate, the sign of the complex amplitudes of the state where "the 11st and 33rd qubits are both 11" or "the 22nd and 44th 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 33rd and 44th qubits are both 00 or both 11 are omitted because their complex 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 complex 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