Grover's Search Algorithm(グローバーの検索アルゴリズム)解説
グローバーのアルゴリズムについて
グローバーの検索アルゴリズムは量子コンピューティングのアルゴリズムで最も有名なアルゴリズムの一つです。
グローバーのアルゴリズムはデータベース検索アルゴリズムと知られています。
グローバーの論文の中の例を要約すると
完全にランダムに並べられたN個の名前を含む電話帳の中から特定の名前を50%の確率で見つけ出すには、古典コンピュータを使うと\(frac{N}{2}\)の名前を見る必要があります。量子コンピュータでは重ね合わせの状態を使うことにより複数の名前を同時に調べることができます。
しかし、より正確にはグローバーのアルゴリズムは逆関数の生成と考えた方がよいでしょう。
このアルゴリズムはinverting a function(関数の逆算)と言った方がよいでしょう。
つまり関数\(y=f(x)\)に対して、ある\(y\)を導出する\(x\)を求めるのに利用することができます。
このチュートリアルの目的
このチュートリアルではグローバーのアルゴリズムの実践的使用法でより一般的な問題(SAT問題)をQ#を使って解いていきます。このチュートリアルではグローバーのアルゴリズムの実装などは取り扱いません。
Part I. Problem Statement (問題定義)
SAT問題・充足可能性問題とは
充足可能性問題とは、入力xをN個のboolean変数\((x_0, x_1, ..., x_{N-1})\)とし、0 が(false)で1が(true)の場合、この複数ビットの入力\(x\)に対して論理和論理積であらわされる関数\(f(x)\)の出力をTrue(1)にする\(x\)の組み合わせが存在するかを確認する問題です。
例えば、\(f(x_0, x_1) = x_0 \wedge (\neg x_0 \vee \neg x_1)\)に関して、\(\wedge\)はAND(論理積)、\(\vee\)をOR(論理和)、\(\neg\)をNOT(論理否定)とした場合、この式を満たす\(x_0, x_1\)の値は\(x_0=1, x_1=0\)になります。一方で\(f(x_0) = x_0 \wedge \neg x_0\)を考えた場合、この式を満たす\(x_0\)は存在しません。
このQ#を使ったチュートリアルではSAT問題を2次元の配列であらわします。
1次元目の配列要素のインデックス\(i\)は\(i\)番目の要素\(x_i\)を示し、各要素は(Int, Bool)のタプル形式で表現されます。Intは0, 1の値をとり、Boolはx_iがNOT(論理否定)かそうでないかを表現します。
\(f(x_0, x_1) = x_0 \wedge (\neg x_0 \vee \neg x_1)\)の例では[[(0, true)], [(0, false), (1, false)]]と表され、[]間をつなぐ","はANDで、[]内の()をつなぐ","はORになります。
Part II. Grover's Search Algorithm(グローバーの検索アルゴリズムを使ってみる)
複数ビットの入力に対してシングルビットを返す量子オラクル\(f(x)\)を想定します。入力ビット\(|x\rangle\)に加えて結果を表示するビット\(|y\rangle\)も考慮し、下記のような量子ゲートを想定します。\(U_f |\vec{x} \rangle |y\rangle = |\vec{x} \rangle |y \oplus f(x) \rangle\)
Groverの検索アルゴリズムをざっくりと説明すると
1) 量子システムを既知の初期状態にする
2) "Grover iteration"と呼ばれる手順を複数回実行する。各操作ではblack boxの量子オラクルが1回だけ呼ばれる。
3) 量子ビットを観測すると、高い確率で期待した答えを入手することができる。
です。
Exercise 2: Run Grover's algorithm to solve a SAT problem
実際にグローバーのアルゴリズムを使ってSATプログラムを解いてみます。まずはプログラムに記載されている問題\(f(x_0, x_1) = x_0 \wedge (\neg x_0 \vee \neg x_1)\)をそのまま動かしてみると\(x_0 = True, x_1 = False\)で正しい答えが出てきます。(場合によっては出てこないこともある?)
\(f(x)\)の値が1であれば解を満たす\(x_i\)の値が存在すること、0であれば解を満たす\(x_i\)の値が存在しないこととなります。次に問題を\(f(x) = x_0 \wedge \neg x_0\)に置き換えて実行してみます。問題を置き換えるのは下記のようにproblemとvariableCountの2行だけ入れ替えればよいです。
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Measurement;
open Quantum.Kata.ExploringGroversAlgorithm;
operation RunGroversAlgorithm_SimpleLoop () : Unit {
let problem = [[(0, true)], [(0, false)]];
let variableCount = 1;
Message($"Solving SAT problem {SATInstanceAsString(problem)}...");
let oracle = CreateOracleForSATInstance(problem);
let iterationCount = 1;
using (register = Qubit[variableCount]) {
GroversAlgorithm_Loop(register, oracle, iterationCount);
let assignment = ResultArrayAsBoolArray(MultiM(register));
Message($"{VariableAssignmentAsString(assignment)}");
ResetAll(register);
}
}この問題は解がないので答えが出るはずがないのですが...
Solving SAT problem (x0) ∧ (¬x0)... x0 = True ()なんか出てきましたが、これがどういう意味なのか実行結果を\(y\)を使って観測する必要があります。
Part III. Verifying the algorithm output (結果の観測)
\(|y\rangle\)を用意することで、\(U_f |\vec{x} \rangle |y\rangle = |\vec{x} \rangle |y \oplus f(x) \rangle\)となります。ここでであることを考慮すると
観測ビット\(|y\rangle\)を\(|0\rangle\)としてやることで、\(U_f |\vec{x} \rangle |0\rangle = |\vec{x} \rangle |f(x) \rangle\)となり\(f(x)\)の値をそのまま観測することができるようになります。
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Measurement;
open Quantum.Kata.ExploringGroversAlgorithm;
operation RunGroversAlgorithm_OutputVerification () : Unit {
// Use a different SAT instance to get a higher probability of failure
let problem = [[(0, true), (1, true)], [(0, false), (1, false)]];
let variableCount = 2;
Message($"Solving SAT problem {SATInstanceAsString(problem)}...");
let oracle = CreateOracleForSATInstance(problem);
let iterationCount = 1;
using (register = Qubit[variableCount]) {
GroversAlgorithm_Loop(register, oracle, iterationCount);
let assignment = ResultArrayAsBoolArray(MultiM(register));
Message($"{VariableAssignmentAsString(assignment)}");
// ========================== Check that the answer is correct. ==========================
// Allocate another qubit to keep the result of evaluating the function.
// You can allocate a single qubit with the following syntax in using statement: <variable name> = Qubit()
using (result = Qubit()) {
// After measuring "register" on line 17, the qubits in "register" end up
// in the state that encodes the answer produced by the algorithm (decoded in "assignment" variable).
// Call oracle with "register" as the first parameter (function input x)
// and the newly allocated qubit as the second parameter (function output f(x))
// to evaluate the function on that answer.
oracle(register, result);
// Measure the newly allocated qubit and check if the measurement result is Zero or One;
// One means the algorithm returned correct answer, Zero - incorrect.
// You can measure the qubit and reset it immediately using MResetZ operation,
// and compare the measurement result to the constants Zero or One using "==" operator.
if (M(result) == One) {
// Report the correct/incorrect result using Message function.
Message("Correct");
} else {
Message("Incorrect");
}
Reset(result);
}
ResetAll(register);
}
}今回取り扱っている問題は\(f(x_0, x_1) = (x_0 \vee x_1) \wedge (\neg x_0 \vee \neg x_1)\)なので正しい解\(x_0 = True, x_1 = False\)等が存在しますので"Correct"が表示されるべきですが、表示されましたでしょうか？どうも表示されない場合があるようです。
Exercise 4: Re-run Grover's algorithm in case of incorrect answer
正しい結果が得られなかった人もいると思いますし、正しい結果が得られた人もいると思います。今度は同じプログラムをループを使って正しい結果が出るまで流してみましょう。
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Measurement;
open Quantum.Kata.ExploringGroversAlgorithm;
operation RunGroversAlgorithm_RerunIncorrectAnswer () : Unit {
// Use a different SAT instance to get a higher probability of failure
let problem = [[(0, true), (1, true)], [(0, false), (1, false)]];
let variableCount = 2;
Message($"Solving SAT problem {SATInstanceAsString(problem)}...");
let oracle = CreateOracleForSATInstance(problem);
let iterationCount = 1;
using (register = Qubit[variableCount]) {
// ======== Use repeat-until-success loop to re-run algorithm in case of a failure ========
// Define a mutable variable to serve as the exit condition.
mutable isAnswerCorrect = false;
// Define a mutable variable to store the answer once you've found a correct one.
mutable finalAnswer = [false, false];
repeat {
GroversAlgorithm_Loop(register, oracle, iterationCount);
let assignment = ResultArrayAsBoolArray(MultiM(register));
Message($"{VariableAssignmentAsString(assignment)}");
using (result = Qubit()) {
oracle(register, result);
if (M(result) == One) {
Message("Correct");
set isAnswerCorrect = true;
} else {
Message("Incorrect");
}
Reset(result);
}
ResetAll(register);
} until (isAnswerCorrect);
// Output the final answer.
Message($"{finalAnswer}");
}
}Part IV. Exploring the success probability of the algorithm (正しい結果が得られる確率について)
ここまでいろんなパターンを流して来たら、正しい結果が観測できる確率が異なることに気づいたと思います。正しい結果が得られる確率は様々な要素によって影響されます。
- 検索スーペースのサイズ(変数の数や問題の式)
- 式を満たす解の種類の数
- グローバーのアルゴリズムを実行する回数
ここでは実際にいろいろな問題に対してグローバーのアルゴリズムを動作させて、実際に正しい結果が観測できる確率を測定してみましょう。
コードの中のコメントに複数の問題が記載されているので、問題を入れ替えていろいろ動かしてみましょう。
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Measurement;
open Quantum.Kata.ExploringGroversAlgorithm;
operation RunGroversAlgorithm_CalculateSuccessProbability () : Unit {
// Here are the SAT instances with different success probabilities mentioned earlier to get you started
// 1 solution: [[(0, true)], [(0, false), (1, false)], [(1, true), (2, true)]]
// 2 solutions: [[(0, true), (1, true)], [(0, false), (1, false)], [(1, true), (2, true)], [(1, false), (2, false)]]
// 3 solutions: [[(1, false)], [(0, true), (2, true)]]
// 4 solutions: [[(0, true), (1, true)], [(0, false), (1, false)]]
let variableCount = 3;
let problem = [[(1, false)], [(0, true), (2, true)]];
Message($"Solving SAT problem {SATInstanceAsString(problem)}...");
let oracle = CreateOracleForSATInstance(problem);
let iterationCount = 1;
using (register = Qubit[variableCount]) {
// Define a mutable variable to store the number of times the algorithm succeeded.
mutable successCount = 0;
for (i in 1 .. 100) {
// Loop body: run Grover's search using "GroversAlgorithm_Loop",
// measure the answer and check whether it is correct.
// Use "set successCount += 1;" to increment the success counter.
GroversAlgorithm_Loop(register, oracle, iterationCount);
let assignment = ResultArrayAsBoolArray(MultiM(register));
Message($"{VariableAssignmentAsString(assignment)}");
// Check that the answer is correct.
using (result = Qubit()) {
oracle(register, result);
if (M(result) == One) {
Message("Correct");
set successCount += 1;
} else {
Message("Incorrect");
}
Reset(result);
}
// Remember to reset the qubits in "register" at the end of each iteration!
ResetAll(register);
}
// Output the success probability of the algorithm.
Message($"The algorithm succeeds with {successCount}% probability.");
}
}下記のように記載すれば一度にすべてのプログラムを流すことができます。
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Measurement;
open Quantum.Kata.ExploringGroversAlgorithm;
operation RunGroversAlgorithm_CalculateSuccessProbability () : Unit {
// Here are the SAT instances with different success probabilities mentioned earlier to get you started
// 1 solution: [[(0, true)], [(0, false), (1, false)], [(1, true), (2, true)]]
// 2 solutions: [[(0, true), (1, true)], [(0, false), (1, false)], [(1, true), (2, true)], [(1, false), (2, false)]]
// 3 solutions: [[(1, false)], [(0, true), (2, true)]]
// 4 solutions: [[(0, true), (1, true)], [(0, false), (1, false)]]
let problems = [[[(0, true)], [(0, false), (1, false)], [(1, true), (2, true)]],
[[(0, true), (1, true)], [(0, false), (1, false)], [(1, true), (2, true)], [(1, false), (2, false)]],
[[(1, false)], [(0, true), (2, true)]],
[[(0, true), (1, true)], [(0, false), (1, false)]]
];
let variableCounts = [3, 3, 3, 2];
mutable variableIndex = 0;
for (problem in problems) {
let variableCount = variableCounts[variableIndex];
set variableIndex +=1;
Message($"Solving SAT problem {SATInstanceAsString(problem)}...");
let oracle = CreateOracleForSATInstance(problem);
let iterationCount = 1;
using (register = Qubit[variableCount]) {
// Define a mutable variable to store the number of times the algorithm succeeded.
mutable successCount = 0;
for (i in 1 .. 100) {
// Loop body: run Grover's search using "GroversAlgorithm_Loop",
// measure the answer and check whether it is correct.
// Use "set successCount += 1;" to increment the success counter.
GroversAlgorithm_Loop(register, oracle, iterationCount);
let assignment = ResultArrayAsBoolArray(MultiM(register));
//Message($"{VariableAssignmentAsString(assignment)}");
// Check that the answer is correct.
using (result = Qubit()) {
oracle(register, result);
if (M(result) == One) {
set successCount += 1;
}
if (i % 10 == 0) {
Message($"counter i={i} successCount={successCount}");
}
Reset(result);
}
// Remember to reset the qubits in "register" at the end of each iteration!
ResetAll(register);
}
// Output the success probability of the algorithm.
Message($"The algorithm succeeds with {successCount}% probability.");
}
}
}Demo: Exploring the success probability of Grover's algorithm
正しい結果が得られる確率について実験するデモはこちらです。以上でチュートリアルは終わりです。次はKatasにある問題に取り組んでいきたいと思います。
