D-Wave 2Xの性能について

QmQ @gejiqmq

@fgksk 本当の最悪の計測はむりでしょう。ただ、難しいベンチマークつくって比較というのはあるでしょう。平均計算量で簡単になってしまう問題、サットとかナップザックとかの場合、ベンチマークの作り方は様々工夫があるようです。

Keisuke Fujii @fgksk

@gejikeiji そーなんですね。そうやって構成した問題だとSAより早いソルバはいくらでもあるんですか？だとするとまだまだ厳しいorそもそも筋が悪い。

QmQ @gejiqmq

@fgksk 例えば素因数分解で難しいのをSATでエンコードしちゃう手があるかと。

Keisuke Fujii @fgksk

@gejikeiji そうですね。それはいつもQAやってるひとに僕は言っています。

Keisuke Fujii @fgksk

@gejikeiji QAは量子モンテカルロで古典計算機上でもうごき、QAでpolyなら量子モンテカルロでもoverheadは増えるけど、polyという話を聞く事があって、じゃぁ素因数分解だとどうなるの？っていうのが素朴な疑問です。

Keisuke Fujii @fgksk

@gejikeiji QAがすごいなら実時間QAと量子モンテカルロby古典計算機の間に指数的ギャップがあるはずで、実時間QAと量子モンテカルロby古典計算機でギャップがないならQAは素因数分解を効率よくとけない。

Keisuke Fujii @fgksk

@gejikeiji ということでQAで素因数分解解こうとしたらどうなんですか？といつも質問しています。

Keisuke Fujii @fgksk

@gejikeiji でもD-waveマシンとかで素因数分解やらないのはworst caseではあまりよくないからかなーと思っています。素因数分解できたほうがよくわからないrandomな問題の集合をとけるよりimpactあるし、定量的ですよね。

Keisuke Fujii @fgksk

@gejikeiji 「768bitは1500台並列で1年」みたいな古典のいいリファレンスありますし。

QmQ @gejiqmq

@fgksk For example, you can generate a boolean CNF formula whose satisfying assignment encodes non-trivial factors of an input number.

QmQ @gejiqmq

@fgksk toughSATなるサイトに書いてありましたから、翻訳するのは普及した技かと。以前、どうやって翻訳するのが効率的か、という論文を見たこともああるので、素人が素手でやるのはまずいんでしょうが。

Keisuke Fujii @fgksk

@gejikeiji これですね：toughsat.appspot.com

Keisuke Fujii @fgksk

@gejikeiji D-waveのマシンは完全結合ではないのでNP完全問題をうめこむのに、かなりサイズを損してますよね（√とかに。）。なので、現状のサイズで素因数分解埋め込んでも（どれくらい効率的にうめこめるのかしらないですが）trivialな問題になるのではと。

QmQ @gejiqmq

@fgksk イジングの形で書いて平均とると、本来みたいものと違うんじゃないかとおもうんですよ。興味ある問題に対応するイジングの具体例は変な難しい集合になってイメージなんですが。

Keisuke Fujii @fgksk

@gejikeiji でも世の中にqubitを全結合できる相互作用なんてないですよね。イジング問題にマップするときに相互作用がある程度localになるのは仕方ないと思います。それでも勝てないと。

QmQ @gejiqmq

@fgksk それは、d-waveマシン、ますます部が悪いのでは。

Keisuke Fujii @fgksk

@gejikeiji 万能量子計算機は相互作用が1D nearest-neighbor two-qubit gateしか使わなくても（誤り訂正まで組み込む事は厳しいですが）素因数分解は多項式時間で解けますよね。

Keisuke Fujii @fgksk

@gejikeiji やっぱり√ぐらいで速くなるというのでは物理的困難さを考えると厳しくて、指数的に勝てるような状況でないと勝負できないので、急がば回れ＝誤り訂正のある万能量子計算機を作れ、だと思っています。

QmQ @gejiqmq

@fgksk はい。そう思います。僕の場合は90年代のニューロだの遺伝的アルゴリズムだのSAだのに踊らされた苦い過去のトラウマで判断しているところがあり、あんまり冷静じゃないかもしれないんですけど。

QmQ @gejiqmq

@fgksk 2Dの構造といい、発想がそもそもずれてる気がするのですよね。余程特殊な目的の機械になるのでは、と思います。その目的を探すのが建設的なのかも。

Jun Takahashi @Jun_Gitef17

@fgksk 横から失礼します。「QAでpolyならQMCでもpoly」を主張する具体的な論文等もしご存知であれば教えて頂けると幸いです！conjecture的な形で主張しているのは iopscience.iop.org/article/10.108… を知ってはいますが、、

Keisuke Fujii @fgksk

@Jun_Gitef17 論文レベルではしらないですけど、界隈では結構そう言ってません？でもそれは非自明な問題だと思います。ギャップがある例とかあるんでしょうか？

Jun Takahashi @Jun_Gitef17

@fgksk 界隈では確かにそういう雰囲気ですけどD-WAVE側の人がそう言ってるのは聞かないですね。iopscience.iop.org/article/10.120… はQMCシミュレートできるけど観測に指数時間かかるというのは物理学会で中島さんがおっしゃってました。

Kodack @iKodack

今朝界隈で話題になっていたぽいToughSAT的過程を経たToughイジングにまつわるQAとか脳とかの評価はモロに俺の来月の北海道のポスターの内容ですので興味ある人は是非議論させてください