論文の概要: Improved Circuit Lower Bounds and Quantum-Classical Separations
- arxiv url: http://arxiv.org/abs/2408.16406v2
- Date: Tue, 5 Nov 2024 00:28:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-08 04:19:50.119388
- Title: Improved Circuit Lower Bounds and Quantum-Classical Separations
- Title（参考訳）: 回路下界の改善と量子古典分離
- Authors: Sabee Grewal, Vinayak M. Kumar,
- Abstract要約: 我々は,GC0が指数サイズのTC0回路を必要とする場合でも,パラメータが失われることなく,AC0がGC0へ持ち上げることを示す。
応用として、Majorityは2Omega(n1/2(d-1))$の深さd GC0[p]回路を必要とすることを証明し、AC0[p]の最先端の下位境界と一致する。
また、ENPは指数サイズ0回路を必要とする(全 m に対して GCC0[m] の結合)。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Kumar used a switching lemma to prove exponential-size lower bounds for a circuit class GC^0 that not only contains AC^0 but can--with a single gate--compute functions that require exponential-size TC^0 circuits. His main result was that switching-lemma lower bounds for AC^0 lift to GC^0 with no loss in parameters, even though GC^0 requires exponential-size TC^0 circuits. Informally, GC^0 is AC^0 with unbounded-fan-in gates that behave arbitrarily inside a sufficiently small Hamming ball but must be constant outside it. We show that polynomial-method lower bounds for AC^0[p] lift to GC^0[p] with no loss in parameters, complementing Kumar's result for GC^0 and the switching lemma. As an application, we prove Majority requires depth-d GC^0[p] circuits of size $2^{\Omega(n^{1/2(d-1)})}$, matching the state-of-the-art lower bounds for AC^0[p]. We also show that E^NP requires exponential-size GCC^0 circuits (the union of GC^0[m] for all m), extending the result of Williams. It is striking that the switching lemma, polynomial method, and algorithmic method all generalize to GC^0-related classes, with the first two methods doing so without any loss. We also establish the strongest known unconditional separations between quantum and classical circuits: 1. There's an oracle relative to which BQP is not contained in the class of languages decidable by uniform families of size-$2^{n^{O(1)}}$ GC^0 circuits, generalizing Raz and Tal's relativized separation of BQP from the polynomial hierarchy. 2. There's a search problem that QNC^0 circuits can solve but average-case hard for exponential-size GC^0 circuits. 3. There's a search problem that QNC^0/qpoly circuits can solve but average-case hard for exponential-size GC^0[p] circuits. 4. There's an interactive problem that QNC^0 circuits can solve but exponential-size GC^0[p] circuits cannot.
- Abstract（参考訳）: Kumar は AC^0 だけでなく、指数サイズの TC^0 回路を必要とする単一のゲート演算関数を持つ回路クラス GC^0 に対して指数サイズの下界を証明するためにスイッチング補題を使用した。
主な結果は、GC^0が指数サイズのTC^0回路を必要とするにもかかわらず、パラメータが失われることなくAC^0リフトをGC^0に切り替えることである。
直交的に、GC^0 は AC^0 であり、十分に小さなハミング球の内部で任意に振る舞う非有界ファンインゲートを持つ。
本稿では,AC^0[p]リフトからGC^0[p]リフトへの多項式-メソッド下界をパラメータの損失なく示し,KumarのGC^0とスイッチング補間結果を補完する。
応用として、Majorityは270Omega(n^{1/2(d-1)})}$の深さd GC^0[p]回路を必要とすることを証明し、AC^0[p]の最先端下界と一致する。
また、E^NP は指数サイズの GCC^0 回路(すべての m に対して GC^0[m] の結合)を必要とすることを示し、ウィリアムズの結果を拡張した。
スイッチング補題、多項式法、アルゴリズム法はすべてGC^0関連クラスに一般化され、最初の2つのメソッドは損失を伴わない。
1) BQP が多項式階層から Rz と Tal の相対化された BQP の分離を一般化し、サイズが 2^{n^{O(1)}}$ GC^0 の均一な族で決定できる言語群に含まれないオラクルが存在する。
2) 指数型GC^0回路ではQNC^0回路は解けるが, 平均ケースハードは難しい。
3) QNC^0/qpoly回路は, 指数型GC^0[p]回路では, 平均ケースハードで解くことができる。
4) QNC^0 回路では解けるが指数サイズの GC^0[p] 回路では解けない。
関連論文リスト
- 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) - On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。
クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文 参考訳（メタデータ） (2024-08-15T17:09:08Z) - A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
CFD問題を解決するための現在の量子アルゴリズムは、単一の量子回路と、場合によっては格子ベースの方法を用いる。
量子格子ボルツマン法(QLBM)を用いた新しい多重回路アルゴリズムを提案する。
この問題は2次元ナビエ・ストークス方程式の流動関数-渦性定式化として鋳造され、2次元蓋駆動キャビティフローで検証および試験された。
論文 参考訳（メタデータ） (2024-01-20T15:32:01Z) - On the Pauli Spectrum of QAC0 [2.3436632098950456]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々は新しい回路の低境界と学習結果を応用として得る。
論文 参考訳（メタデータ） (2023-11-16T07:25:06Z) - Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
北エフの量子二重モデルは有限群$G$に基づく。
本稿では, (a) 基底状態の生成, (b) 任意の距離で分離されたエノン対の生成, (c) 非破壊的トポロジカル電荷測定のための量子回路について述べる。
論文 参考訳（メタデータ） (2022-05-04T08:10:36Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳（メタデータ） (2021-08-10T15:00: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) - Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
本稿では量子回路マッピングQXXとその機械学習バージョンQXX-MLPを紹介する。
後者は、レイアウトされた回路の深さが小さくなるように最適なQXXパラメータ値を自動的に推論する。
近似を用いてレイアウト法を学習可能な経験的証拠を提示する。
論文 参考訳（メタデータ） (2020-07-29T05:26:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。