量子超越性
一部の研究者は、「超越性(supremacy)」という言葉が白人至上主義(White supremacy)の人種差別的な信念を想起させるため「量子超越性」と言う言葉を使用すべきではないと主張している。 ネイチャーに掲載された13人の研究者によって署名された解説は、代わりに「量子優位性(quantum advantage)」と言う言葉を使用すべきであると主張し、議論を呼んだ。 カリフォルニア工科大学の理論物理学の教授でこの用語を作ったジョン・プレスキルは、「量子コンピューターが古典的なコンピューターではできないタスクを、それが役に立つか否かにかかわらず、できるようになる時点を表すために『量子超越性』と言う言葉を作った。 この新しい言葉で、我々が今、量子物理の原理に基づく情報技術が優位となる特別な時代にいることを強調したかった」。彼はさらに「他のいくつかの可能性を考慮したが、採用しなかった。量子超越性が私が伝えたいポイントを最もよく捕らえていたので決めた。 1つの選択肢は『量子優位性』で、これも現在広く使用されている。 しかし、私にとって、『優位性』には『超越性』ほどのパンチがない。 競馬では鼻で勝っても優位だが、量子コンピュータの速度は、特定のタスクについて、古典的なコンピュータの速度を大幅に上回る」。
ショアのアルゴリズムは、 nビット整数の素因数分解を O ~ ( n 3 ) {\displaystyle {\tilde {O}}(n^{3})} 時間で行う。これに対して、知られている最善の古典アルゴリズムは 2 O ( n 1 / 3 ) {\displaystyle 2^{O(n^{1/3})}} 時間必要である。また、この問題の複雑さの最良の上界は O ( 2 n / 3 + o ( 1 ) ) {\displaystyle O(2^{n/3+o(1)})} である。このアルゴリズムは整数因数分解に帰着される全ての問題を高速化する。その中には奇数オーダーの可換体上の行列群のメンバーシップ問題が含まれる。
このアルゴリズムは、 量子コンピューティングにとって実用的にも歴史的にも重要である。古典コンピュータでは解くことの出来ないと信じられている現実の問題に対して提案された、最初の多項式時間量子アルゴリズムである。つまり、今日合理的に信じられている暗号化プロトコルであるRSAが安全であるという仮定の下で、このアルゴリズムは超多項式の高速化を実現する。
例え非常に大きな数の場合でも、因数分解は乗算するだけで従来のコンピューターですばやくチェックできるため、因数分解は他の量子優位性の提案よりも利点がある。ただし、Shorのアルゴリズムを大きな数に対して実装することは、現在の技術では不可能なため、優位性を実証するための戦略として追求されていない。