問題の難しさ

【 問題の難しさ 】

Mahadevは、量子コンピュータが行う計算についての最も基本的な問題である、「量子計算の古典的検証問題」を解きました。

我々人間が、量子コンピュータにある計算を実行させた時、量子コンピュータが我々の指示通りに計算を行ったのか、我々の予想もしなかった量子の奇妙な振る舞いで我々の意図とは違うデタラメな（我々にとって）計算をしたのかを、我々人間がチェックできるのかという問題は、ひとまず「大丈夫。人間がチェックできる」という形で解決されました。

ここでは、まず、この問題が難しい問題であることを確認してみたいと思います。

我々が、プログラムをデバッグしようとする時、 まず、プログラムの中の変数がどのような値を取っているかをチェックします。プログラム実行中のコンピュータの「状態」は、各変数へどのような値が割り当てられているかで決まります。

次に、プログラムのステップが進んだ時の、変数の値の変化をチェックします。変数の値の変化は、コンピュータの状態の変化をもたらすのですが、コンピュータの「ふるまい」というのは、この状態の変化の継起する系列に他なりません。

コンピュータの振る舞いが、正しいものかは、最終的には変数への値の割り当てに帰着する状態の変化を追いかければチェックできます。

n個のqubitからなる量子コンピュータの状態は、2^n 個の基底からなるベクトルで表現されます。それは、普通のコンピュータで言えば、 2^n個の変数があることに相当します。

我々は、この2^n個の変数の変化をトレースできるでしょうか？

普通のコンピュータ・プログラムで変数の数nが 50を超えるのは珍しくないかもしれません。ただ、かつての Google IBMの論争は、2^53個の変数をどうやってトレースするかの論争と見ることができます。nが大きくなるにつれ、 2^n個の変数のトレースは、我々の手に余るようになるのは明らかです。

量子コンピュータの働きをチェックし検証することの難しさは、実は、もう一つあります。それは、我々は、量子コンピュータの状態を正確に知ることはできないという問題です。

量子コンピュータの状態は、先に見たように2^n個の状態の「重ね合わせ」になっているのですが、その状態を知ろうとして観測すると、その「重ね合わせ」の状態は失われてしまいます。

観測によって得られるのは、n個の古典bit の情報だけです。　

普通のコンピュータでは、その振る舞いの正しさを検証するためには、コンピュータの状態とその変化を知ることが不可欠です。それは、量子コンピュータでも同じです。

普通のコンピュータのデバッグでは、コンピュータの状態とその変化は、基本的には変数の値をトレースすることで可能なのですが、量子コンピュータでは、そもそも、状態を決定している変数の値に直接アクセスすることができないのです。

マハデフは、こうした難しさをどのように解決したのでしょうか？

--------------------------------

「量子コンピュータの働きをチェックし検証する -- 問題の難しさ」 を公開しました。
https://youtu.be/_4mV_vMQUZc?list=PLQIrJ0f9gMcOQHQ6KmWuUxuRZkHT-2gZ-

スライドのpdf
https://drive.google.com/file/d/1NuLpiSWtDEORImbf-PTvQv6Hcw9r7ajZ/view?usp=sharing

blog：「問題の難しさ 」
https://maruyama097.blogspot.com/2022/11/blog-post_14.html

まとめページ「量子計算の古典的検証 」　
https://www.marulabo.net/docs/cvqc/

参考資料
Urmila Mahadev, Classical Verification of Quantum Computations
2018/09/12  https://arxiv.org/pdf/1804.01082.pdf