高橋惇くん（現中国科学院）との共同研究の論文がJournal of Statistical Mechanics: Theory and Experimentに掲載されました：

Phase transitions in quantum annealing of an NP-hard problem detected by fidelity susceptibility

Jun Takahashi and Koji Hukushima
J. Stat. Mech. (2019) 043102
DOI: https://doi.org/10.1088/1742-5468/ab0819

量子アニーリングの研究など一生しないと思っていたのです．門脇さんの博士時代の研究はリアルタイムで見ていて，触手が伸びなかった．説明できないもやもやした感じがあったが，基本的に触手が伸びないということは面白くないと思っていたということです．それが，一変したのは高橋くんがいろいろ考えてたからで，この研究は面白い．

子供のような感想だけど，本当にそう思う．

ある種の組み合わせ最適化問題は解くことが難しいとクラス分けされている．計算量理論でNP困難と言われるクラスである．例えば．統計物理学のモデルでは空間次元が３以上のイジングスピングラスの基底状態探索はこのクラスに属する．このようなNP困難な問題は量子アニーリングをつかえば解けるだろうか？

にわかに答えが出る問題ではない．しかし，解けないだろうと強く信じられている．解けないという意味も難しいが，ざっくりとは多項式時間では解は見つからないと思ってよい．そのとき，解けない理由は何だろうか?よく言われることは，量子アニーリングの過程で相転移が起きることが原因だと考えられている．特に，

１次転移が問題である．一次転移点でエネルギーギャップが問題のサイズの指数関数的に小さくなり，そこをアニーリングで通過するときに断熱的に基底状態を保つために必要な掃引速度は指数的にゆっくりする必要があり，結果として指数時間が必要になる．確かに一次転移は難しいわけである．だから，「NP困難な問題は一次転移をするので，量子アニーリングでも難しい」という単純なシナリオは思いつくかもしれない．しかし，

りゆうとしてはそれでは不十分であると考える．NP困難問題は一次転移する…とは考えにくいからである．そもそもNP困難などの計算量理論の分類は最悪評価に基づいている．この論文で議論した問題は最大独立集合問題と呼ばれ，NP困難のクラスに属する問題である．最大独立集合はグラフ上に定義される問題であり，真に難しいグラフもあれば，簡単にとけるグラフもある．全ての最大独立集合問題が難しいわけではない．このような状況で，最大独立集合問題は量子アニーリングの過程で一次転移が起きるとは思えないわけである．むしろ，起きてはいけないとも思える．

NP困難問題の量子アニーリングにおける難しさの起源を議論したのがこの論文の目的である．特に，同じ問題の中の例題のバラエティと熱力学極限で定義される相転移の存在との整合性のとり方に気を使った．我々の結果の示唆するところは次のとおりである．全ての例題は共通の相転移を示す．しかし，それは一次転移ではなく，二次転移のように見える．より詳しくその相転移の詳細を調べてみたが，相の同定には至らなかった．少なくともよく知られているスピングラス相転移とは思えない．そして，その謎の相の中では自己平均性は破れていて，一次転移を示す例題もあれば，そうでない例題もあるように見える．一次転移点も例題によってバラバラである．この謎の相はこのような性質を持っている相なのであろう．

ぐたいてきに何をやっているかに興味を持たれたらぜひ論文を見て欲しい．解きたい例題の解を唯一にすることが技術的には重要であり，その方法とか，SSEでフィディリティ感受率を計算する方法とか．まだ，決定的な解答にはなっていないなぁとも思う．本当にこんなシナリオが全てのNP困難問題で起きていると楽しいし，難しい問題の難しさが物理的な現象に影響を与えていると思うとワクワクする．最後のところは惇くんに教えてもらった愉しさである．