「量子計算で出来ること・出来ないこと」

　2019年のVol.74の物理学会誌に、表題の記事が掲載されています（P.98-101）。以前、『量子コンピュータが人工知能を加速する』という本を読みましたが、素人的には、「公開鍵暗号方式での信用取引がヤバい？！」程度の認識しかなく、量子コンピュータに何が出来て何が出来ないのかは、そもそもの仕組みが理解できていないので、まったく歯が立たない記事ではありました。
　たとえば、“ときメモ”で２つに分岐する選択ポイントが１００回出現する場合、唯一のハッピーエンディングの経路探索をするなんて余裕でできると、普通の人は考えると思います（私もそう思っていました）。でも、本記事を読むと、２のｎ乗のｎがそこそこの数であれば、あっという間に指数関数的に膨大な時間が必要になり、上記例の程度の問題すら解けない…ということがわかります。
　古典計算に比べて「速い」と言われる量子計算の、高速性を示す結果には、以下の３つアプローチがあるとの記載を、心得ておきたいと思いました。
１．古典の現在のベストのアルゴリズムと比較して量子のほうが高速であることを示すタイプ
２．サブルーチンを呼ぶ回数を数えた時に量子のほうが古典より少なくて済むことを示すタイプ
３．量子スプレマシー（量子超越性）＝「もし量子計算が古典計算で効率的にシミュレートできたら多項式階層が崩壊すること」を証明するタイプ
　３．の解説は、私には難しすぎてよくわからなかったのですが、将来的に古典のアルゴリズムのアップデートがあるとしても、量子高速性が強力な基盤で証明される、というメリットがあるようです。
　脚注の最後の記載に、日本の現在の研究状況に対する著者の感想がありました。
――海外ではすでに、量子情報というのは一つの確立した物理の一分野として認識されており、多くの教員や研究グループが存在するが、日本ではまだそもそも「量子計算（量子情報）は物理である」という認識すら薄いように見える。――
　「量子コンピューターによる社会変革」というキャッチコピーもネット上で散見されますが、出来ること・出来ないことを、ある程度きちんと把握しておくことは、大事なことかもしれません。