B3: Less Than Oracle I

解説

計算基底状態 $\ket{0},\ \ket{1},\ ...\ \ket{L-1}$ それぞれの複素振幅 $a_i$ に $-1$ をかけていくことを考えます。

$-1$ をかける操作自体は $Z$ ゲート を利用できます。$Z$ ゲートは計算基底状態 $\ket{0}$ はそのままに、計算基底状態 $\ket{1}$ を $-\ket{1}$ に変換するような量子ゲートです。

では、重ね合わせ状態の中の特定の計算基底状態 $\ket{l}$ にのみ $Z$ ゲートを作用させるにはどうすればよいでしょうか？

これは次のように実現できます。

1. $\ket{l} = \ket{l_1 l_2 l_3 ... l_n}$ のうち、$l_i = 0$ であるようなインデックス $i$ に対して、$X$ ゲートを作用させる。こうして、$\ket{l}$ を $\ket{2^n - 1} = \ket{1...1}$ に変換する。
2. $n - 1$ ビットを制御ビット、残りの $1$ ビットを標的ビットとする複数制御 $Z$ ゲート¹を作用させます。このとき、$Z$ ゲートは重ね合わせ状態の中の計算基底状態 $\ket{l}$ にのみ作用します。
3. 1. の逆操作を行い、$\ket{2^n - 1}$ を $\ket{l}$ に戻す。

よって、この操作を計算基底状態 $\ket{0},\ \ket{1},\ ...\ \ket{L-1}$ それぞれに対して行うことで、この問題を解くことができます。

解答例

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

from qiskit import QuantumCircuit
from qiskit.circuit.library import ZGate
 
 
def solve(n: int, L: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    for l in range(L):
        for i in range(n):
            # check if i-th bit of l is 0 or 1
            if not ((l >> i) & 1):
                qc.x(i)
        if n == 1:
            qc.z(0)
        else:
            # apply multiple controlled Z gate
            qc.append(ZGate().control(n - 1), range(n))
        for i in range(n):
            if not ((l >> i) & 1):
                qc.x(i)
    return qc