ベールの差分サンプリングによる安定器推定の改善

私たちは、安定器形式に関してさまざまなモデルで量子状態の学習の複雑さを研究し、次の結果を得ました。私たちは、任意のClifford+T回路が計算的に擬似ランダムな量子状態を準備するためにはΩ(n) Tゲートが必要であることを証明します。これは以前に知られていた制約に対する指数的な改善です。この制約は、線形時間量子安全な擬似ランダム関数が存在する場合、漸近的に厳密です。いくつかの安定器状態との忠実度が少なくともτであるn量子ビットの純粋量子状態|ψ⟩が与えられた場合、私たちは忠実度が少なくともτ − εである安定器状態の簡潔な記述を出力するアルゴリズムを提供します。このアルゴリズムはO(n/(ε2τ4))サンプルとexp(O(n/τ4)) / ε2時間を使用します。τが一定の領域では、このアルゴリズムはすべての安定器状態に対する単純なexp(O(n2))-時間のブルートフォースアルゴリズムよりも安定器忠実度を大幅に早く推定します。特にτ > cos2(π/8)の場合、上記のアルゴリズムの修正が多項式時間で実行されることを示します。私たちは安定器状態に対する耐容特性検定アルゴリズムを示します。私たちのすべての結果における基礎的なアルゴリズム的原始はベールの差分サンプリングです。私たちの結果を証明するために、ベールの差分サンプリング、シンプレクティックフーリエ解析、グラフ理論の間の関係を確立および/または強化します。”