浅い回路による量子優位性

量子効果は情報処理能力を高め、特定の計算問題の解決を迅速化する可能性があります。量子優位性が特定の状況において厳密に証明できるか、近未来のデバイスを用いて実験的に示されるかは、現在進行中の議論の主題です。我々は、一定の時間内に実行される並列量子アルゴリズムが、その古典的対応物よりも厳密に強力であることを示しています；これらは、二次二項型に関連する特定の線形代数問題の解決において、証明可能に優れています。我々の研究は計算における量子優位性の無条件な証明を提供し、その起源を同時に特定します：それは量子の非局所性の結果です。提案された量子アルゴリズムは、隣接ゲートを持つ定深度の量子回路のみを必要とするため、近い将来の実験的実現の適切な候補です。