量子超越性

量子超越性について

量子コンピューティングの分野において「量子超越性」という概念は、量子デバイスが古典コンピュータでは実用的な時間内に解決できない問題を解く能力を持つことを証明するものです。この定義は、問題がどれほど有用であるかにかかわらず成立します。これに対し、「量子優位性」とは、量子コンピュータが古典コンピュータよりも速く問題を解決できることを表します。

量子超越性の実現には、まず高性能な量子コンピュータの構築が求められ、次に古典アルゴリズムに対して超多項式的な速度向上が可能な問題を見つけ出す必要があります。この用語は、元々ジョン・プレスキルによって知られるようになりましたが、その背景にはユーリ・マニンとリチャード・ファインマンの初期の量子計算に関する提案が存在しています。

量子優位性の実証例

量子優位性を実証するために、アーロンソンとアルヒポフが提案したボソンサンプリングの方法や、D-Waveの特殊なクラスターに関連する問題、ランダム量子回路の出力をサンプリングする手法などが挙げられます。また、素因数分解のように、合理的な計算仮定に基づいて古典コンピュータでは困難とされる問題もあります。

例えば、Googleは、49個の超伝導量子ビットを用いて、2017年までに量子優位性を確認する計画を発表しました。さらに、2018年には、NASAとの提携を通じて量子プロセッサでの実験を行い、古典シミュレーションと比較することで量子超越性を確認しようとしました。

計算の複雑さ

計算複雑性理論は、問題解決に必要なリソースが入力サイズに対してどのように増加するかを考察します。量子計算の複雑性理論は、実際の量子コンピュータの構築が難しいことや、デコヒーレンス、ノイズの影響などを必ずしも考慮しない理論的な議論を展開します。この理論において、量子コンピュータは全ての古典的なアルゴリズムをシミュレートできるため、量子優位性の実現可能性が検討されます。

BQP（有界誤差量子多項式時間）というクラスは、量子コンピュータが多項式時間で解決できる決定問題の集合を指します。この関係性は未解決な問題を含んでいますが、量子優位性を示すためには、古典コンピュータでは実行できないことの証明が必要です。

実証のための提案

量子計算の優位性を実証するためには、以下の条件が必要です：明確な計算問題、対応する量子アルゴリズム、最善の古典アルゴリズムとの比較、及び従来のアルゴリズムが改善されないという仮定に基づく議論です。

ショアのアルゴリズムやボソンサンプリング、ランダム量子回路のサンプリングといった技術も、量子超越性を実証する有力な手段として注目されています。

懐疑論と論争

量子コンピュータはデコヒーレンスやノイズの影響を受けやすく、これらが障害になる可能性があります。量子エラー訂正が問題解決のための鍵とされますが、実際のエラー率に関する見解には異論もあります。また、量子優位性の実現に対する研究成果として、古典計算の進展があり、これが量子アルゴリズムの優位性を否定する可能性も示唆されています。

「量子超越性」という用語についても論争があり、一部の研究者からは、その言葉が持つ人種的な連想への配慮から用語の変更が提唱されています。これもまた、量子計算に関連する現在の議論や進展を反映していると言えるでしょう。

もう一度検索