位相とか計算量の話

QmQ @gejiqmq

計算量関係の面々が、これにヒントを得て考えたのが非局所ゲームの話。つまり、遠隔地にいるAとBにCがある質問をし、答えからゲームの利得を計算する。例えばスピンの向きとか。もし、古典力学なら、ゲームの平均の利得はベルの不等式で制限され、量子ならTirlsonまで行く。

QmQ @gejiqmq

このゲームの利得の期待値の最大値が計算可能か否か？という問題を考える。すると、この答えは、「AとBの合成系」をどうモデル化するかに依存してしまう。ヒルベルト空間AとBのテンソル積でやるか、可換な二つのC*代数と考えるか。前者なら計算可能でなく、後者ならOK

QmQ @gejiqmq

AとB,に検証者が質問して計算を進めるモデルを多証明者対話証明といって、古典では非常によく調べられている。近似不可能性への応用で有名なPCP定理はこのモデルで受理可能な言語がNEXPであることの、（ある意味での）スケールダウンである。

QmQ @gejiqmq

古典では非常に重要な概念なものだし、ベルの不等式との関係もあるので、量子でも２０００年ころから研究が始まった。まず、量子でもNEXPができるか。ベルの不等式の破れでもわかるように、量子のA,Bは古典の場合よりもCを騙す能力が高い。そこで、直感的には古典よりも弱そうなわけである。

QmQ @gejiqmq

ところが、数年前、伊藤Vidickによって、ついにNEXPが量子でできることがわかった。となると、今度はどこまでいけるの？ということが問題になる。先のゲームの値の計算量はこの問いの一環である。で、ある時からこの問題には作用素代数のプロが大きな顔をしだした。先にもいったとおり、

QmQ @gejiqmq

理由は、先にも言った通り、合成系の定義によって答えがかわるくらい、解析的に微妙な話題だから。今ではこのあたりの話をするのに、topological tensor product の薀蓄が必須になってしまった。系AとBの合成系のオブザーバブルの全体は、A⊗Bとかその和でよかろう。

QmQ @gejiqmq

有限和のときは定義はあきらか。無限和のときが大変で、どういう位相をいれるかで、えられるものが違ってくる。で、自然なテンソル積は無限にたくさんあって、最初と最大がある。普通にヒルベルト空間をテンソル積にして、その上のオブザーバブルを考えると、最小でも最大でもない、中間のがでてくる。

QmQ @gejiqmq

こういう面倒なことは、考えたくないというのが、数学者じゃない普通の人の反応だろう。だけれど、実際にゲームをやって、利得の計算をすることは実際できるのだから、これは一応、原理的には観測可能な量にかかわる話である。なので、面倒だから本質的でないにちがいない、と知らぬ振りもできない。

QmQ @gejiqmq

多証明者対話証明の量子版を初めて定義していらい、ずっとこの関連のことをやってきて、最後の最後で振り落されてしまった。やはり高尚な数学では数学出身にかなわない。なんとか食いつける隙間があればいいが、、、

QmQ @gejiqmq

計算量関係で最近面白いとおもっているのは、きれいなQubitが少数、たとえば一つとか二つで、あとはNoisyなQubitがあるモデル。当然確率的計算になるのだけれど、誤り確率の増幅が長い事できなかった。量子でも古典でも、普通の確率的計算のモデルなら、何べんも繰り返して多数決を

QmQ @gejiqmq

多数決をとれば、少々の誤り確率があっても、非常に高い確率で正しい答えをだすことができる。しかし、今は１つのqubit以外は全部ノイズがのっているので、多数決をとっても、その結果を書くスペースすらない。

QmQ @gejiqmq

なので、このモデルで正解確率の増幅ができるかはかなりの謎であった。それが、最近、かなーりできてしまうことがわかったのである。１つのクリーンなqubitがあれば、両側でもかなりできてしまう。詳細はまだ論文がでてないところもあるので、やめておく。

QmQ @gejiqmq

多分、古典だと同じようなことはできないのではないか。基本的な手法としては、例えばWatrousがQMAの正解確率の増幅で用いたような技を使う。つまり、一度計算を最後までやったあと、逆に回してもとに戻し、最初からやりなおすのだ。

QmQ @gejiqmq

こんなことが出来るのは、量子でユニタリだから。で、そもそも、なんで正解確率の増幅をしたいかといえば、それは完全問題の話とからんでくる。（実用的には、外に古典的なメモリーを足せばよいので、この計算モデルの枠の中での増幅を考える意味はあまりない。）

QmQ @gejiqmq

ある計算量クラスで一番難しい問題を完全問題という。もう少し正確には、他のどんな問題も、その問題に帰着できるような問題の事。で、この帰着のために問題を変形するとき、大抵正解確率が変化してしまう。なので、増幅して正解確率を合わせてやりたいから。

QmQ @gejiqmq

さて、これまではノイズがのったqubitは常に０と１が確率半々で混ざっていると仮定されてきた。そこで興味があるのが、ここから外れた場合である。どんな状態にあるか、全然不明のときは何ができるか。偏った分布だと、実は先に述べた増幅の方法はうまくいかない。

QmQ @gejiqmq

逆に、０と１の割合が半々より定数ほどもずれていて、そのずれの大きさを知っていたとしよう。すると、algorithmic coolingとかいわれる手法で、ノイズを一部の量子ビットに押し付け、きれいなqubitを得ることが出来る。（正確には、多項式分の１程度のノイズはのこったまま）

QmQ @gejiqmq

algorithmic cooling はShulmann Vasiraniが９０年代の終わりごろだした。独立に、北川先生が別のアルゴリズムを出している。世界的には前者がやたらと有名だ。しかし、その論文の証明は自分にはよくわからんかった。一方、後者の方は、

QmQ @gejiqmq

北川さんたちのはきちんとした論文に書いたのがみつからない。しかし、講演などのアブストラクトの断片から、再構成することはさほど困難ではなく、その正しさは理解できる。分布が独立でない場合は彼らのままでは使えないけれど、DeFenettiを組み合わせればなんのことはない。

QmQ @gejiqmq

しかしながら、こういった技が使えるには、分布についてのある程度の知識がないといけない。それが全然なかったらどうだろう。せめて、一様分布の時と同じことくらいはできるのだろうか。今のところは、多分できると思っている。