ノイズのあるQNC⁰を定数深さの有界多項式閾値回路から無条件に分離する

私たちは、Kum23によって最近導入された、制限された多項式閾値関数を計算するゲートを持つ定数深さの回路のクラスを研究します。この回路ファミリーを整数値の次数境界kでパラメータ化された有界多項式閾値回路としてbPTFC⁰kと呼び、これらのクラスと定数深さの量子回路（QNC⁰）との分離を証明する3つの難易度結果を示します。2em - QNC⁰が量子ビット上で確実に解決できる偶数 halving 問題WKS+19は、すべてのk=O(n^(1/(5d)))に対して有界多項式閾値回路bPTFC⁰kに対して平均ケースで困難であることを証明します。2em - 各素数p>2のmod\ pを計算することに基づく新しい関係問題のファミリーを構築し、上記と同じ次数境界パラメータのbPTFC⁰k回路に対して高次元量子システム（`qupits'）上のQNC⁰回路との分離を証明します。2em - 私たちは、この前述の2つの結果がローカル確率的ノイズモデルの下でノイズに対して堅牢であることを証明し、論理的マジック状態を助言として使用する非クリフォードQNC⁰/|T^1/p>回路の耐障害実装を導入します。bPTFC⁰k回路は、特定の多項式閾値関数（PTF）のクラスを計算でき、これらは神経ネットワークの自然なモデルとして機能し、表現力と計算能力を向上させます。さらに、十分に大きなkの値に対して、bPTFC⁰kはTC⁰をサブクラスとして含みます。私たちが克服する主な課題には、古典的な平均ケース下限を確立すること、勝率における量子-古典的ギャップを持つ非局所ゲームを設計すること、量子ビットを超えて高次元に拡張するために必要なノイズ耐性の非クリフォード量子回路を開発することが含まれます。