量子超越性
任意のランダム量子回路をシミュレートするための最善のアルゴリズムの実行時間は、 量子ビット数に応じて指数関数的に増加する。あるグループは、およそ50量子ビットがあれば量子超越性を実証するのに十分であると推定した。Googleは、49 量子ビットチップを構築して、現在の古典的なコンピューターが妥当な時間内にアクセスできない確率分布を作ることにより、2017年末までに量子優位性を実証する意向を発表した。当時時の古典的なスーパーコンピュータで実行されている最大のユニバーサル量子回路シミュレータは、48量子ビットまでシミュレートすることが出来た。しかしその後、特定の種類の回路においては、56量子ビットまでの量子回路がシミュレーション可能となったため、量子優位性を実証するための量子ビット数を増やす必要が生じた。2019年10月23日、Googleは、フィデリティの高い量子論理回路によって作られた「Sycamore」という新しい53量子ビットプロセッサを開発して行った量子優位性実験の結果を、ネイチャーの記事「プログラム可能な超伝導プロセッサを使用した量子優位性」で公開した 。 Googleは彼らのマシンが200秒で目的の計算を実行したと主張し、古典的なアルゴリズムは同じ問題を解決するために世界最速のスーパーコンピューターで10,000年かかると推定した。IBMはこの主張に異議を唱え、従来のアルゴリズムを改良すれば、同じスーパーコンピューターで2日半でその問題を解決できるはずであると述べた。