Prime2Ising

素因数分解から帰着した落とし戸付きのイジング模型のハミルトニアンを計算します。

FACTORING -> Circuit SAT -> MAXSAT -> QUBO -> MAXCUT -> Ising

の順に経由して二体相互作用のみのハミルトニアンをO(n^2)で作ります。 FACTORINGからC-SATへの帰着は工夫するとより効率的にできて、 例えばこれやこれ などが知られているようです。前者でnlognになるらしいです。

4=2*2を変換したising