Fugu-MT 論文翻訳(概要): 2-Fold Forrelation is in QAC$^0$

論文の概要: 2-Fold Forrelation is in QAC$^0$

arxiv url: http://arxiv.org/abs/2609.07060v1
Date: Mon, 07 Sep 2026 05:31:45 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-12 01:46:27.519693
Title: 2-Fold Forrelation is in QAC$^0$
Title（参考訳）: 2-Fold ForrelationはQAC$^0$である
Abstract要約: 本稿では,QAC$0$の回路を用いて,逆多元性約束ギャップを持つ2次元のForrelationを有界誤差で解くことができることを示す。
参考スコア（独自算出の注目度）: 0.2876637469655382
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC$^0$ circuits. Unlike the standard oracle-based Forrelation algorithm, our circuits receive the input explicitly, in the same form as the AC$^0$ circuits against which Forrelation is known to be hard. At constant gap, this yields a natural promise-problem separation between QAC$^0$ and AC$^0$.
Abstract（参考訳）: 本研究では,多項式サイズQAC$^0$回路を用いて,逆多元性約束ギャップを持つ2次元フォルレレーションを有界誤差で解くことができることを示す。標準的なオラクルベースのForrelationアルゴリズムとは異なり、我々の回路はForrelationが困難であることが知られているAC$^0$回路と同じ形で入力を明示的に受信する。一定のギャップにおいて、これは QAC$^0$ と AC$^0$ を自然に分離する。

関連論文リスト

One Gate at a Time: Complexity Growth in Random Quantum Circuits [3.34407072562438]
ランダムなユニタリ回路の誤差回路の複雑さは、時間とともにほぼ線形に増加し、$(T/log T)$となることを示す。これにより、スペクトルギャップとユニタリ設計から派生した以前の下界を$mathrmpoly(n)$の係数で改善する。
論文参考訳（メタデータ） (2026-09-15T16:58:25Z)
Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文参考訳（メタデータ） (2026-03-19T15:53:41Z)
Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
有限状態マルコフ鎖を$n$状態と遷移行列$P$で研究する。すべての非退化モードが実周辺不変部分空間 $mathcalK(P)$ によってキャプチャされ、商空間 $mathbbRn/mathcalK(P) 上の誘導作用素が厳密に収縮し、ユニークな商解が得られることを示す。
論文参考訳（メタデータ） (2026-01-31T02:57:01Z)
Forrelation is Extremally Hard [0.0]
フォルレレーション問題(Forrelation problem)は、量子能力と古典的能力の指数的分離を示す中心的な問題である。この問題を1つの量子クエリと成功確率1で解くことができるが、$tildeOmegaleft (2n/4right)$ classical randomized queryが必要である。
論文参考訳（メタデータ） (2025-08-04T15:19:19Z)
On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文参考訳（メタデータ） (2024-08-15T17:09:08Z)
Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文参考訳（メタデータ） (2023-02-13T22:51:07Z)
Qubit recycling and the path counting problem [0.0]
近年,畳み込み型回路(マトリックス製品状態サンドマルチスケール角化再正規化アンザッツなど)で使用されるキューディットを一元的にリセットできることが示されている。このような回路と局所量子回路の間を補間する量子回路の族に対するこのプロトコルの忠実度を解析する。
論文参考訳（メタデータ） (2023-01-09T23:59:41Z)
Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
北エフの量子二重モデルは有限群$G$に基づく。本稿では, (a) 基底状態の生成, (b) 任意の距離で分離されたエノン対の生成, (c) 非破壊的トポロジカル電荷測定のための量子回路について述べる。
論文参考訳（メタデータ） (2022-05-04T08:10:36Z)
Conditions for realizing one-point interactions from a multi-layer structure model [77.34726150561087]
N$平行な均質層からなるヘテロ構造は、その幅が0に縮まるにつれて、その極限において研究される。問題は一次元で調べられ、シュル・オーディンガー方程式の断片的定数ポテンシャルが与えられる。
論文参考訳（メタデータ） (2021-12-15T22:30:39Z)
Interactive quantum advantage with noisy, shallow Clifford circuits [0.0]
本稿では,Grier と Schaeffer の対話プロトコルに耐雑音性を加えるための戦略を示す。この削減の重要な要素は、古典的なシミュレーションタスクにおける平均ケースの硬さを示すことである。シュミレートするために$oplus$L-hardの量子タスクでさえそうであることを示す。
論文参考訳（メタデータ） (2021-02-13T00:54:45Z)

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