「量子計算の古典的検証」問題とは何か？

【「量子計算の古典的検証」問題とは何か？ 】

「量子計算」というのは、量子コンピュータが行なう計算のことです。「古典的検証」を行うのは人間です。人間が古典的手段を使って、量子コンピュータが行なった計算が正しいかどうかをチェックすることを、「量子計算の古典的検証」と言います。

「古典的手段」とは、主要には、古典的コンピュータのことを指します。これも、ピンとこない言い回しかもしれません。それは、量子コンピュータとの対比で古典的と言われているだけで、最新鋭のスーパーコンピュータを含む、普通のコンピュータのことです。

「量子計算の古典的検証」とは、量子コンピュータの行なった計算が正しいものであるかを、人間が普通のコンピュータを使って、確かめると言うことです。

　【 ショアのアルゴリズムの場合】

量子コンピュータのアルゴリズムとして有名な素因数分解を行う「ショアのアルゴリズム」の場合でしたら、「量子計算の古典的検証」は簡単です。

入力した数に対して量子コンピュータが出力した素因数を、コンピュータで実際に掛け算を行なって、それが入力したものと一致しているか確かめればいいわけですから。

ただ、量子コンピュータが行う計算の正しさが、コンピュータで簡単にチェックできるとは限りません。

　【 Google IBM論争の場合】

2019年のGoogleの量子優越性実証実験についての、GoogleとIBMの論争は、直接的には、50数個のqubitを持つ量子コンピュータの「古典的検証」の手法をめぐるものでした。

Googleは、検証にはスーパー・コンピュータを使っても「一万年」かかるとしたのに対して、IBMはやり方を工夫すれば、「二日半」で検証できると主張しました。

IBMは、現在、400 qubitの量子コンピュータを開発しているといいます。こうしたマシンでの「量子計算」の「古典的検証」は、かつて IBMがGoogleに対して主張したような手法で、高速化できるのでしょうか？　

それは、不可能です。

 【 ファインマンの場合】

量子コンピュータのアイデアは、ファインマンの古典的なコンピュータ（スーパーコンピュータを含む普通のコンピュータのことです）では、量子の法則に従う自然をシミレートできないという問題意識から始まりました。

　「だから、量子の法則に従う量子コンピュータを作ろう！」

そもそも、量子コンピュータは、普通のコンピュータでシミレートできない計算をするものとして考えられていました。

　【「量子計算の古典的検証問題」とは？】

一方で、普通のコンピュータにない量子コンピュータの能力に期待しながら、他方では、その成果を普通のコンピュータを通じて、人間が利用できると考えているわけです。

「量子コンピュータ」対「古典コンピュータ＋人間」の対比で言うと前者と後者の計算能力は明らかに異なっています。普通のコンピュータと同様に、人間の能力は、「古典的」なものであることに、注意してください。

「量子計算の古典的検証問題」というのは、この問題を、原理的にキチンと考えようということです。

　「量子計算の古典的検証は可能である」
　　　　　あるいは
　「量子計算の古典的検証は不可能である」

直観的には、二つの陣営の能力差が大きすぎて、「量子計算の古典的検証」は不可能に思えます。

　【「量子計算の古典的検証問題」の現実的・実践的意味 】

それでは、現在のものより、さらに大きな量子コンピュータが完成した時、我々は、それが正しく動作していることをチェックする方法も、その量子コンピュータが行った計算が正しいのかの検証も、原理的には存在しないということになります。

もしも、将来、量子コンピュータの利用が進むなら、おそらくそれはクラウド上の量子コンピュータに、みながアクセスする形になると思うのですが、その時、量子コンピュータに成りすました偽の量子コンピュータが出現した時、それを偽物と見破る方法はないのでしょうか？

逆に、もしも、「量子コンピュータなんか信じない」という人が存在したら、その人に、量子コンピュータのパワーを納得させる方法はあるのでしょうか？

　【 「量子計算の古典的検証問題」の解決 -- Urmila Mahadevの登場 -- 】

「量子計算の古典的検証問題」は、2004年にGottesmanによって定式化されたと言われています。はやくから、問題は認識されていて、活発に研究されてきました。

ただ、この問題が解決されたのは最近のことです。彗星のように登場した若い大学院生 Urmila Mahadev によってこの問題は、肯定的に解決されたのです。

　「量子計算の古典的検証は可能である !」

量子コンピュータにとっても人間にとっても意味のある、とても大事な発見でした。

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

「「量子計算の古典的検証」問題とは何か？」を公開しました。

https://youtu.be/Cyv3ZwhjwYA?list=PLQIrJ0f9gMcOQHQ6KmWuUxuRZkHT-2gZ-

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

blog：「量子計算の古典的検証」問題とは何か？」　https://maruyama097.blogspot.com/2022/11/blog-post_12.html

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

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