sparse-dense by FoYo: Groverの探索（量子アルゴリズム）でコンビニ出店案

【要旨】Groverの探索は、典型的な量子アルゴリズムの一つである。これは、可能性のある全ての探索問合せを量子重ね合わせの原理で一度に行い、量子状態の確率振幅を波の干渉のように増幅/減衰させる。この繰り返しによって、解を浮き上がらせ、確定させる。そのような驚異のアルゴリズムである。その概要は、すでに本ブログ記事[1]でも述べた。ここでは、IBM Quantum Challenge 2019[2]で出題された課題「コンビニ出店案作成」に対するGrover探索による解答例を追試行し、その威力と魅力を確認した。

[量子アニーリングによる結果も、末尾に追加した。]

●Grover探索アルゴリズムの概要

　すでに、別の記事[1]で述べたので、ここでは極く簡単に復習する。簡単な例として、00、01、10、11を入力とする関数fがあり、fはある一つの入力に対してのみ１であり、その他の入力に対しては0を出力する。関数値f(xx)=1となる入力xxを求める問題である。古典的探索では、最悪の場合、関数fの評価を３回行う必要があるが、Groverによれば、それは１回で済む。図１はこのアルゴリズムを実現する量子回路とその説明である。

　まず、Oracleと呼ばれる量子回路を作る。それは、４個の全ての入力を纏めた量子重ね合わせを受け取り、f(xx)=1となる|xx⟩の確率振幅の符号を反転させる。その際、解xxに応じたOracleを構成するのである。だが、これは解をすでに与えているわけではなく、課題そのものの記述に相当する。Oracleの中で、関数fは１回評価される。

　次に、Grover反復と呼ばれる確率振幅の増幅/減衰により、解を他から分離することができるのである。すなわち、解を与える入力のみが多数回測定されるように作られている。そこが核心部分である。この例では反復１回で明確に解が得られた。一般には、入力サイズNに対して、√N回のオーダーの反復で解が得られることが知られている。

●課題：コンビニ出店案の作成

　少し現実的な「コンビニ出店案の作成」にGrover探索を適用する。これは、IBMのQuantum Challenge 2019での出題[2]を若干変更したものである。図２にその仕様を示した。合計11地区に４社のいずれかのコンビニを一つだけ出店する案を全て列挙せよという問題である。

　これはグラフの彩色問題の一つであり、各辺の両端のノードの色が同色になることを禁止することに相当する。すでにA社、B社、C社、D社が図１のようにそれぞれ１店を出店済みなので、残り７地区にどのように出店させるかである。

　これを解くには、全ての条件を満たす場合に最小になるようなエネルギー関数を設定した量子アニーリング法が適しているかも知れない。また、数理計画による解法もあるだろう。しかし、ここでは、Grover探索を用いて、量子アルゴリズムの威力、魅力を確認したい。

●「コンビニ出店案」をGrover探索で解く

　この解法は、最初に挙げた00、01、10、11を入力とする探索と基本的に同じ仕組みである。だが、解がいくつ存在するかわからないので、それに対応するOracleの作成に工夫が必要である。具体的な実装方法とプログラムは参考資料[2]を利用させていただいた。解の候補として考えるべき、７量子による入力は16,384（4の7乗）とおりである。Oracleが構成した後は、上に述べたGrover反復を行えばよい。図３に、Qiskitを用いた量子シミュレーション結果を示した。

　この量子シミュレーションでは同じことを500回（500 shots）行ない、その測定値の統計を示してある。図3(a)は、Grover反復１回の状態である。ほとんどの入力は１回だけ測定され、いくつかの入力に対しては２回〜７回程度測定された。さらに反復を続けると、解を与える入力の測定回数が順次増加し、解でないものの出現が減少する。

　Grover反復を７回実行した結果が図4(b)である。出現頻度が40〜50と際立つものが９個観測された。それが解だと判定される。実に見事な解法ではないか！

（なお、(a)よりも(b)での縦棒の幅が太くなっているのは、出現回数0回の入力が激増したため、図からそれらが取り除かれたためである。）

●得られた解を確認する

　以上の結果を図４の通り確認した。（解が９個しかないことは証明されていないが）恐らくこれが全ての解であろう。確かに、どの解においても、辺の両端のノードは異なる彩色となっており、全ての条件を満たしている。

●感想

　驚嘆すべき量子アルゴリズムの一つであるGrover探索を、ある程度現実的な問題にも適用できることが分かった。IBM Quantum Challengeでは、現実的な課題を順次増やして量子コンピューティングコミュニティを活性化させようとしている。いずれ、そこで出題される課題にも挑戦してみたい。また、冒頭に述べたように、この課題は、量子アニーリングの利用にも適していると思われるので、そちらも試す価値はあるだろう。

[追加]2022-12-22

　その後、量子アニーリングによる解法もやってみた。参考資料[3]のデモアプリ（グラフ彩色）を参考にした。縦軸にノード番号、横軸に色番号のマス目を作り、そこに０（該当せず）か１（該当する）が入るようにする。初期設定済み（出店済み）に対応するマス目は１とする。各行についてone-hot制約を、各色について隣接ノード同士の値の積が０となるように制約を設定する。それに対して量子アニーリングを実行すれば良い。その結果、上記と同一の９個の解が得られたので、以下に掲載する。