B4: Less Than Oracle II

解説

以下、$\ket{L} = \ket{L_1, ..., L_n}$ のように整数 $L$ の $i$ 番目のビットを $L_i$ と表すこととします。

はじめに、オラクルの対象となる整数の集合 $A = \left\{0,\ 1,\ ...,\ L-1\right\}$ を次のように分解します。

すなわち、$A$ は $i$ 番目のビットが $L$ より小さく、$i+1$ から $n$ 番目までのビットがすべて $L$ と等しいような集合 $A_i$ のインデックス $i$ に関する和集合と言い換えることができます。なお、$(X_i < L_i)$ は $(X_i = 0 \land L_i = 1)$ と等価です。

例として $\ket{L} = \ket{5} = \ket{101}$ の場合を考えます。

• $i=1$ のとき、 $A_1 = \left\{\ket{X} \mid (X_1 < 1) \land ((X_2 = 0) \land (X_3 = 1)) \right\} = \{\ket{001} = \ket{4}\}$
• $i=2$ のとき、$A_2 = \left\{\ket{X} \mid (X_2 < 0) \land (X_3 = 1) \right\} = \{\}$
• $i=3$ のとき、$A_3 = \left\{\ket{X} \mid (X_3 < 1) \right\} = \{\ket{000} = \ket{0}, \ket{100} = \ket{1}, \ket{010} = \ket{2}, \ket{110} = \ket{3}\}$

よって、$A = A_1 \cup A_2 \cup A_3 = \{\ket{0}, \ket{1}, \ket{2}, \ket{3}, \ket{4}\}$ と計算でき、無事 $L = 5$ 未満の状態を列挙できます。

このような分解を元に、インデックス $i$ それぞれの集合に対して $Z$ ゲートを作用させることでオラクルを実現できます。

各インデックスにおいて 2 つの条件 $X_i < L_i$ と $((X_{i+1} = L_{i+1}) \land ... \land (X_n = L_n))$ は量子ゲートを用いて次のように表現できます。

• $X_i < L_i$:
  1. $L_i = 0$ の場合には何もしない（ゲートを作用させずにスキップする）
• $((X_{i+1} = L_{i+1}) \land ... \land (X_n = L_n))$:
  1. $i+1$ から $n$ ビット目までのインデックス $j$ に対して、$L_j = 0$ ならば $j$ 番目の量子ビットに $X$ ゲートを作用させる。
  2. $i$ 番目の量子ビットに $X$ ゲートを作用させる。( $X_i = 0$ の場合に $-1$ をかけるため)
  3. 複数制御 $Z$ ゲートを $i+1$ から $n$ ビット目までを制御ビット、$i$ ビット目を標的ビットとして作用させる。
  4. 2. と 1. の逆操作を行う。

解答例

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

from qiskit import QuantumCircuit
from qiskit.circuit.library import ZGate
 
 
def solve(n: int, L: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    for i in range(n):
        if not (L >> i) & 1:
            continue
        for j in range(i + 1, n):
            if not (L >> j) & 1:
                qc.x(j)
        qc.x(i)
        if i == n - 1:
            qc.z(i)
        else:
            qc.append(ZGate().control(n - i - 1), range(i, n))
        qc.x(i)
        for j in range(i + 1, n):
            if not (L >> j) & 1:
                qc.x(j)
 
    return qc

補足

• 問題 B3 では、オラクルの対象となるすべての状態にそれぞれ対応した量子ゲートを作用させる実装が想定解法となっていますが、これは貪欲法であり非効率的です。量子アルゴリズムが古典アルゴリズムに対して計算量の観点で優位性を発揮するには、回路の深さの浅い効率的なオラクルを実装する必要があります。
• より効率的なオラクルの実装法が文献 [1] にて提案されています。

References

• [1] J. Sanchez-Rivero et al., “Automatic generation of an efficient less-than oracle for quantum amplitude amplification,” in 2023 IEEE/ACM 4th International Workshop on Quantum Software Engineering (Q-SE), May 2023, pp. 26–33. (https://arxiv.org/abs/2303.07120)