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

B4: Reflection Operator I

実行時間制限：3 秒

メモリ制限：512 MiB

配点：200点

Writer：Not_Leonian

解説

00 以上 2n2^n 未満の整数 xx について、量子状態 ∣x⟩\ket{x} に演算子 2∣0⟩⟨0∣−I2\ket{0}\bra{0} - I を作用させた結果は次式で表されます。

(2∣0⟩⟨0∣−I)∣x⟩=2∣0⟩⟨0∣x⟩−∣x⟩={∣x⟩(x=0)−∣x⟩(x≠0)\begin{align} (2\ket{0}\bra{0} - I) \ket{x} &= 2\ket{0} \braket{0|x} - \ket{x} \nonumber \\ &= \begin{cases} \ket{x} & (x = 0) \\ -\ket{x} & (x \neq 0) \end{cases} \end{align}

実装方針は複数考えられます。

解法1

この問題ではグローバル位相の変化を問わないことから、以下の操作を実装することを考えます。

∣x⟩→{−∣x⟩(x=0)∣x⟩(x≠0)\begin{equation} \ket{x} \xrightarrow{} \begin{cases} - \ket{x} & (x = 0) \\ \ket{x} & (x\neq 0) \end{cases} \end{equation}

全ての量子ビットに XX ゲートを作用させると、 ∣0⟩\ket{0} は ∣2n−1⟩\ket{2^n-1} になります。 さらに、どれか 11 ビットを標的ビット、残りの (n−1)(n-1) ビットを制御ビットとして複数制御 ZZ ゲートを作用させると、重ね合わせにある計算基底状態のうち ∣2n−1⟩\ket{2^n-1} のみの符号を反転させることができます。 再度全ての量子ビットに XX ゲートを作用させて戻すと、操作を実装できたことになります。

n=3n = 3 の場合の回路図は、以下の通りです。

解法2

解法1と同様に、グローバル位相の変化を問わないことを利用します。 xx の下位 (n−1)(n-1) ビットを xlx_l 、上位 11 ビットを xhx_h とします。また、 xl, xhx_l,\ x_h の全てのビットを反転させた数を、それぞれ ¬xl, ¬xh\lnot x_l,\ \lnot x_h で表すことにします。 すなわち ∣x⟩=∣xl⟩n−1∣xh⟩1\ket{x} = \ket{x_l}_{n-1} \ket{x_h}_1 が成り立ちます。

∣x⟩\ket{x} に XX ゲートを作用させた後、 nn ビット目に HH ゲートを作用させると、以下のようになります。

∣x⟩→X∣¬xl⟩n−1∣¬xh⟩1→H{12(∣¬xl⟩n−1∣0⟩1−∣¬xl⟩n−1∣1⟩1)(xh=0)12(∣¬xl⟩n−1∣0⟩1+∣¬xl⟩n−1∣1⟩1)(xh=1)\begin{equation} \ket{x} \xrightarrow{X} \ket{\lnot x_l}_{n-1} \ket{\lnot x_h}_1 \xrightarrow{H} \begin{cases} \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 - \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 + \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_h=1) \end{cases} \end{equation}

さらに、 nn ビット目を除いた (n−1)(n-1) ビットを制御ビット、nn ビット目を標的ビットとして複数制御 XX ゲートを作用させると、以下のようになります。

{12(∣¬xl⟩n−1∣0⟩1−∣¬xl⟩n−1∣1⟩1)(xh=0)12(∣¬xl⟩n−1∣0⟩1+∣¬xl⟩n−1∣1⟩1)(xh=1)→MCX{12(∣¬xl⟩n−1∣1⟩1−∣¬xl⟩n−1∣0⟩1)(xl=0, xh=0)12(∣¬xl⟩n−1∣1⟩1+∣¬xl⟩n−1∣0⟩1)(xl=0, xh=1)12(∣¬xl⟩n−1∣0⟩1−∣¬xl⟩n−1∣1⟩1)(xl≠0, xh=0)12(∣¬xl⟩n−1∣0⟩1+∣¬xl⟩n−1∣1⟩1)(xl≠0, xh=1)\begin{equation} \begin{cases} \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 - \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 + \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_h=1) \end{cases} \xrightarrow{MCX} \begin{cases} \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{1}_1 - \ket{\lnot x_l}_{n-1} \ket{0}_1) & (x_l=0, \ x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{1}_1 + \ket{\lnot x_l}_{n-1} \ket{0}_1) & (x_l=0, \ x_h=1) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 - \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_l\neq 0, \ x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 + \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_l\neq 0, \ x_h=1) \end{cases} \end{equation}

12(∣¬xl⟩n∣1⟩1−∣¬xl⟩n∣0⟩1)=−12(∣¬xl⟩n∣0⟩1−∣¬xl⟩n∣1⟩1)\frac{1}{\sqrt{2}}(\ket{\lnot x_l}_n\ket{1}_1-\ket{\lnot x_l}_n\ket{0}_1)=-\frac{1}{\sqrt{2}}(\ket{\lnot x_l}_n\ket{0}_1-\ket{\lnot x_l}_n\ket{1}_1) と 12(∣¬xl⟩n∣1⟩1+∣¬xl⟩n∣0⟩1)=12(∣¬xl⟩n∣0⟩1+∣¬xl⟩n∣1⟩1)\frac{1}{\sqrt{2}}(\ket{\lnot x_l}_n\ket{1}_1+\ket{\lnot x_l}_n\ket{0}_1)=\frac{1}{\sqrt{2}}(\ket{\lnot x_l}_n\ket{0}_1+\ket{\lnot x_l}_n\ket{1}_1) に注目して、 nn ビット目に HH ゲートを作用させた後、全ての量子ビットに XX ゲートを作用させると、以下のようになり、操作が実装できたことになります。

{12(∣¬xl⟩n−1∣1⟩1−∣¬xl⟩n−1∣0⟩1)(xl=0, xh=0)12(∣¬xl⟩n−1∣1⟩1+∣¬xl⟩n−1∣0⟩1)(xl=0, xh=1)12(∣¬xl⟩n−1∣0⟩1−∣¬xl⟩n−1∣1⟩1)(xl≠0, xh=0)12(∣¬xl⟩n−1∣0⟩1+∣¬xl⟩n−1∣1⟩1)(xl≠0, xh=1)→H{−∣¬xl⟩n−1∣¬xh⟩1(xl=0, xh=0)∣¬xl⟩n−1∣¬xh⟩1(xl≠0∨xh=1)→X{−∣x⟩(x=0)∣x⟩(x≠0)\begin{align} \begin{cases} \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{1}_1 - \ket{\lnot x_l}_{n-1} \ket{0}_1) & (x_l=0, \ x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{1}_1 + \ket{\lnot x_l}_{n-1} \ket{0}_1) & (x_l=0, \ x_h=1) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 - \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_l\neq 0, \ x_h=0) \\ \frac{1}{\sqrt{2}} (\ket{\lnot x_l}_{n-1} \ket{0}_1 + \ket{\lnot x_l}_{n-1} \ket{1}_1) & (x_l\neq 0, \ x_h=1) \end{cases} & \xrightarrow{H} \begin{cases} -\ket{\lnot x_l}_{n-1} \ket{\lnot x_h}_1 & (x_l=0, \ x_h=0) \\ \ket{\lnot x_l}_{n-1} \ket{\lnot x_h}_1 & (x_l\neq 0\lor x_h=1) \end{cases} \\ & \xrightarrow{X} \begin{cases}-\ket{x} & (x=0) \\ \ket{x} & (x\neq 0) \end{cases} \end{align}

n=3n = 3 の場合の回路図は、以下の通りです。

解答例

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

解法1

from qiskit import QuantumCircuit
from qiskit.circuit.library import ZGate
 
 
def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
    qc.append(ZGate().control(n - 1), range(n))
    qc.x(range(n))
 
    return qc

解法2

from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
    qc.h(n - 1)
    qc.mcx(list(range(n - 1)), n - 1)
    qc.h(n - 1)
    qc.x(range(n))
 
    return qc