量子超越性
量子コンピューティングにおいて量子超越性(りょうしちょうえつせい、英: Quantum supremacy)とは、プログラム可能な量子デバイスが、どの様な古典コンピュータでも実用的な時間では解決できない問題を解決できることを(問題の有用性に関係なく)証明することである。それよりも弱い量子優位性 (quantum advantage) は、量子デバイスが古典コンピュータよりも速く問題を解決できることを表す。量子超越性には概念上、処理能力の高い量子コンピューターを構築するエンジニアリングタスクと、知られている最善の古典アルゴリズムに比べて、その量子コンピュータを用いて超多項式 (en:superpolynomial)の高速化ができるような問題を見つける計算複雑性理論上のタスクが含まれる。この用語は元々ジョン・プレスキルによって広められたが、量子コンピューティングの利点、特に量子システムのシミュレーションの概念は、 ユーリ・マニン (1980) およびリチャード・ファインマン (1981)の量子計算の提案にさかのぼる。
量子優位性を実証する提案の例には、 アーロンソン(en:Scott Aaronson)とアルヒポフのボソンサンプリング提案、D-Waveの特殊なフラストレーテッドクラスターループ問題とランダム量子回路の出力のサンプリングが含まれる。
素因数分解と同様に、ランダム量子回路の出力分布をサンプリングすることは、合理的な複雑さの仮定に基づく古典的なコンピュータでは難しいと考えられている。Googleは以前、49の超伝導量子ビットの配列でこの問題を解決することにより、2017年末までに量子優位性を実証する計画を発表した。