論文の概要: On the Pauli Spectrum of QAC0
- arxiv url: http://arxiv.org/abs/2311.09631v2
- Date: Fri, 17 Nov 2023 17:47:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-20 11:54:29.290615
- Title: On the Pauli Spectrum of QAC0
- Title（参考訳）: QAC0のパウリスペクトルについて
- Authors: Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, Henry Yuen
- Abstract要約: 我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々はこの予想を、少なくとも$nO(1/d)$補助量子ビットを持つ深さ-d$,-size $mathsfQAC0$回路のクラスで証明する。
我々は新しい回路の低境界と学習結果を応用として得る。
- 参考スコア（独自算出の注目度）: 2.5602836891933074
- 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 -
1/\mathrm{poly}(n))$-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{ac}^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パリティ関数、入力の$(11/\mathrm{poly}(n))$-fraction。
さらに、補助量子ビットが制限された $\mathsf{QAC}^0$ 回路のクラスは準ポリノミカル標本の複雑さで学習できることを示し、$\mathsf{QAC}^0$ 回路に対する最初の学習結果を与える。
より広い意味で、この結果は「ポール解析」技術が量子回路の研究に強力なツールとなる証拠を与える。
関連論文リスト
- Low-degree approximation of QAC$^0$ circuits [0.0]
パリティ関数はQAC$0$で計算できないことを示す。
また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
論文 参考訳（メタデータ） (2024-11-01T19:04:13Z) - On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。
これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
論文 参考訳（メタデータ） (2024-10-09T02:55:57Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - 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 and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - 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) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。