JSTら、「弱い」量子コンピューターの古典コンピューターに対する優位性を証明

• Tweet
• 

科学技術振興機構（JST）は2018年5月18日、京都大学、東京大学、名古屋大学、NTTと共同で、1量子ビットしか使えないような「弱い」量子コンピューターでも、ある場面では古典コンピューターより高速であることを理論的に証明したと発表した。

量子コンピューターは、現在我々が使っているコンピューター（古典コンピューター）を遥かに凌駕する超高速計算が可能であることが分かっている。しかし、大量の量子ビットで、任意の量子アルゴリズムをエラーなく実行することは遠い未来のことであると考えられている。そこで、小さなサイズに限定して、特定のアルゴリズムのみを走らせることを目標とした「弱い」量子コンピューターにより、古典コンピューターに対する優位性（量子スプレマシー）を示そうとする研究が盛んになっている。

中でも、単一の量子ビットのみを使うone‐clean qubitモデルは、結び目不変量であるJones多項式の計算など、古典コンピューターで効率的に計算する方法が知られていない量を効率的に計算できるとされている。しかし、将来、新たな計算法が発見される可能性もあり、one‐clean qubitモデルの古典に対する優位性があるか否かは、この20年間未解決の問題として残されていた。

研究グループは今回、新たな手法としてNQPというNP（非決定性多項式時間）の量子版を使用。one‐clean qubitモデルで、1量子ビットの測定のみでも古典に対する優位性が得られることを初めて理論的に証明した。また、同方法をほかの弱い量子計算モデルにも応用。それらの量子スプレマシーを、従来より強い計算量理論的基盤で証明することにも成功した。

研究グループは、この成果は量子スプレマシーの実現に向けた理論的基盤を整備するものであると説明。また、今後の量子計算の理論的、実験的研究の発展に大きく寄与することが期待できるとしている。さらに今後は、有用な量子アルゴリズムの開発につなげることも目指すとし、one‐clean qubitモデルを使った高速な量子アルゴリズムの開発も重要な課題だという。

関連リンク

プレスリリース