「弱い」計算能力の量子コンピューターでも、古典コンピューターの性能を上回ることを理論的に証明

＜研究の背景＞

原子や光などのミクロな世界は、量子力学という物理理論に従っています。量子コンピューターとは、その量子力学に従って動作する全く新しいタイプのコンピューターのことです。量子コンピューターは、私たちが現在使っているコンピューター（古典コンピューターと呼ばれています）をはるかに凌駕する計算性能を持つと信じられており、その実現に大きな期待が寄せられています。

どのような量子アルゴリズム^注１）でも走らせることのできる汎用の量子コンピューターを作るのは一つの究極のゴールであり、大学だけでなく、ＩＢＭやＧｏｏｇｌｅなどの企業を含め、世界中で多くの研究者が取り組んでいます。しかしながら、大量の量子ビット^注２）を扱える汎用の量子コンピューターを実現するのはまだ難しく、最近では、汎用ではなく、ある特定の問題に対しては古典コンピューターよりも優れた計算が可能である量子コンピューター（非汎用の量子コンピューター）を開発する研究に興味が持たれています。このように、計算能力の「弱い」非汎用の量子コンピューターで、古典コンピューターに対する優位性を示そうとする研究は「量子スプレマシー」と呼ばれています。

非汎用の量子コンピューターの例として最も古いものに、ｏｎｅ－ｃｌｅａｎ－ｑｕｂｉｔモデルというものがあります。これは、１９９８年に、米国ロスアラモス研究所の研究者により提案されたものであり、当初はＮＭＲ量子コンピューター^注３）の数理モデルとして使われていました。このｏｎｅ－ｃｌｅａｎ－ｑｕｂｉｔモデルは、偏極率の低い量子ビットを用いた量子コンピューターであるため、任意の量子計算を行うことはできませんが、結び目不変量^注４）の計算など特定の問題に限っては、現在の古典のベストのアルゴリズムよりも高速に解くことができることが知られています。この事実は、ｏｎｅ－ｃｌｅａｎ－ｑｕｂｉｔモデルが古典コンピューターよりも強力であることを示唆します。しかしながら、将来より高速な古典アルゴリズムが見つかるかもしれません。したがって、ｏｎｅ－ｃｌｅａｎ－ｑｕｂｉｔモデルが本当に古典コンピューターを凌駕する「量子スプレマシー」を示すのか、ということについては、長年の未解決問題でした。

＜今回の成果と期待できる効果＞

本研究では、今回初めて、このｏｎｅ－ｃｌｅａｎ－ｑｕｂｉｔモデルが、古典コンピューターよりも高速であることを計算量理論に基づいて理論的に証明しました（図）。これにより、上記の長年の未解決問題に解を与えたことになります。複雑な汎用量子コンピューターを実現しなくとも、近い将来に実現できる非汎用量子コンピューターでも古典コンピューターに対する優位性が証明できたことで、今後の量子テクノロジーの応用において重要な役割を果たしていくことが期待されます。とりわけ、最近ＩＢＭがクラウド量子計算のサービスを試験的に開始して話題となりましたが、将来クラウド量子計算が一般化した際には、まずはこのような非汎用の量子計算がクラウド上で行われることになるため、本研究はその理論的基盤をなすものです。

＜参考図＞

＜用語解説＞

注１） 量子アルゴリズム

量子力学に基づいて動作するアルゴリズム。素因数分解や検索など、いくつかの高速なアルゴリズムが見つかっている。

注２） 量子ビット

古典計算では０と１のビットを用いて計算を行うが、量子計算においては、０と１の二つの量子状態（およびその重ね合わせ）を用いて計算を行う。光の偏光や原子の二準位などをもちいて実現することができる。

注３） ＮＭＲ量子コンピューター

ＮＭＲ（Ｎｕｃｌｅａｒ　Ｍａｇｎｅｔｉｃ　Ｒｅｓｏｎａｎｃｅ、核磁気共鳴）を用いた量子計算機。分子のスピンを外場で操作して量子計算を実現する。

注４） 結び目不変量

結び目を特長付ける多項式など。紐を切らずに動かす操作で不変となるような量であり、結び目が同じかどうか判断する指標となる。

＜論文情報＞

＜お問い合わせ先＞