ひとりAdvent Calendar 24日目です。
その1、その2に引き続き、Grover の探索アルゴリズムを見てみます。
https://tech.tanaka733.net/entry/2018/12/Grover%27s-search-algorithm-in-qsharp-sample-2tech.tanaka733.net
今回はMultiple Element Quantum Database Search with the Canonで、検索対象が複数、かつ実装する際にQ#のライブラリが提供しているAPIを利用しています。
ApplyGroverSearchというのがC#から呼ばれるQ#側のコードで、今までの2つはマークするQubitの位置が固定されていましたが、今回は引数で渡せるようになっています。nDatabaseQubitsで指定した数のQubitがデータベースにあるので、2n通りの状態があり、マークする状態のインデックスが配列の要素となっています。
QArray<long> markedElements = new QArray<long>() { 0, 39, 101, 234 };
ApplyGroverSearchoperationの実装はこうなっています。
operation ApplyGroverSearch (markedElements : Int[], nIterations : Int, nDatabaseQubits : Int) : (Result, Int) {
mutable resultSuccess = Zero;
mutable numberElement = 0;
using (qubits = Qubit[nDatabaseQubits + 1]) {
let markedQubit = qubits[0];
let databaseRegister = qubits[1 .. nDatabaseQubits];
(GroverSearch(markedElements, nIterations, 0))(qubits);
set resultSuccess = M(markedQubit);
let resultElement = MultiM(databaseRegister);
set numberElement = PositiveIntFromResultArr(resultElement);
ResetAll(qubits);
}
// Returns the measurement results of the algorithm.
return (resultSuccess, numberElement);
}
Quantum/DatabaseSearch.qs at release/v0.3.1810 · Microsoft/Quantum · GitHub
markedQubitとdatabaseRegister用のQubitを用意して、アルゴリズムの実装であるGroverSearchを実行し、測定しています。databaseRegisterの状態をインデックス値で取得するためMultiMで複数Qubitの測定を行い、PositiveIntFromResultArrでその測定結果からインデックスの値を取得しています。
MultiM operation (Microsoft.Quantum.Canon) | Microsoft Docs
PositiveIntFromResultArr function (Microsoft.Quantum.Canon) | Microsoft Docs
usingを抜ける直前のResetAllはすべてのQubitの状態を|0>に戻す便利operationです。Q#ではusingを抜ける際に、Qubitの状態を|0>に戻す必要があるのですが、今まで2回のサンプルのようにわざわざ測定してから操作せずとも、この便利メソッドを実行しておけば問題ありません。1Qubitの場合はResetoperationが使えます。
ResetAll operation (Microsoft.Quantum.Primitive) | Microsoft Docs
GroverSearchoperationは引数にQubit[]をとって、そのQubit配列を操作するoperationを返します。そのoperationを生成はAmpAmpByOracleというQ#のライブラリを呼び出しています。
function GroverSearch (markedElements : Int[], nIterations : Int, idxMarkedQubit : Int) : (Qubit[] => Unit : Adjoint, Controlled) {
return AmpAmpByOracle(nIterations, GroverStatePrepOracle(markedElements), idxMarkedQubit);
}
AmpAmpByOracleはStandard Amplitude Amplification algorithmとある通り、振幅増幅を行うためのAPIです。第1引数で指定した回数だけ、第2引数のStateOracleを振幅増幅します。第3引数は第2引数のStateOracleのflag QubitとなるQubitのインデックスを指定します。
AmpAmpByOracle function (Microsoft.Quantum.Canon) | Microsoft Docs
StateOracleは定義済みの型でここに説明があります。初期状態からある振幅（ドキュメント上ではλ）でターゲット状態|Ψs>を生成するOracleを定義します。役目としてはその1で説明したStatePreparationOracleとまさに同じ役割をしています。違いは、StatePreparationOracleではマークされたQubitそのものを渡していましたが、StateOracleではQubitの状態を表すインデックスを渡しています。というわけで、あとの実装はその時の実装と比べながらみるとわかりやすいかと思います。
StateOracle user defined type (Microsoft.Quantum.Canon) | Microsoft Docs
GroverStatePrepOracleは次のような実装です。StateOracleを生成するためにGroverStatePrepOracleImplを呼び出した結果を渡しています。
function GroverStatePrepOracle (markedElements : Int[]) : StateOracle {
return StateOracle(GroverStatePrepOracleImpl(markedElements, _, _));
}
StateOracleは(Int, Qubit[]) => Unitというシグネチャーを持つので、2つの_は部分適用の際にそれぞれIntとQubit[]となります。GroverStatePrepOracleImplは次のような実装です。
operation GroverStatePrepOracleImpl (markedElements : Int[], idxMarkedQubit : Int, startQubits : Qubit[]) : Unit {
body (...) {
let flagQubit = startQubits[idxMarkedQubit];
let databaseRegister = Exclude([idxMarkedQubit], startQubits);
ApplyToEachCA(H, databaseRegister);
DatabaseOracleFromInts(markedElements, flagQubit, databaseRegister);
}
adjoint invert;
controlled distribute;
controlled adjoint distribute;
}
Excludeは第2引数の配列から第1引数で指定したインデックスを除外した部分配列を返します。Exclude([1],[0,1,2]) = [0,2]となります。
Exclude function (Microsoft.Quantum.Canon) | Microsoft Docs
インデックス用にマークされたQubit以外にHadamardゲートを適用しています。ここは、その1のStatePreparationOracleの中のUniformSuperpositionOracleに相当しています。次にDatabaseOracleに相当するDatabaseOracleFromIntsを適用します。
operation DatabaseOracleFromInts (markedElements : Int[], markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {
body (...) {
let nMarked = Length(markedElements);
for (idxMarked in 0 .. nMarked - 1) {
(ControlledOnInt(markedElements[idxMarked], ApplyToEachCA(X, _)))(databaseRegister, [markedQubit]);
}
}
adjoint invert;
controlled distribute;
controlled adjoint distribute;
}
ここでは、ターゲットとなる状態をインデックス値で持っているため、ControlledOnIntを使っています。
ControlledOnInt function (Microsoft.Quantum.Canon) | Microsoft Docs
その1、その2と比べると、探索要素が複数かつ任意（C#コードから引数として指定できる）ようになっているのに実装は簡単になっています。このようにQ#では単純なゲートばかりでなく、かなり便利なoperationも用意されています。 というわけで、Grover の探索アルゴリズムのかけあしですが見てみました。
