論文の概要: On the Pauli Spectrum of QAC0
- arxiv url: http://arxiv.org/abs/2311.09631v4
- Date: Wed, 17 Jul 2024 20:47:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-19 22:00:54.996293
- Title: On the Pauli Spectrum of QAC0
- Title（参考訳）: QAC0のパウリスペクトルについて
- Authors: Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, Henry Yuen,
- Abstract要約: 我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々は新しい回路の低境界と学習結果を応用として得る。
- 参考スコア（独自算出の注目度）: 2.3436632098950456
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The circuit class $\mathsf{QAC}^0$ was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size $\mathsf{QAC}^0$ cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of $\mathsf{QAC}^0$ circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical $\mathsf{AC}^0$ circuits. We conjecture that the Pauli spectrum of $\mathsf{QAC}^0$ circuits satisfies low-degree concentration, in analogy to the famous Linial, Nisan, Mansour theorem on the low-degree Fourier concentration of $\mathsf{AC}^0$ circuits. If true, this conjecture immediately implies that polynomial-size $\mathsf{QAC}^0$ circuits cannot compute parity. We prove this conjecture for the class of depth-$d$, polynomial-size $\mathsf{QAC}^0$ circuits with at most $n^{O(1/d)}$ auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute - the $n$-bit parity function on more than $(\frac{1}{2} + 2^{-\Omega(n^{1/d})})$-fraction of inputs, and - the $n$-bit majority function on more than $(1 - \Omega(n^{-1/2}))$-fraction of inputs. Additionally we show that this class of $\mathsf{QAC}^0$ circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for $\mathsf{QAC}^0$ circuits. More broadly, our results add evidence that "Pauli-analytic" techniques can be a powerful tool in studying quantum circuits.
- Abstract（参考訳）: 回路クラス $\mathsf{QAC}^0$ はムーア (1999) によって、ゲート集合が多ビットトフォリゲートを含む定数深さ量子回路のモデルとして導入された。
そのような回路に対する下界の証明は、量子回路の複雑さにおける長年の挑戦であり、特に多項式サイズの$\mathsf{QAC}^0$がパリティ関数を計算できないことを示すことは、20年以上も未解決の問題のままである。
本研究では、古典的な$\mathsf{QAC}^0$回路のフーリエスペクトルの量子アナログと見なせる$\mathsf{QAC}^0$回路のパウリスペクトルの概念を同定する。
我々は、$\mathsf{QAC}^0$回路のパウリスペクトルが、有名なLinial, Nisan, Mansour定理に類似して、$\mathsf{QAC}^0$回路の低次フーリエ濃度に対する低次濃度を満たすことを予想する。
もし真なら、この予想は直ちに多項式サイズ$\mathsf{QAC}^0$回路がパリティを計算できないことを意味する。
我々は、この予想を、少なくとも$n^{O(1/d)}$補助量子ビットを持つ深さ=d$、多項式サイズ$\mathsf{QAC}^0$回路のクラスで証明する。
この回路のクラスは、$(\frac{1}{2} + 2^{-\Omega(n^{1/d})} 以上の$n$-bitパリティ関数、$(1 - \Omega(n^{-1/2}) 以上の$n$-bitマジョリティ関数。
さらに、補助量子ビットが制限された $\mathsf{QAC}^0$ 回路のクラスは準ポリノミカル標本の複雑さで学習できることを示し、$\mathsf{QAC}^0$ 回路に対する最初の学習結果を与える。
より広範に、我々の結果は、"Pauli-analytic"技術が量子回路の研究において強力なツールであることを示す証拠となる。
関連論文リスト
- The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
量子回路複雑性の主な目的の1つは、量子浅層回路によって解くことができるが、古典的により多くの計算資源を必要とする問題を見つけることである。
我々は古典的回路と量子的定数深さ回路の分離を新たに証明する。
無限大ゲートセットの場合、高次元ヒルベルト空間に対するこれらの量子回路クラスは標準量子ビット実装に何の利点も与えない。
論文 参考訳（メタデータ） (2024-04-28T07:44:27Z) - Parity vs. AC0 with simple quantum preprocessing [0.0]
我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。
私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
論文 参考訳（メタデータ） (2023-11-22T20:27:05Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳（メタデータ） (2021-02-03T09:20:32Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - Bounds on the QAC$^0$ Complexity of Approximating Parity [0.0]
その結果,QAC回路はサイズに関係なくパリティを近似できることがわかった。
QAC回路は1/2 + exp(-o(n/d))$ perroximation of parityを達成するために少なくとも$Omega(n/d)$ multi-qubit gateを必要とする。
論文 参考訳（メタデータ） (2020-08-17T16:51:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。