論文の概要: Improved Lower Bounds for QAC0

• arxiv url: http://arxiv.org/abs/2512.14643v1
• Date: Tue, 16 Dec 2025 17:59:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-17 16:49:26.822901
• Title: Improved Lower Bounds for QAC0
• Title（参考訳）: QAC0における下界の改善
• Authors: Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, John Wright,
• Abstract要約: AAC$0$の回路をAC$0$で古典的にシミュレートする新しい手法を提案する。 我々は量子回路の出力要求を1ビットに緩和し、これまでの最良境界であるローゼンタールよりも2$の値が強い。 我々の証明技術は、本質的に古典的な決定問題に対して、定数深度量子回路は必ずしも古典的な量子回路よりも多くの電力を提供するとは限らないことを示唆している。
• 参考スコア（独自算出の注目度）: 1.4609117117519856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we establish the strongest known lower bounds against QAC$^0$, while allowing its full power of polynomially many ancillae and gates. Our two main results show that: (1) Depth 3 QAC$^0$ circuits cannot compute PARITY regardless of size, and require at least $Ω(\exp(\sqrt{n}))$ many gates to compute MAJORITY. (2) Depth 2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage in depth $2$, regardless of size. We present new techniques for simulating certain QAC$^0$ circuits classically in AC$^0$ to obtain our depth $3$ lower bounds. In these results, we relax the output requirement of the quantum circuit to a single bit (i.e., no restrictions on input preservation/reversible computation), making our depth $2$ approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC$^0$ circuits, which can compute PARITY exactly in depth $2$ using exponential size. Our proof techniques further suggest that, for inherently classical decision problems, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth $2$ QAC$^0$ circuits, regardless of size, cannot exactly synthesize an $n$-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth $2$ exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound).
• Abstract（参考訳）: 本研究では,QAC$^0$に対して既知の最強の下界を確立するとともに,多項式的に多くのアンシラとゲートのフルパワーを実現する。 1) QAC$^0$回路はサイズに関わらずPARITYを計算できず、少なくとも$Ω(\exp(\sqrt{n}))$多くのゲートでMAJORITYを計算する必要がある。 2) 深さ2回路は, 大きさに関わらず, 高影響ブール関数(例えばPARITY)を非無視的優位性で近似することはできない。 我々は、AC$^0$の回路を古典的にシミュレーションし、その深さを3ドル下限とする新しい手法を提案する。 これらの結果から、量子回路の出力要求を1ビットに緩和し(すなわち、入力保存/可逆計算の制限がない)、この深さ2$近似を前回のRosenhal(2021)の最高値よりも強くする。 これにより、従来のAC$^0$回路と自然に比較できるようになり、指数サイズを用いてPARITYを正確に2ドルで計算できる。 我々の証明技術は、本質的に古典的な決定問題に対して、定数深度量子回路は必ずしも古典的な量子回路よりも多くの電力を提供するとは限らないことを示唆している。 3つ目の結果は、深さ2$QAC$^0$回路は、サイズに関係なく、正確に$n$ターゲットのネコマタ状態(合成がPARITYの計算に直接関係している状態)を合成できないことを示している。 これは、ネコマタ (Nekomata) を近似するために、Rosenthal (2021) の2ドルの指数関数サイズ上界(英語版)を補完する(これは唯一知られている定数深さPARITY上界のサブ回路として用いられる)。

関連論文リスト

• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Lower T-count with faster algorithms [2.488003578430483]
  低実行時間で効率的な$T$-countを提案することで、$T$-count削減問題に寄与する。 様々な量子回路において,現在最高のT$カウント還元アルゴリズムであるTODDの複雑さを大幅に改善する。 我々は,さらに複雑さの低い別のアルゴリズムを提案し,評価されたほとんどの量子回路の最先端技術よりも高いあるいは等しいT$カウントを実現する。
  論文  参考訳（メタデータ） (2024-07-11T17:31:20Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• On the Pauli Spectrum of QAC0 [2.3436632098950456]
  我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。 我々は新しい回路の低境界と学習結果を応用として得る。
  論文  参考訳（メタデータ） (2023-11-16T07:25:06Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• 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)
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates [0.0]
  ply(t)cdot n1/D$-depth local random quantum circuits with two qudit Near-ighbor gates are almost $t$-designs in various measures。 また,異なるモデルを用いた深度O(log(n)loglog(n)において,反濃縮が可能であることを証明した。
  論文  参考訳（メタデータ） (2018-09-18T22:28:15Z)

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

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