論文の概要: Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated

• arxiv url: http://arxiv.org/abs/2604.02793v1
• Date: Fri, 03 Apr 2026 06:59:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-06 17:20:24.36505
• Title: Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
• Title（参考訳）: Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
• Authors: Lucas Gretta, Meghal Gupta, Malvika Raj Joshi,
• Abstract要約: 浅い量子回路を理解する際の大きな未解決問題は、彼らがパリティを計算できるかどうかである。 我々は、AC$0$のセミナルLMN定理の量子アナログを証明した。 古典的な設定とは異なり、フーリエ濃度はQAC$0$のパワーを特徴付ける。
• 参考スコア（独自算出の注目度）: 1.4018975578160688
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major open problem in understanding shallow quantum circuits (QAC$^0$) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC$^0$: any QAC$^0$ circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC$^0$. Thus, proving a quantum analog of the seminal LMN theorem for AC$^0$ is necessary to bound the quantum circuit complexity of PARITY. In the other direction, LMN does not fully capture the limitations of AC$^0$. For example, despite MAJORITY having $99\%$ of its weight on low-degree Fourier coefficients, no AC$^0$ circuit can non-trivially correlate with it. In contrast, we provide a QAC$^0$ circuit that achieves $(1-o(1))$ correlation with MAJORITY, establishing the first average-case decision separation between AC$^0$ and QAC$^0$. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC$^0$. PARITY is also known to be equivalent in QAC$^0$ to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY $\in$ QAC$^0$.
• Abstract（参考訳）: 浅い量子回路(QAC$^0$)を理解する際の大きな未解決問題は、パリティを計算できるかどうかである。 この疑問は、QAC$^0$のフーリエスペクトルのみに関するものであることを示す: QAC$^0$:QAC$^0$におけるPARITYを正確に計算するのに、非無視可能な高レベルフーリエ質量サファイスを持つ任意のQAC$^0$回路。 したがって、 AC$^0$ のセミナル LMN 定理の量子アナログを証明することは、PARITY の量子回路複雑性を束縛するために必要である。 一方、LMN は AC$^0$ の極限を完全には捉えない。 例えば、MAJORITYは低次フーリエ係数に対して99\%$の重量を持つにもかかわらず、AC$^0$の回路はそれと非自明に相関することができない。 対照的に、MAJORITYと(1-o(1))$相関を達成できるQAC$^0$回路を提供し、AC$^0$とQAC$^0$の分離を初めて行う。 古典的な設定とは異なり、フーリエ濃度はQAC$^0$のパワーを主に特徴付ける可能性がある。 PARITY は QAC$^0$ で GHZ 状態を高忠実度に準備するといった本質的に量子的なタスクと等価であることが知られている。 この等価性は、幅広い状態合成タスクに拡張する。 痕跡距離, 忠実度, 相互情報などの既存の指標は, これらの状態を捉えるには不十分であり, フェリニティという新たな尺度を導入することを実証する。 ポリ(n)-重のディック状態のような非無視性のある状態、あるいは導出状態の任意の状態を作成することは、PARITY$\in$ QAC$^0$を意味することを証明している。

関連論文リスト

• Low-degree approximation of QAC$^0$ circuits [0.0]
  パリティ関数はQAC$0$で計算できないことを示す。 また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
  論文  参考訳（メタデータ） (2024-11-01T19:04:13Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• On the Pauli Spectrum of QAC0 [2.3436632098950456]
  我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。 我々は新しい回路の低境界と学習結果を応用として得る。
  論文  参考訳（メタデータ） (2023-11-16T07:25:06Z)
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation [13.810917492304565]
  離散確率分布の特性を推定するための統一量子アルゴリズムフレームワークを提案する。 我々のフレームワークは、$alpha$-R'enyi entropy $H_alpha(p)$を、少なくとも2/3$の確率で加算エラー$epsilon$内で推定する。
  論文  参考訳（メタデータ） (2022-12-03T08:01:55Z)
• 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)
• Bosonic quantum communication across arbitrarily high loss channels [68.58838842613457]
  一般減衰器$Phi_lambda, sigma$はボゾン量子チャネルであり、入力と固定された環境状態を組み合わせることで作用する。 任意の$lambda>0$に対して、適切な単一モード状態 $sigma(lambda)$が存在することを示す。 我々の結果は、チャネルの入力でエネルギー制約を固定しても成り立ち、任意に低い透過率の極限でも一定の速度で量子通信が可能であることを示唆している。
  論文  参考訳（メタデータ） (2020-03-19T16:50:11Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。