藤井啓祐 「驚異の量子コンピュータ」ﾒﾓ
藤井啓祐 「驚異の量子コンピュータ」ﾒﾓ
第Ⅲ部 量子コンピュータの挑戦
第8章 量子超越をめざして
----------------------------------------------------------------------------------
【まとめ】
・量子超越とは、量子性が計算を指数関数的に加速し、量子コンピュータが従来型コンピュータより高速であること。
・現時点の量子コンピュータの出力は有用なものではないが、グーグルの量子超越は科学技術史上重大な成果。
・量子コンピュータの検証可能性問題は自然科学の根底に関わる問題で、量子計算分野の研究者は物理学の根幹に関わる研究をしている。
----------------------------------------------------------------------------------
＜量子超越＞
・量子コンピュータが従来型のコンピュータ（古典コンピュータ）より高速であること
・量子性により計算が加速される物理現象。
＜量子情報科学＞
・情報や計算の複雑さという尺度で、極限的に複雑な世界のフロンティアを探求する物理。
◎計算の複雑さの測り方
・量子超越のゴール：量子コンピュータを用いて古典コンピュータよりも高速に計算できることを定量的に実証すること。
・量子コンピュータの高速性は、古典コンピュータよりも短時間で答えを出せることに限らない。
・計算規模（サイズ）をＮとしたとき、古典コンピュータではＮに対して指数関数的に計算時間が増大する問題に対し、量子コンピュータを用いてＮに対する多項式的な計算時間に押さえ込めるかが目標。
・古典コンピュータでの指数関数的な計算時間が、量子コンピュータで多項式関数的な計算時間に抑えられるとき、指数関数的な加速があるという。
＜スケーリング比較＞
・問題のサイズに対してかかる計算時間の依存性（多項式的か指数的か）でコンピュータの計算能力を比較すること。
・計算複雑性の分野で計算能力を比較するときはスケーリングが用いられる。
◎物理現象の複雑性
・演算の並列度が、興味のある現象が含む自由度及び精度と同程度になれば、古典力学で記述する物理系はシミュレーションできる。
・古典力学でふるまう物理系は、要求される変数の精度も有限であり、古典コンピュータに比してスケーリングにて指数的な差は生まれない。
・量子力学に従いふるまう物理系では話が変わる。
→シミュレーション対象に含まれる粒子数に対し、指数的な数の変数（確率振幅）が必要。
・計算原理を古典物理学にしたままコンピュータを大きくしても、量子力学に従う物理系のシミュレーションに必要な規模には追いつかない。
・量子系のシミュレーションは、計算原理を量子力学にしないと解決しない
→量子力学に従う物理系のシミュレーションでは、古典コンピュータと量子コンピュータのあいだでスケーリングとして指数的な計算速度差が生じる。
・量子コンピュータによる計算の加速とは、スケーリングによる指数関数的な計算の加速実験を計算機科学的に検証すること。
◎量子超越への道筋
・ランダムな量子回路からなる計算を量子コンピュータで実行する。
・その出力はランダムで、何かの役に立つものではない。
・量子超越では、その出力が有用かどうかは関係なく、量子により計算を加速し、古典コンピュータを上回ることができるか実証することが優先。
・今の量子コンピュータの規模で最も量子コンピュータが得意とする計算を対象とする。
◎古典コンピュータとの戦い
・量子コンピュータの出力の検証には、スーパーコンピュータを用いる。
・誰が量子超越を最初に実証するかを巡り、国際的な量子コンピュータの開発競争が始まっている。
・生まれたばかりの量子コンピュータ 対 ５０年以上かけて成熟してきた古典コンピュータの戦い。
・計算ステップ数が増えるにつれ古典コンピュータは圧倒的に不利。
・古典コンピュータの限界を越えるステップ数の計算が可能な高精度な量子コンピュータが実現される見込み。
◎グーグルの量子超越
・２０１９年１０月２３日、学術誌ネイチャーはグーグルが開発した量子コンピュータが量子超越に到達したことを発表した。
・グーグルは５３量子ビットを搭載したシカモア(Sycamore)と呼ばれるチップを用いてランダムな量子回路を実行してビット列をサンプリングした。
・５３量子ビットすべてを使った場合、量子コンピュータで２００秒かかるタスクを従来コンピュータで実行すると、スパコンでも１万年かかると結論づけた。
・史上はじめて量子コンピュータが古典コンピュータの速さを越えた。
・ＩＢＭは１万年も必要なく、２日半で十分という見積もりを発表。
・現在の量子コンピュータの限界
①従来コンピュータに不得意な問題を計算している。
②出力はランダムなビット列で、有用なものではない。
・上記の限界をふまえても、グーグルの成果は科学技術史上重大な成果。
①量子力学の原理で動作。
②プログラム可能で万能性をもつる。
③数学的にきちんと計算ルールを記述可能。
④従来のコンピュータ上でシミュレーションを行う最速アルゴリズムでも量子ビット数や計算ステップ数に対し指数関数的に時間を要するような計算をするマシンを史上はじめて実現
⑤スパコンよりも速く特定のタスクを実行できることを実験的に示した
・今回の偉業は、ライト兄弟における人類初の１２秒のフライトに相当する。
・当時は約に立つものではなかったが、振り返ると現在の飛行機に繋がる重要な最初の一歩。
・量子コンピュータ研究者の究極目標は、量子誤り訂正を搭載した、誤り耐性量子コンピュータを実現すること。
・それを実現するには１０年、２０年といった研究開発が必要。
◎自然を検証することの難しさ
・古典コンピュータを超越していることは、同時に量子コンピュータの出力結果の検証が難しいことを意味する。
・検証に使うための量子コンピュータがないため、ランダム量子回路の出力を簡単に検証できない。
・量子コンピュータを検証するには量子コンピュータが必要。
・検証可能性問題は技術的問題ではなく、自然科学の根底に関わる問題。
・現在研究が活発に進められている一つの大きなテーマ。
・検証可能性は計算機科学において古くから研究されてきた。
・問題を定義するための一つの方法として利用されている。
・問題の難しさを測るひとつの方法：答えを導き出すために必要となる計算ステップ数。
・計算ステップ数の代わりに、答えの候補が与えられたとき、その答えが正解であるかどうかを検証することに必要なステップ数で問題の難しさを測る。
＜ＮＰ問題＞
・答えの候補が与えられたとき、それが正しいかどうかを検証することが効率良く（問題サイズの多項式関数的時間）できる問題のこと。
・答えの正しい候補を見つけるのにどのくらいの計算ステップが必要かはわからない。＜Ｐ問題＞
・正しい答えそのものを効率良く見つけることができる問題↓
・ＮＰ問題はＰ問題よりも真に難しいかの、ＮＰ＝Ｐなのかは未解決問題。
・素因数分解問題は、今のところ古典コンピュータでは簡単に解く方法が知られていないＮＰ問題でありながら、量子コンピュータでは簡単に解くことができる。
→量子コンピュータが量子コンピュータとして機能しているかどうかの検証に、素因数分解問題を利用できる。
・仮に素因数分解問題を古典コンピュータでも効率良く解くことができるアルゴリズムが見つかった場合、検証方法として使えない。
・どのような問題設定にすれば、量子コンピュータからの回答から、より強い意味で量子コンピュータの存在を検証できるかが研究されている。
・物理学者が仮説を立て、それを実験で検証する営みは、古典コンピュータしたもたない我々が、自然＝量子コンピュータを検証する問題に等しい。
・量子計算分野の研究者は、物理学の根幹に関わる重要な研究をしている。
・ＮＰ問題を拡張し、量子コンピュータで効率良く答えを検証できる問題を定義することで、量子コンピュータを手にいれた人類がどのように自然を理解できるか、といった未知の知見を教えてくれる。
