ユニタリーハール測度のための反集中およびランダム量子回路への応用

ユニタリーハール測度に対するカーべリー・ライトスタイルの反集中不等式を証明します。それは、ランダムユニタリのエントリーにおける多項式が特定の範囲に入る確率が多項式であることを示すことによって行われます。これを用いて、ランダム量子回路のスクランブリング速度が下限であることを示します。すなわち、すべての入力キュービットは、その光円に触れた任意の出力キュービットに対して、深さに対して少なくとも指数的に小さい影響を持ちます。この新しいスクランブリング速度の下限に対する3つの応用を示しますが、これはハールランダムゲートを持つランダム量子回路に適用されます。-近似ユニタリ設計のための最適な（^-1）深さの下限；制限された深さの回路の深さを計算する多項式時間量子アルゴリズム；回路へのオラクルアクセスを用いて、多項式的に小さいダイヤモンド距離までの対数深さ回路を学習する多項式時間アルゴリズム。最初の深さ下限は、任意のアーキテクチャに対して機能します。後者の2つのアルゴリズムは、任意の幾何学的次元に対して定義されたアーキテクチャに適用され、良好な光円特性を持つ広範なクラスのアーキテクチャに一般化することができます。