ひとりAdvent Calendar 23日目です。
その1に引き続き、Grover の探索アルゴリズムを見てみます。
今日はQuantum Database Search with Manual Oracle Definitionsでこれは前回の実装に確率振幅増幅が追加されているものでした。
前回は確率振幅増幅を行わないコードになっていました。nIterationsだけ増幅を行うコードはここです。
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
ReflectMarkedとReflectStartを実行しています。これは確率振幅増幅で、欲しい解の確率振幅を反転させることと平均値の周りで逆転させることに相当しています。まずはReflectMarkedを見てみます。
operation ReflectMarked (markedQubit : Qubit) : Unit {
// Marked elements always have the marked qubit in the state |1〉.
R1(PI(), markedQubit);
}
R1は第2引数で指定したQubitを|1>のまわりに第1引数で指定した角度だけ回転させるoperationです。
R1 operation (Microsoft.Quantum.Primitive) | Microsoft Docs
PI()は定数が返ってくるfunctionで、数学関連のfunctionはこれ以外にもMicrosoft.Quantum.Extensions.Mathに定義されています。三角関数、対数・指数関数などそろっているので、必要になった場合は用意されていないか確認するのがいいでしょう。
Microsoft.Quantum.Extensions.Math | Microsoft Docs
次にReflectStartを見てみます。
operation ReflectStart (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {
Adjoint StatePreparationOracle(markedQubit, databaseRegister);
ReflectZero([markedQubit] + databaseRegister);
StatePreparationOracle(markedQubit, databaseRegister);
}
ここの処理は別のサイトの説明から引用してみます。
Grover の検索アルゴリズムとQuantum Amplitude Amplification/Estimation - 物理とか
初期状態に対する反転は次のように記述できるとあります。
初期状態を作り出すユニタリーの複素共役転置、[tex:{S 0}]、初期状態を作り出すユニタリーの順に適用するばよいことがわかります。ここで、[tex:{S 0}]は|0>のだけの符号を反転するようなユニタリーです。
StatePreparationOracleが前回も出てきました。初期状態を生成するためのユニタリーです。ユニタリーの複素共役転置はQ#ではAdjoint修飾子で記述できます。これは前回出てきたControlleredと似たような使われ方になります。
Q# type model | Microsoft Docs
ReflectZeroが、|0>だけの符号を反転するようなユニタリーです。引数が[markedQubit] + databaseRegisterとなっています。databaseRegisterはもともとQubitの配列で[markedQubit]も配列を生成しているので、配列の足し算となります。Q#では配列の足し算はC#のLINQのConcatのように足された配列の後ろの要素から足す配列が追加された、一つの配列を生成します。例えば、[1]+[2,3,4]=[1,2,3,4]となります。
|0>だけの符号を反転するoperationの実装は次のように記述できます。
operation ReflectZero (databaseRegister : Qubit[]) : Unit {
let nQubits = Length(databaseRegister);
for (idxQubit in 0 .. nQubits - 1) {
X(databaseRegister[idxQubit]);
}
Controlled Z(databaseRegister[1 .. nQubits - 1], databaseRegister[0]);
for (idxQubit in 0 .. nQubits - 1) {
X(databaseRegister[idxQubit]);
}
}
Controlledを使うために、まず全Qubitを反転させています。|0>が|1>になっているので、そのQubitを制御ビットとしてControlled Zを適用します。最後に元に戻すために再度全Qubitを反転させています。これで振幅増幅の説明まで終わりました。次回はその3として、Qunatum Development Kitが提供しているより高レイヤのAPIを使った実装例を見てみます。
