ひとり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 = 2n and for n a positive integer. Note that n is the number of qubits needed to encode the database element index k.
つまり、n量子ビットからなるデータベースが与えられたとき、というインデックスで示される状態
を探します。
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の配列に対して、すべての状態が同じ確率で存在するような重ね合わせの状態を作成しています。
operation UniformSuperpositionOracle (databaseRegister : Qubit[]) : Unit { body (...) { let nQubits = Length(databaseRegister); for (idxQubit in 0 .. nQubits - 1) { H(databaseRegister[idxQubit]); } } adjoint invert; }
そして、DatabaseOracle
というオペレーションでオラクル関数を定義しています。という状態のときのみ
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,
.
Controlled
で修飾すると第一引数に指定するQubitの配列がcontrolsビットとして使われます。すなわち、このQubitすべてが のときだけ、修飾されたoperatoを第二引数に作用させます。今やりたいのは、
databaseRegister
がの場合のみ
markedQubit
を1にしたいので、まさにうってつけの使い方になります*1。
ということで、ようやく確率振幅増幅に至るまでの手順がわかったので、次はいよいよ確率振幅増幅を扱ったQuantum Database Search with Manual Oracle Definitions
に入ります。
*1:むしろ、ここの記述を簡単にしたいので検索対象のインデックスをにしたと思われます