量子超越性
以下は、現在NISQデバイスと呼ばれることが多い現在の技術を使用して、量子計算の優位性を実証するための提案である。そのような提案には、(1)明確に定義された計算上の問題、(2)その問題を解決するための量子アルゴリズム 、(3)最善の古典アルゴリズムとの比較、および(4)合理的な仮定の下では、現在存在する古典アルゴリズムが大幅に改善する見込みがないと言う計算複雑性理論上の議論、が含まれる(そのため、量子アルゴリズムはあらゆる古典アルゴリズムに対して超多項式の高速化を提供する)。