量子コンピュータ(アニーリング型)の限界を計算複雑性理論で明らかにしてみた
量子コンピュータ(アニーリング型)は巡回セールスマン問題より難しい問題は解けません。そこが量子コンピュータ(アニーリング型)の限界です。
因みに、巡回セールスマン問題とは、都市の集合と都市間の距離から、全ての都市を一度ずつ巡る経路の最短を求める問題のことです。
この記事では、どうやってそのような結論に至ったかを説明します。
量子コンピュータ(アニーリング型)とは
量子コンピュータ(アニーリング型)は、量子アニーリングという量子ゆらぎを利用し最適化問題を解く手法を実現したコンピュータのことです。
量子アニーリングで解ける最適化問題はQuadratic unconstrained binary optimization(以下、QUBOと書きます)と呼ばれる、変数が0または1をとる二次式の最小値を求める問題です。
もう少し詳しくQUBOについて説明します。QUBOの扱う二次式は以下のように書くことができます。ここで、$${Q_{ij}}$$は有理数の係数とし、$${x_i}$$, $${x_j}$$は変数で0または1を取ります。
変数$${x_i}$$,$${x_j}$$の値を変えることで上の二次式は様々な値を取りますが、QUBOはその中で最小のものを求める問題です。例えば、下記二次式の最小値を求める問題はQUBOです。
答えは、-1となり、$${x_1=1}$$, $${x_2=0}$$のときの値となります。
量子コンピュータ(アニーリング型)は、D-Wave Systems, Inc.により世界初の商用のものが発表されました。それ以降も、企業や学術界は新たな量子コンピュータ(アニーリング型)を開発し、そして研究者たちは色々な世の中の問題をQUBOに変換して解こうとしています。
量子アニーリングの理論や応用の現状についての概要は、量子アニーリングの理論を提案された西森氏の以下のページを御覧ください。
この記事では以下に量子コンピュータ(アニーリング型)のことを、量子コンと書きます。
計算複雑性理論とは
問題の難しさを扱うコンピュータサイエンスの研究テーマです。計算複雑性理論では、いろんな問題がどの程度難しいかを明らかにします。ここで言う問題とは、数式を与えてその解を求めるようなものを指します。上で現れたQUBOも、この問題のひとつです。
問題の難しさを明らかにすることの嬉しさは何でしょうか？ひとつの嬉しさは、ある問題の難しさを明らかにすることで、どの問題がその問題に変換できるか、またどの問題がその問題に変換できないかがわかることです。そして、変換先の問題を効率的に解く方法がある場合、それが利用できるかどうかがわかります。
どうやって計算複雑性理論を用いて量子コンピュータ(アニーリング型)の限界を明らかにするか
QUBOの難しさを明らかにすることで、どの問題がQUBOに変換できるか、そしてどの問題が変換できないかがわかります。したがって、QUBOを解く量子コンがどの問題が解けるか解けないかを明らかにできます。量子コンで解けない問題がわかったとき、量子コンの限界を明らかにしたと言って良いと思います。
QUBOの難しさ
QUBOは、論理式の充足可能性を判定する問題(以下、SATと書きます)を解く事ができる計算機を多くても多項式回実行することで解くことができます。多項式回と書いていますが、QUBOの二次式の大きさと比例する回数で、それほど多くはないです。すなわちQUBOはそれくらいの難しさということです。他にも、巡回セールスマン問題も、SATを解く計算機を多くても多項式回実行することで解くことができます。
因みに、巡回セールスマン問題はQUBOに変換可能であり、その逆も可能です。このことは、QUBOは巡回セールスマン問題と同程度の難しさということを意味します。
QUBOの難しさからわかること
SATを解く計算機を多項式回実行するだけでは解けない問題(QUBOよりも難しい問題)は、QUBOに変換することができません。すなわち、そのような問題は量子コンでは解けません。量子コンでは解けない問題の例として、2種の限量子(∃∀)がついた論理式の充足可能性判定(以下、2QBFと書きます)などがあります。
2QBFが扱う論理式は下のように一般的に書くことができます。ここで、$${p_1, \dots, p_m, q_1, \dots, q_n}$$は論理変数で、$${\phi}$$はそれら論理変数のみが現れる限量子のない論理式です。
2QBFは、論理変数$${q_1, \dots, q_n}$$が0であろうと1であろうと$${\phi}$$が1となる論理変数$${p_1, \dots, p_n}$$の値があるかを問う問題です。
因みに2QBFは論理回路を合成する問題を表すことができます。以下のような2種の限量子が付いた論理式を考えます。
論理式$${\phi}$$が論理回路に満たしてほしい仕様(入力の論理変数iと出力の論理変数$${o}$$が満たす関係)を表し、論理式$${\psi}$$が入出力を意味する変数$${i}$$と変数$${o}$$そして論理変数$${c}$$からなる論理回路を表すとします。ここで上記の限量子付き論理式が充足可能ならば(かつそのときだけ)、仕様と論理回路の入出力の関係が一致する論理変数$${c}$$への値が存在します。ですので上記式の充足可能性判定問題を解くことで、仕様と一致する論理回路を合成(具体的には論理回路に現れる、論理変数$${c}$$への値の推論)することができます。
まとめ
量子コンピュータ(アニーリング型)は巡回セールスマン問題より難しい問題は解けません。解けない問題として、2QBFを利用した論理回路の合成などがあります。
とはいえ、量子コンは巡回セールスマン問題を解く能力はあるので、様々な社会の問題を解決する将来有望な技術だと思います。個人的には、巡回セールスマン問題よりも簡単なSATが解けるだけでも夢があると思います。
あとがき(なんでこの記事を書こうとしたかのか)
QUBOは巡回セールスマン問題と同程度の難しさなのでそれより難しい問題は解けないという情報は、(証明は簡単だけど。。)量子コンピュータ(アニーリング型)のアプリを考えるときに役に立つと思い記事にしました。
実は、自分も2年前に量子コンのブームに乗ろうと(2QBFを解く必要がある)プログラム最適化の問題をQUBOに変換しようとしたのですが、なかなかうまく行きませんでした。その時、QUBOが巡回セールスマン問題と同程度の難しさとわかっていれば、QUBOへの変換方法を考えるのに費やした(低く見積もって)数日間を無駄にしなくてよかったなあと。
それともう一つのこの記事を書いた理由は、QUBOはNP完全といっている論文があったので、その間違いの指摘です。QUBOはFP^NP完全です。
書きっぷりについての言い訳
・この記事は、計算機科学(特に、計算複雑性理論)を軽く学んだことがある人が概要を理解出来るくらいのものを目指しました。
・この記事は、多項式階層が潰れないことを仮定し書くことで、文章の歯切れを良くしています。まあ多項式階層は潰れないと思うので大丈夫かと。