学校で習った数学とはまるっきり違う世界へ、ようこそ。
ここは洞窟のなか。暗い地下道を進んでいくと、つきあたりに鍵のかかったふたつの部屋が現れます。中には、全知全能の仙人がひとりずつひっそりと佇んでいます。あなたが質問すれば、仙人たちはひとりずつ答えてくれます。
ところが困ったことに、仙人たちが常に真実を語ってくれるとは限りません。そして仙人同士は互いに意思疎通を図れないものの、あなたの問いかけに返してくる答えそのものはもつれ合い、連動しています。ですから、あなたが知りたい問題の答えを導き出すには、よく考えて賢く質問しなければなりません。質問によって、そしてその答えによっては、あなたはこの世界に存在するすべての問題を解き明かすことができるのです。
…これは新手のRPGゲーム、ではありません。量子もつれ現象を盛り込んだ理論上の計算モデルです。
数学の世界では、しばしばこういった机上の計算モデルを使って、コンピューターができることとできないことを区別しています（理論的に）。
コンピューターの性能がどんどん向上するとともに、よりたくさんのことがより速くできるようになってきました。ならば、量子コンピューターは？と考えたのがアメリカの名門・カリフォルニア工科大学の研究員であるAnand NatarajanさんとJohn Wrightさん、ほか3名の天才的数学者たち。
新しい計算モデルを編み出して理論的に検証を重ねた結果、ふたつの量子コンピューターがひとつの問題に取り組んだとき、コンピューターの｢できること｣の範囲が飛躍的に拡大することを証明しました。いままでのコンピューターで解けなかった問題も、量子コンピューターなら解ける！という結論が出たわけです。
証明の終着点は｢MIP*=RE｣。非常にシンプルです。しかし、そこに至るまでには165ページにもおよぶ難解な数理解析がビッシリと…。
難解なのもそのはず、これは計算複雑性理論という分野に入ります。難解すぎてまだ他の研究者のチェックが追いついていないのですが、最終的にだれも反論できなかった場合は、量子物理学と計算理論と数学との架け橋となる重要な研究成果です。
計算できるか、できないか
コンピューターの｢できること｣の範囲はどうやって調べるんでしょうか。
コンピューターはそもそも計算する機械。｢計算（compute）｣は、足し算・引き算などの四則演算よりももっと幅広い意味で｢状態Aの時、外部からの入力（刺激）を受けて判断を行い、状態Bへ移る｣ということです。これを状態Cへ…状態Dへ……と段階的に進んで行って、最終的にすべての手順を追って停止するまでが計算です。
これ、つまりはアルゴリズムですね。
計算複雑性理論は、アルゴリズムの計算量を考える学問です。言い換えれば、与えられた問題をどれぐらい速く解けるかを考えます。計算できるか、できないかの区別は、アルゴリズムを実行するのにかかる時間が基準となっています。
複雑性クラスP──計算できる
たとえばnという整数をk乗にする計算。kにも整数が入ります。kの値が1、2、3…と増えていくと、解がどんどん大きな数にふくらんでいって、計算にとんでもなく長い時間がかかります。
でも、この計算はコンピューターが｢計算できる｣とされている許容範囲内。逆に、｢これよりもっと時間がかかっちゃったら数学的に効率よく解けない｣とみなされるのです。この問題の複雑性オーダーは｢多項式時間計算可能クラス（Polynomial Time）｣、略してクラスPと呼ばれ、計算できるカテゴリーに入ります。
では、クラスPじゃなかったら計算できないのでしょうか？
複雑性クラスNP──計算できるのかもしれない
たとえ多項式時間内に解けないとしても、あらかじめ答えの見当をつけておいて、その見当が合っているかどうかを多項式時間内に確かめられる問題であれば、｢非決定性多項式時間（Non-deterministic Polynomial Time）｣、またはクラスNPに入ります。
NP問題で有名なのは色塗り問題です。
点を線でつないだグラフがあります。点を3色に分けて塗ります。ただし、隣り合わせの点は同じ色に塗れません。
点の数がまだ10個だったら楽勝。ところが、点の数が100、1,000と増えていくと、とんでもなく時間のかかる問題になってしまいますし、コンピューターのメモリに入りきらないほどの情報量にもなってしまいます。
このように解くのは不可能でも、できあがったグラフがちゃんと色塗りされているかどうかをチェックするのは可能なので、クラスNPに属しているわけです。世界地図を4色で塗り分ける問題もここの複雑性オーダーに入ります。
ちなみに、クラスNPとクラスPは同じかもしれないけど、まだ証明されていません。クラスNPに属している問題も、もしかしたら効率的に解けるアルゴリズム自体がまだ見つかっていないだけで、実は多項式時間内に解けるかもしれないからです。
複雑性クラスIPとMIP
さらに、1980年代には新たな計算モデルが提案され、数学者たちの議論の的となりました。
Quanta Magazineに載っていた例がわかりやすいので、こちらに引用します。
あなたの前にふたつのブロックが置かれています。あなたはこのブロックの色が同じか、それとも違うかを判断しなければいけません。ところが、色覚多様性（色盲）により、あなた自身で色を見分けることはできません。
そこで、｢証明者（prover）｣と呼ばれる第三者に質問して、答えを推測することにします。ただし、証明者は必ずしも正直に答えてはくれません。
この場合は、どういう質問をすれば正しい答えに導いてもらえるでしょうか？
まず、ブロックの色が違うか聞きます。仮に証明者が｢はい｣と答えたとしましょう。次に、ブロックにAとBとの名前を付け、証明者に覚えてもらってからブロックを背後に隠し、ランダムに証明者の前に出してどちらのブロックだかを教えてもらいます。
もし本当にブロックの色が違っていたなら、ブロックAとBの違いを見分けるのは百発百中。でも、もし同じ色だった（最初の答えが間違っていた）としたら、ブロックを正確に言い当てる確率が50％しかありませんね。
このようにして、証明者に質問することで解を得られる問題をクラスIPといいます。
さらに、複数の証明者がいる場合はクラスMIPに…、という具合に、効率的に解けない問題でも、｢証明者｣という名のコンピューターを使って答えを知ることができるわけです。
さて、ここからが量子コンピューターの出番です。
世界で初めて複雑性クラスMIP*を定義
MIP*についている｢*｣は、量子コンピューターを意味しています。比較的新しい分野なため、MIP*が定義されたのは｢MIP*=RE｣が初めて。
証明に成功したAnand Natarajanさんは、まだ学生だった頃、コンピューター科学者・Scott Aaronson氏の講義を受けて、MIP*についてほとんどなにも知られていない現状にショックを受けたそうです。
｢MIP*がものすごく幅広い可能性のなかで語られていて、計算複雑性理論をやっている者にはめったにない機会だった｣と米ギズモードに語っています。共著者であるJohn Wrightさんも、IPとMIPはすでに定義づけられているので、MIP*を解明するのは僕たちしかいない、と考えたそうです。
量子もつれを味方につけるともっと難しい問題が解ける
NatarajanさんとWrightさんはタグを組んでこの問題に取り組み、2019年には量子のもつれがあるおかげでMIP*のほうがMIPよりもはるかに難しい問題を解けると発表しました。
なぜか。量子もつれは、いったん相互作用した量子は分離できない現象を指します。片方の量子に変化があると、どんなに遠く離れていようがもう片方の量子に影響します。
だから、ふたつの量子コンピューターに質問して答えを得ようとするとき、量子もつれのおかげで答えが連動しているので、より質問者にとって有利な情報を引き出せるのです。
それと同時に量子力学の基本原理である｢不確定性原理（Uncertainty Principle）｣が作用するので、量子コンピューターの答えはスクランブルされてもう片方の量子コンピューターには伝りません。だから、ふたつの量子コンピューターはお互いなにを言ったか知ることができないので、共謀できないのです。
停止性問題も解ける
さらに、Natarajanさんたちはテクノロジー・シドニー大学のZhengfeng Jiさん、カリフォルニア工科大学のThomas Vidickさんと、トロント大学のHenry Yuenさんを交えて2020年1月14日にMIP*=REを証明することに成功。量子コンピューターを使えば複雑性クラスREに属するすべての問題が解けることを証明しました。
REというのは答えが｢はい｣か｢いいえ｣の決定問題のうち、有限時間内に｢はい｣の答えが得られるすべての問題。ものすごく幅広い領域です。REで有名な例が｢停止性（判定）問題｣です。
あるアルゴリズムがある入力を受けた場合、有限時間内に停止するかどうかを判定できるか？
これはいままでのコンピューターでは解決できない問題でした。コンピューターの父・アラン・チューリングが、84年前にすでに｢停止性を判定できるアルゴリズムは存在しない｣と論破しています。
にもかかわらず、もしMIP*=REが本当だとしたら、停止性問題も解決できるようになる。量子コンピューターを使えば、いままで解けなかった問題も解けるようになるわけです。
量子コンピューターはいままでのコンピューターとは決定的に異なることを、MIP*=REは改めて突きつけています。
44年未解決だったコンヌ問題を否定
さらにさらに、MIP*=REは44年のあいだ未解決だった｢コンヌの埋め込み予想｣を否定したのだとか。カリフォルニア工科大学の理論物理学者、John Preskill教授もその功績をツイッターで大絶賛しています。
Amazing development: The Connes Embedding Conjecture, open since the 1970s, seems to have been refuted using quantum information tools, by Ji, Natarajan, Vidick, Wright, and Yuen. https://t.co/8pFqzQM334
— John Preskill (@preskill) 2020年1月14日
今まで｢ほんとだったら便利だな～｣と期待されていたコンヌの予想が否定されただけに、抽象代数学・非可換実代数幾何学・量子情報理論など関連性の高い分野にじわじわと波紋を広げていきそうです。
NatarajanさんもWrightさんもまだポスドク研究員で若いのに、これだけ大きな仕事を成し遂げるとはお見事…!!
今となっては代数学の式でさえ解けるかどうか怪しげな私も、コンピュータ－の恩恵にあやからない日はありません。我が家のパソコンにも計算理論や計算複雑性理論の知見が活かされていると思うと感慨深いですし、これからの時代に花開く量子コンピューターが楽しみになるニュースでもありました。
Reference: 京都大学数理解析研究所, Quanta Magazine, 『チューリングの計算理論入門』高岡詠子著, 『量子コンピューターが人口知能を加速する』西岡秀稔・大関真之著
