Q#のGrover の探索アルゴリズムのサンプルコードをのぞいてみる　その1

ひとりAdvent Calendar 20日目です。

前回に引き続き今回はGroverの探索アルゴリズムのサンプルを覗いてみます。サンプルプロジェクトはこれです。

Quantum/Samples/src/DatabaseSearch at release/v0.3.1810 · Microsoft/Quantum · GitHub

さて、Groverの探索アルゴリズムというのはランダムな並んだデータベースからある条件を満たす1つの要素を探すアルゴリズムです。こちらの記事がわかりやすかったです。

で、その記事の最初にあるようにもう少し一般的には逆関数の導出、あるいは重ね合わせられた量子状態から1つだけ反転させた(markされた)量子ビットの検出を行います。このQ#のサンプルではどの量子ビットの検出を行うかは次のように固定されています。

For the first example, we start by hard coding an oracle D that always marks only the item k = N - 1 for N = 2ⁿ and for n a positive integer. Note that n is the number of qubits needed to encode the database element index k.

つまり、n量子ビットからなるデータベースが与えられたとき、 ${2^ n - 1}$ というインデックスで示される状態 ${|11\dots11⟩}$ を探します。

Program.csクラスを見るとわかるように、Random Database Search with Manual Oracle Definitions、Quantum Database Search with Manual Oracle DefinitionsとMultiple Element Quantum Database Search with the Canonの3つのサンプルを動かしています。今日は最初のRandom Database Search with Manual Oracle Definitionsを見てみます。最初の二つはプリミティブなoperationを使った実装で最後がQ# SDKが提供している便利メソッドを使った実装とのことです。

ちなみにサンプルプロジェクトを実行すると、この部分は次のように出力されます。

Classical random search for marked element in database.
  Database size: 8.
  Success probability:  0.125

Attempt 99. Success: Zero,  Probability: 0.12 Found database index One, One, Zero
Attempt 199. Success: Zero,  Probability: 0.11 Found database index Zero, Zero, One
Attempt 299. Success: Zero,  Probability: 0.103 Found database index One, Zero, Zero
Attempt 399. Success: One,  Probability: 0.102 Found database index One, One, One
Attempt 499. Success: Zero,  Probability: 0.108 Found database index One, One, Zero
Attempt 599. Success: One,  Probability: 0.108 Found database index One, One, One
Attempt 699. Success: Zero,  Probability: 0.11 Found database index One, Zero, Zero
Attempt 799. Success: Zero,  Probability: 0.112 Found database index Zero, Zero, One
Attempt 899. Success: Zero,  Probability: 0.119 Found database index One, Zero, One
Attempt 999. Success: Zero,  Probability: 0.119 Found database index Zero, One, Zero

3量子ビットからなるデータベースを検索するので確率は1/8となっています。

Q#で量子ビットを使って実装していますが、Classicalと表現されています。このあたりを見ていきましょう。C#から呼び出しているQ#のoperationはApplyQuantumSearchです。

Quantum/DatabaseSearch.qs at release/v0.3.1810 · Microsoft/Quantum · GitHub

やっていることはnDatabaseQubits + 1個のQubitを確保し、最初の一つをmarkedQubitに残りをdatabaseRegisterに割り当てて、QuantumSearch operationを呼び出し、Qubitの測定結果を返しているだけになります。というわけでQuantumSearch の実装を見てみます。

operation QuantumSearch (nIterations : Int, markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {
        
        StatePreparationOracle(markedQubit, databaseRegister);
        
        // Loop over Grover iterates.
        for (idx in 0 .. nIterations - 1) {
            ReflectMarked(markedQubit);
            ReflectStart(markedQubit, databaseRegister);
        }
    }

Quantum/DatabaseSearch.qs at release/v0.3.1810 · Microsoft/Quantum · GitHub

といっても、Random Database Search with Manual Oracle Definitionsの場合nIterationsが0なのでStatePreparationOracleを呼び出しているだけです。このfor文の中がGroverのアルゴリズムの確率振幅増幅にあたるのですが、ようはそれをしていないわけです。そして、StatePreparationOracleの実装にうつります。

operation StatePreparationOracle (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {
    
    body (...) {
        UniformSuperpositionOracle(databaseRegister);
        DatabaseOracle(markedQubit, databaseRegister);
    }
    
    adjoint invert;
}

Quantum/DatabaseSearch.qs at release/v0.3.1810 · Microsoft/Quantum · GitHub

bodyとadjoint invertというキーワードが出てきました。bodyはoperationの実装本体を記述するキーワードで、adjointやcontrolleredを指定しない場合はbodyを省略して直接実装本体を記述することができます。adjointはそのoperationがadjointであることを表明しており、invertというのはコンパイラーにadjointなoperationの生成方法を指示しています。このあたりは別途まとめて説明することにして、今日は実装の方の説明に集中します。

UniformSuperpositionOracleとDatabaseOracleの2つのオペレーションを呼び出しています。UniformSuperpositionOracleはその名前の通り、databaseRegisterというQubitの配列に対して、すべての状態が同じ確率で存在するような重ね合わせの状態 ${\frac{|00\dots00⟩ +|00\dots01⟩ +\dots +|11\dots10⟩ +|11\dots11⟩ }{\sqrt 2^ n}}$ を作成しています。

operation UniformSuperpositionOracle (databaseRegister : Qubit[]) : Unit {
    
    body (...) {
        let nQubits = Length(databaseRegister);
        
        for (idxQubit in 0 .. nQubits - 1) {
            H(databaseRegister[idxQubit]);
        }
    }
    
    adjoint invert;
}

そして、DatabaseOracleというオペレーションでオラクル関数を定義しています。 ${|11\dots11⟩}$ という状態のときのみmarkedQubitを反転させればいいので、Controlled Xというoperationを使っています。

operation DatabaseOracle (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {
    
    body (...) {
        Controlled X(databaseRegister, markedQubit);
    }
    
    adjoint invert;
}

Quantum/DatabaseSearch.qs at release/v0.3.1810 · Microsoft/Quantum · GitHub

このoperator（ここではX)にControlledを修飾して使う場合の説明についてはここに書いてあります。

Q# type model | Microsoft Docs

In Q#, controlled versions always take an array of control qubits, and the specified state is always for all of the control qubits to be in the computational (PauliZ) One state, ${|1⟩}$ .

Controlledで修飾すると第一引数に指定するQubitの配列がcontrolsビットとして使われます。すなわち、このQubitすべてが ${|1⟩}$ のときだけ、修飾されたoperatoを第二引数に作用させます。今やりたいのは、databaseRegisterが ${|11\dots11⟩}$ の場合のみmarkedQubitを1にしたいので、まさにうってつけの使い方になります*1。

ということで、ようやく確率振幅増幅に至るまでの手順がわかったので、次はいよいよ確率振幅増幅を扱ったQuantum Database Search with Manual Oracle Definitionsに入ります。

*1:むしろ、ここの記述を簡単にしたいので検索対象のインデックスを ${2^ n - 1}$ にしたと思われます

銀の光と碧い空

クラウドなインフラとC#なアプリ開発の狭間にいるエンジニアの日々

Q#のGrover の探索アルゴリズムのサンプルコードをのぞいてみる　その1