LogoQCoder Programming Contest 004
ログイン
← 前の解説次の解説 →

A7: Zeta / Moebius Transform II

実行時間制限：3 秒

メモリ制限：512 MiB

配点：300点

Writer：fortoobye

解説

問題 A6 の発想を利用することで、この問題を解くことができます。

以下の n=2n = 2 の例をみてみましょう。

この図のように、11 番目と 33 番目の量子ビットを1つの組、22 番目と 44 番目の量子ビットをもう1つの組として扱うことが重要です。 各組には同じ種類の量子ゲートが作用されています。

ここから、各量子ゲートによってどのような状態遷移が起きているかを具体的に確認してみます。

はじめに、以下のような状態 ∣0000⟩,∣1000⟩,∣0100⟩,∣1100⟩\ket{0000}, \ket{1000}, \ket{0100}, \ket{1100} の重ね合わせ状態を考えます。ただし、a0,a1,a2,a3a_0, a_1, a_2, a_3 は各状態の複素振幅です。

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}

まず、この状態にθ=2arctan⁡(2)\theta = 2 \arctan{(\sqrt{2})} として RyRy ゲートを作用させます。

(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}

次に、制御 HH ゲートを作用させることで、1/31 / 3 で括ることができる重ね合わせ状態を生成します。

(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}

そして、XX ゲートと制御 XX ゲートを作用させることで、複素振幅を適切に入れ替えます。

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}

最後に、制御 ZZ ゲートを作用させることで、「1番目と3番目の量子ビットが両方とも 11」もしくは「2番目と4番目の量子ビットが両方とも 11」となる状態の複素振幅の正負を反転させます。

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}

以上の操作をまとめると、次のような状態遷移が成り立ちます。 ただし、3番目と4番目の量子ビットが両方とも 00、あるいは両方とも 11 である場合以外の状態については、その複素振幅を考慮しないため、ここではそれらの状態を省略します。

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}

ここで n=2n = 2 の場合、問題文に示されている式は

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}

であるので、(6)(6) 式と (7)(7) 式を比較すると、それらが一致していることが分かります。 以上のことから、ここで行なっている操作によって、目的の量子状態が正しく生成されていることを確認できます。

この操作を一般の nn について行うことで、この問題を解くことができます。

参考

この問題の問題名にあるように、

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}

の各状態の複素振幅がゼータ変換に対応して、

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}

の各状態の複素振幅がメビウス変換に対応しています。

解答例

解答例は以下の通りです。

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