量子断熱計算とゲートモデルの等価性について

Kodack @iKodack

断熱計算と量子ゲートモデルの等価性の論文、前に論文紹介で必死こいてある程度読んだんですけど、log-local Hamiltonianの断熱計算とゲートモデルの等価性まで言うだけならsoundnessとcompletenessを理解すればそこまで複雑でもなかった気がします

Kodack @iKodack

5-localから定数を削っていったりってところは雑にしか読んでないんですけど、数学抜きにして5に出来そうみたいなアイデアは割と直観的だった気がします

Kodack @iKodack

断熱計算というかQMAについての話の論文紹介の時に読んだ経験だと、個人的にはarxiv.org/abs/quant-ph/0…やhttp://t.co/0F3ATB86dGが参考になりましたので興味がある人のお役に立てば

Kodack @iKodack

等価であるという事実もそうですけど、個人的にはShorのアルゴリズムを断熱計算に翻訳する効率的な方法がわからないままでも理論の上では等価性の証明が先取りできるという事実がなんか本来なら未来にわかることを先取りして知りえている感じがあって面白いなぁと思います

Kodack @iKodack

前のスライド見返したけどlog-local HamiltonianのQMA完全性の証明が比較的楽なだけで、Universal k-local AQCがゲートモデルを模倣する証明はまた別だから等価性の証明はやっぱ結構めんどいし俺もちゃんとわかってるわけではないぽかった

Kodack @iKodack

恥ずい

根来誠 QuEL @makoto_ne56

@iKodack log-localハミルトニアンってqubit数Nに対してlogN体の遠隔相互作用(近接ではなく)ハミルトニアンのことですか？もしそうなら量子誤り訂正も断熱的にやりゃいいやんっていう論理がかなり苦しくなりますね。恐ろしい閾値に。

根来誠 QuEL @makoto_ne56

Soundnessって何だろ？

根来誠 QuEL @makoto_ne56

近接相互作用しかないハードで遠隔地間に相互作用させるにはpolyN回(2次元ならルートN回)SWAPしないといけない。それぞれのSWAPをフォールトトレラントにするために、、、ということでかなり苦しくなる。

Kodack @iKodack

@makoto0218ne56 さっきのその俺のツイート後で見返したら語弊があるので後悔しているんですが、少なくとも論文で証明された定理としてuniversal 2-local AQCはゲートモデルと等価になっていると思います。なのでその心配は不要だと思います。続

Kodack @iKodack

@makoto0218ne56 log-localについて言及しているのは、俺の読んだ論文では構成がたしか「任意の量子回路の検証はlog-local ham.の最小固有値判定にできる→頑張ると2-localにできる→2-local最小固有値は2-local AQCにマップ可能」続

根来誠 QuEL @makoto_ne56

@iKodack 良く3-localって言うときは実は全然ローカルじゃなくて、系のどこかから無作為に3つとってきて三体相互作用を作るとかあるじゃないですか？そういうのではなく三次元以下最近接とかを意味するのですか？

Kodack @iKodack

@makoto0218ne56 よって2-local AQCは量子回路を模倣できる、となっていました。最初のlog-localまでの話は割と理解できたのですが、二個目以降の部分が私にとって難解でだったという話です。続

Kodack @iKodack

@makoto0218ne56 これでlog-localまで～と言ったのですが、それは私の勘違いでlog-localAQCがゲートモデルを模倣するのは正しいと思いますが、実際には三個目の項目も証明されないと等価性が証明できないのでその証明はやっぱり結構込み入っていると思います。

Kodack @iKodack

@makoto0218ne56 読んだのだいぶ前なので違ったら申し訳ないのですが、QMA完全かという意味では隣接相互作用の場合も帰着で証明されていたと思います。つまり無作為な3つとlattice隣接の最小固有値問題の難しさという意味では同じくらい難しいということだったと思います

Kodack @iKodack

@makoto0218ne56 なのでAQCで探索するべき対象は空間的に隣接相互作用しているハミルトニアンの固有値問題で良いと思うのですが、実際に実験するときにも空間的な隣接相互作用のみでよいかどうかは多分良いとは思いますがはっきりと答えることが出来ないです。すいません...

Kodack @iKodack

@makoto0218ne56 解きたい問題の難しさがどこらへんまでQMA完全に含まれるのか？はarxiv.org/abs/1212.6312を参考にしてます。

根来誠 QuEL @makoto_ne56

@iKodack やっぱり肝はそこですね。量子アルゴリズムはいくらでもSWAP作戦使ってもいいけど、誤り訂正のアルゴリズム(プロトコル？)にSWAP作戦を使うと閾値がえぐいことになる。少なくともトポロジカルサーフェスコードレベル(～1％)は無理。

Kodack @iKodack

@makoto0218ne56 このあたり議論する相手もいなくて自分でも曖昧なんで是非今度議論したいのですが、二つの能力の等価性で議論しているのは「解ける問題」が同じである点ではなく、「解凍の妥当性チェックが出来る問題」が同じという点なので、

Kodack @iKodack

@makoto0218ne56 この議論で隣接okだったからといって、「素因数分解を断熱モデルにするとどうなるのか？」「そのときアニールする対象は空間的な隣接相互作用ハミルトニアンになるのか？」などの解答とはならないというのが現状ではないかと自分では思っています。

根来誠 QuEL @makoto_ne56

@iKodack アニーリングでSWAPとか閾値とかって定義できないんだけど、何となく意味伝わってますかね。 昔1次元系ゲートモデルのフォールトトレラント閾値みたいなのを考えたときに面白いくらい破綻したことがあったので。

Kodack @iKodack

@makoto0218ne56 誤り訂正の閾値に関してそこらへんがどうきくかについては俺があまり理解できてないのですが言及されている誤り訂正のお話は前のPRXの論文などに関する内容のことでしょうか？またアニーリングの方で現実に誤り訂正出来るかに関しては俺は全然理解できてないです…

根来誠 QuEL @makoto_ne56

量子アルゴリズムとフォールトトレラント閾値理論とハードウェアのすべてのレイヤーを知ってて議論できる人ってなかなかいないですよね。 @iKodack

根来誠 QuEL @makoto_ne56

@iKodack PRXはフォールトトレラント量子計算までは議論してないんです。

根来誠 QuEL @makoto_ne56

@iKodack この辺に関してまたどこかでじっくり議論したいですね。F井先生やT手さんとかも交えて。今日はいろいろ教えてくれてありがとうございました。計算量理論勉強しときます。