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制約を、各色について隣接ノード同士の値の積が０となるように制約を設定する。それに対して量子アニーリングを実行すれば良い。その結果、上記と同一の９個の解が得られたので、以下に掲載する。

参考資料

[1] 初級量子コンピューティングの旅の目的地Grover:

https://sparse-dense.blogspot.com/2022/08/grover.html

[2] IBM Quantum Challenge 2019:

https://github.com/quantum-challenge/2019/blob/master/problems/final/answer_and_comment_by_judges.ipynb

[3] Fixstars Amplify,

https://amplify.fixstars.com/ja/demo

ドイチュのアルゴリズムで量子計算のこころに触れる（続）

　前回の記事で、ドイチュの量子アルゴリズムを述べた。今回は、その拡張版であるドイチュ・ジョサのアルゴリズムを試した。

■ドイチュ・ジョサのアルゴリズム

　この場合も、値として0か１をとる２値関数f(x)が定数関数か平衡関数かを、ただ１回の関数の評価で判定できるという不思議なアルゴリズムである。今回は、変数xは、0,1,2, ... , 2ⁿ-1を取るように値域が拡大されている。この場合の定数関数とは、どのxに対してもf(x)の値は同一であり、平衡関数とは、半分のxに対してはf(x)=0であり、残り半分のxに対してはf(x)=1ということである。

　従来のコンピュータで平衡関数/定数関数を判定するには、f(x)を最大2^n-1+1回調べる必要があるが、ドイチュ・ジョサの量子アルゴリズムでは、ただ１回で済む、という素晴らしさがある。

■ドイチュ・ジョサのアルゴリズムの量子回路

　前回同様、渡邉靖志著[1]のドイチュ・ジョサのアルゴリズムとその量子回路の説明を参考にさせていただいた。この著書には、簡潔にその真髄が書かれている。図１に示す通り、特に難しい数式を含むわけではないが巧妙に組み立てられているので、じっくりと腰を据えて理解する必要がある。ここには詳細説明は書けないが、ともかく、この量子回路によって最終的に測定した結果、n個の0の列 "000...0" が観測される可能性が0%であれば、平衡関数であるということだ。

■IBM Quantum実機での実行

　理解を確認するため、n=3の場合の量子回路図を作り、それをIBM Quantum実機で動かしてみた。その際、Qiskitの解説[2]を参考にさせていただいた。図２に定数関数の場合の、図３に平衡関数の場合の判定結果をそれぞれ示した。いずれも納得できる結果だが、現状の実機ではノイズのために幾らかの誤差が生ずる。すなわち、理論的には観測されないはずのビット列も若干観測されたが、結果の判断に影響はない。

　なお、誤差のない理論通りの実行結果を得て、理解を進めたいのであれば、実機ではなくシミュレータを使えば良い。IBM Quantumの環境では、実機の場合と全く同じインタフェースでこのようなシミュレータを使うことができる。また、図４に示す通り、Qni量子シミュレータを使うのも良いだろう。

参考文献

[1] 渡邉靖志：入門講義　量子コンピュータ、講談社サイエンティフィック、2021年11月24日初版

[2] Open-Source Quantum Development Qiskit,

https://qiskit.org/textbook/ja/ch-states/introduction.html

ドイチュのアルゴリズムで量子計算のこころに触れる

【要旨】アルゴリズム、アルゴリズムとよく言いますが、コインの真偽判定に関するドイチュのアルゴリズムは、現在のPC上では考えられません。量子計算に特有の全く不思議なアルゴリズムですが、小生なりに理解した結果を、分かりやすく説明します。（なお、量子ビットの状態、重ね合わせ、もつれ、及び量子ゲートの基礎知識を前提としていますが、ご存じなくても、不思議さは感じていただけると思います。）

このアルゴリズムの拡張版であるドイチュ・ジョサのアルゴリズムについてはこちらに簡単な試行結果があります。

●コインの真偽判定の問題
　コインをトスして何かを決める場合がある。その際、コインが変造されていないかを検査したい。表裏が同一のデザインならば、それは偽物だ。表と裏をそれぞれ見るので、２回の検査を要する。これを２値（０, 1）関数f(x)の適用に置き換えてみる。変数xも0か1をとるとする。コインの最初の検査をf(0)、２回目の検査をf(1)とする。関数値0と1は、それぞれ、QueenエリザベスIIのデザインと裏地のデザインに対応する。そのような関数fとして、図１に示すように、 f1, f2, f3, f4の４種が考えられる。f1と f2は、平衡関数（裏表が異なる）と呼ばれ、f3, f4は定数関数（表裏が同一）と呼ばれる。

●ドイチュのアルゴリズム
　この問題を解く、ドイチュのアルゴリズム（1985年）は、ただ１回のコインの検査だけで済むという。そんなことできるのか？実に不思議だが、それを実現する量子回路が図２に示すものだ。詳細は後で述べるが、まずはそれがどんなものかを見てみよう。

　制御ビットと標的ビットという２つの量子ビットを用意し、それぞれ"|0>"と"|1>"に初期化する。それらにアダマールゲートHを通す。その状態にOracleと呼ばれる判定ゲート適用する。Oracleの中身は、図にあるように排他的論理和をとるだけの単純なものだが、Oracleに入ってくる状態①が、すでに量子特有の重ね合わせ状態となっていて、これが常識では考えにくい作用を起こす元になっている。
　それはともかく、Oracle適用後の制御ビットにさらにアダマールHを適用し、その結果を観測した結果が、"0"ならば定数関数（偽物）であり、"1"ならば平衡関数（本物）だという。繰り返しになるが、Oracleは１回しか通していない。だから、f(x)の計算も１回しかやっていない。それなのに、このような結論が得られるのだ！

●ドイチュのアルゴリズムの実行
　なぜこのアルゴリムでよいのかは後で述べるが、その前に、この回路をQni量子シミュレータで実行して結果を確認する。IBM Quantumの実機でも簡単に実行できるのだが、待ち時間が長すぎるので、今回は保留した。

　図２では、対象の関数として一般的にf(x)としたが、実際には具体的な関数に対応した量子回路をOracleとして設定する必要がある。図３に、上で述べた４種類の関数ごとのOracleを示した。各関数がなぜ、それぞれ図のようなOracle（量子ゲートで構成）になるのかは、青色の数式で示してある。例えば、関数f1は、制御NOTゲート（CNOT）だけでOracleを構成できる。

　それぞれの関数ごとに、図２に示した量子回路の実行結果（最終的な観測結果）は、上で述べたように、平衡関数（本物）、定数関数（偽物）を正しく識別したことが確認できた！

●ドイチュのアルゴリズムの証明
　ここからは、このアルゴリズムが思い通りに働くことを理論的に示す。ここで用いた計算は、渡邉靖志著[1]に従っているが、途中の計算過程もできるだけ省略せずに、独自の説明も加えた。その前に必要となる種々の量子ゲートの働きについては、こちらのブログ記事も参照されたい。また、アダマールゲートHについては、小生自作の図４のブロッホ球の模型もイメージするのに役立つだろう。

　では、図２の量子回路に戻り、アダマールゲート適用後の状態①がどうなるかを、以下の計算で示す。（ケットベクトルや直積の記号が頻出して入力しにくいので、万年筆で手書きした。クリックして拡大してご覧ください。）

　次に、Oracleを通過後の状態②の計算を示す。そして、この状態での制御ビットに再度アダマールゲートHを適用し、それを観測して、関数の均衡、定数を判定できることを明らかにしている。

これで完結した！

●IBM Quantum実機でも実行
　量子コンピュータ実機（IBM Quantum - ibm_nairobi)による結果も得られたので記録しておく。下図は、図３の関数f1に対するものであり、観測結果は93.5%(=958/1024)の確率で、"1"、すなわち、平衡関数だという正しい結果となった。

●感想など

　ここまでで計算上、ドイチュのアルゴリズムを理解できたことになる。しかし、実感としては、いまだに不思議さは拭い去れない。そこでは、量子ビットの重ね合わせ状態が巧みに使われていて、f(0)とf(1)が同時に計算されていることになる。これは、従来の並列処理を想起させるかも知れないが、その仕組みは本質的に異なる。量子コンピューティングのこころに触れることができるアルゴリズムなのである。

謝辞

　この記事を書くに当たって、以下の参考文献を大いに利用させていただいた。[1]からは、量子コンピューティング全般の基本を、理論と例題を通して学ぶことができた。また[2]からは、Qni量子シミュレータを活用したアルゴリズムの実装について学んだ。これらの著者に感謝申し上げたい。

参考文献

[1] 渡邉靖志：入門講義　量子コンピュータ、講談社サイエンティフィック、2021年11月24日初版

[2] 中山茂：量子アプリQni - 量子プログラミング初歩、Gaia教育シリーズ52、2022年8月8日初版