量子超越性

量子コンピューティングにおいて量子超越性 とは、プログラム可能な量子デバイスが、どの様な古典コンピュータでも実用的な時間では解決できない問題を解決できることを（問題の有用性に関係なく）証明することである。それよりも弱い量子優位性 は、量子デバイスが古典コンピュータよりも速く問題を解決できることを表す。量子超越性には概念上、処理能力の高い量子コンピューターを構築するエンジニアリングタスクと、知られている最善の古典アルゴリズムに比べて、その量子コンピュータを用いて超多項式 の高速化ができるような問題を見つける計算複雑性理論上のタスクが含まれる。この用語は元々ジョン・プレスキルによって広められたが、量子コンピューティングの利点、特に量子システムのシミュレーションの概念は、 ユーリ・マニン （1980） およびリチャード・ファインマン （1981）の量子計算の提案にさかのぼる。