HPC研究会というのがあって、特別講演に第一原理計算をしている人が
出てきたので、空気をあえて読まず思わず質問した(そうして、僕のような人間は嫌われる)。発表の中で、数理の人との協調が重要といっていた。電子相関の問題はとても難しいと、コメントしたら、どう難しいのか分からないといわれるので巡回セールスマン問題を解くくらい難しいといったが
解ってもらえなかった。物理の人がわかりやすいと思われる例は、spin-glass系の基底状態を求めるという問題である。これは巡回セールスマン問題と同じくらい難しい問題であるMax-cut問題と似た、そして本質的には同じ構造しているため、その難しさを理解しやすいと思われる。なお、この問題は、2-RDMの対角要素のrepresentablity条件かどうかを決める問題とも等しい。量子力学に於ける、Hamiltonianの基底状態を求めるという問題に、人間が出会ったなかでも、大変難しいとされる問題を埋め込むことができるのである。
これは深刻であり一般にこれこれの処方で解くというアルゴリズムが無いということを示している。さらにまた量子コンピュータを用いてもダメである、ということも、知られている(量子化学の系ではうまく行くように見える場合もある)。
さて、toy problemを埋め込んだにすぎないじゃないか。我々は電子系を問題にしているのである、という反論もあるかもしれないが、残念ながらほぼ同じような結果が電子系でも知られている。昨年Nature Physicsに出た論文で、2次元Hubbardモデルの基底状態をefficientに求めることはできないことが示された。これはNP-hardなのである。さらに、DFTにおける汎関数、F[rho]も、同じことがしめされている。DMRGがなぜうまくいっているように見えたかというと、電子相関の構造が比較的簡単な系に応用したからである。つまりDMRGでも2次元、3次元の問題は解けない(=つまり固有値のdecayがexponentailに遅い)。
物性の人たちはLDAで満足している(のか?)ので、平均場近似 - Hartree-Fockさえ、難しいというが、その難しさについてもコメントが必要だろう。Hartree-Fockは平均場近似ではあるが、最小化する関数は二次関数であり、最適化の人たちの言葉では、二次計画を解くことになる。残念ながらこれは凸ではないため、厳密な最小化問題はNP-hardである。要するに厳密に解けた、ということをいうのはとてもとても難しい...のだ。
さて、厳密なアルゴリズムでNP-hardが示されたからといって、悲嘆にくれることは一切ない。「うまく行く」系を見つけてそれっぽい値を出す、ここはHeuristicsを用いてやれば良い。最終的には、電子相関の分類、ということになろう。どういうタイプがあり、どう解けるか、これを分類して行くのである。
Frank Verstrateだったっけの論文や、量子情報の人たちや、N-representability問題を扱っている人たちの仕事が理解の役に立つと思われる。
出てきたので、空気をあえて読まず思わず質問した(そうして、僕のような人間は嫌われる)。発表の中で、数理の人との協調が重要といっていた。電子相関の問題はとても難しいと、コメントしたら、どう難しいのか分からないといわれるので巡回セールスマン問題を解くくらい難しいといったが
解ってもらえなかった。物理の人がわかりやすいと思われる例は、spin-glass系の基底状態を求めるという問題である。これは巡回セールスマン問題と同じくらい難しい問題であるMax-cut問題と似た、そして本質的には同じ構造しているため、その難しさを理解しやすいと思われる。なお、この問題は、2-RDMの対角要素のrepresentablity条件かどうかを決める問題とも等しい。量子力学に於ける、Hamiltonianの基底状態を求めるという問題に、人間が出会ったなかでも、大変難しいとされる問題を埋め込むことができるのである。
これは深刻であり一般にこれこれの処方で解くというアルゴリズムが無いということを示している。さらにまた量子コンピュータを用いてもダメである、ということも、知られている(量子化学の系ではうまく行くように見える場合もある)。
さて、toy problemを埋め込んだにすぎないじゃないか。我々は電子系を問題にしているのである、という反論もあるかもしれないが、残念ながらほぼ同じような結果が電子系でも知られている。昨年Nature Physicsに出た論文で、2次元Hubbardモデルの基底状態をefficientに求めることはできないことが示された。これはNP-hardなのである。さらに、DFTにおける汎関数、F[rho]も、同じことがしめされている。DMRGがなぜうまくいっているように見えたかというと、電子相関の構造が比較的簡単な系に応用したからである。つまりDMRGでも2次元、3次元の問題は解けない(=つまり固有値のdecayがexponentailに遅い)。
物性の人たちはLDAで満足している(のか?)ので、平均場近似 - Hartree-Fockさえ、難しいというが、その難しさについてもコメントが必要だろう。Hartree-Fockは平均場近似ではあるが、最小化する関数は二次関数であり、最適化の人たちの言葉では、二次計画を解くことになる。残念ながらこれは凸ではないため、厳密な最小化問題はNP-hardである。要するに厳密に解けた、ということをいうのはとてもとても難しい...のだ。
さて、厳密なアルゴリズムでNP-hardが示されたからといって、悲嘆にくれることは一切ない。「うまく行く」系を見つけてそれっぽい値を出す、ここはHeuristicsを用いてやれば良い。最終的には、電子相関の分類、ということになろう。どういうタイプがあり、どう解けるか、これを分類して行くのである。
Frank Verstrateだったっけの論文や、量子情報の人たちや、N-representability問題を扱っている人たちの仕事が理解の役に立つと思われる。