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

B2: XOR Oracle

実行時間制限：3 秒

メモリ制限：512 MiB

配点：200点

Writer：admin

解説

オラクルの作用後の状態 y′=y⊕x1⊕x2⊕...⊕xny' = y \oplus x_1 \oplus x_2 \oplus ... \oplus x_n は次のように括弧をつけて、2量子ビットに対する操作 ⊕\oplus の入れ子で表現されます。

y⊕x1⊕x2⊕...⊕xn=(((y⊕x1)⊕x2)⊕...)⊕xn)\begin{equation} y \oplus x_1 \oplus x_2 \oplus ... \oplus x_n = (((y \oplus x_1) \oplus x_2) \oplus ... ) \oplus x_n) \end{equation}

すなわち、x1x_1 から xnx_n までそれぞれの量子ビットを制御ビットとし、yy を標的ビットとする CXCX ゲートを合計で nn 個作用させることでオラクルを実現できます。

y→CX(x1,y)y⊕x1→CX(x2,y)y⊕x1⊕x2       ...→CX(xn,y)y⊕x1⊕x2⊕...⊕xn\begin{align} y &\xrightarrow{CX(x_1, y)} y \oplus x_1 \nonumber\\ &\xrightarrow{CX(x_2, y)} y \oplus x_1 \oplus x_2 \nonumber\\ &\ \ \ \ \ \ \ ... \nonumber\\ &\xrightarrow{CX(x_n, y)} y \oplus x_1 \oplus x_2 \oplus ... \oplus x_n\\ \end{align}

解答例

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

from qiskit import QuantumCircuit, QuantumRegister
 
 
def solve(n: int) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(1)
    qc = QuantumCircuit(x, y)
 
    for i in range(n):
      qc.cx(x[i], y)
 
    return qc