論文の概要: Forrelation is Extremally Hard

• arxiv url: http://arxiv.org/abs/2508.02514v1
• Date: Mon, 04 Aug 2025 15:19:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 18:25:22.401516
• Title: Forrelation is Extremally Hard
• Title（参考訳）: フォーレレーションは極端に硬い
• Authors: Uma Girish, Rocco Servedio,
• Abstract要約: フォルレレーション問題(Forrelation problem)は、量子能力と古典的能力の指数的分離を示す中心的な問題である。 この問題を1つの量子クエリと成功確率1で解くことができるが、$tildeOmegaleft (2n/4right)$ classical randomized queryが必要である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to $n$-bit Boolean functions $f$ and $g$, the goal is to estimate the Forrelation function $\mathrm{forr}(f,g)$, which measures the correlation between $g$ and the Fourier transform of $f$. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely $(f,g)$ with $\mathrm{forr}(f,g)=1$ and $\mathrm{forr}(f,g)=-1$. We show that this problem can be solved with one quantum query and success probability one, yet requires $\tilde{\Omega}\left(2^{n/4}\right)$ classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs $f,g$ are computable by small classical circuits and show classical hardness under cryptographic assumptions.
• Abstract（参考訳）: フォルレレーション問題(Forrelation problem)は、量子能力と古典的能力の指数的分離を示す中心的な問題である。 この問題において、$n$-bit Boolean 関数 $f$ と $g$ へのクエリアクセスが与えられた場合、ゴールは Forrelation 関数 $\mathrm{forr}(f,g)$ を推定することであり、$g$ と $f$ のフーリエ変換の間の相関を測ることである。 この研究では、以前の解析的アプローチとは対照的に、Forrelation問題に関する新しい線形代数的視点を提供する。 Forrelation 問題と曲がったブール関数の接続を確立し、この接続を通じて Forrelation 問題の極端バージョンを分析し、Forrelation の極端インスタンス、すなわち $(f,g)$ と $\mathrm{forr}(f,g)= 1$ と $\mathrm{forr}(f,g)= 1$ を区別する。 この問題は1つの量子クエリと1つの成功確率で解けるが、わずか3分の1の確率を持つアルゴリズムであっても、$\tilde{\Omega}\left(2^{n/4}\right)$ classical randomized queryが必要であり、1つの正確な量子クエリの驚くべきパワーを強調している。 また、この問題の制限された変種について研究し、$f,g$は小さな古典回路で計算可能であり、暗号的仮定の下で古典的な硬さを示す。

関連論文リスト

• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Quantum advantage in zero-error function computation with side information [10.0060346233449]
  本稿では,サイド情報を用いたゼロエラー関数計算の問題点について考察する。 Alice and Bob has correlation source $X,Y$ with joint p.m.f. $p_XY(cdot, cdot)$. Bob want to compute $f(X,Y)$ with zero error。
  論文  参考訳（メタデータ） (2024-02-02T16:41:36Z)
• Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization [51.533164528799084]
  小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。 関数評価がノイズである場合でも,このパターンは真であることがわかった。
  論文  参考訳（メタデータ） (2024-01-11T07:45:09Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Feature Cross Search via Submodular Optimization [58.15569071608769]
  機能工学の基本的な基礎として機能横断探索について研究する。 この問題に対して単純なgreedy $(1-1/e)$-approximationアルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2021-07-05T16:58:31Z)
• Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra [3.2498534294827044]
  我々は、Forrelation値を得るために量子アルゴリズムを再検討する。 屈曲双対性に基づく約束問題を含む既存の2次元フォルレレーションの定式化を導入する。 線形関数の重ね合わせで量子アルゴリズムを微調整し、相互相関サンプリング技術を得る。
  論文  参考訳（メタデータ） (2021-04-25T17:13:18Z)
• Classical algorithms for Forrelation [2.624902795082451]
  1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。 この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。 グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
  論文  参考訳（メタデータ） (2021-02-13T17:25:41Z)
• $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity [3.4984289152418753]
  我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。 我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
  論文  参考訳（メタデータ） (2020-08-16T21:26:46Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Lower Bounds for XOR of Forrelations [7.510385608531827]
  我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。 また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:05:09Z)
• Towards Optimal Separations between Quantum and Randomized Query Complexities [0.30458514384586394]
  入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。 任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
  論文  参考訳（メタデータ） (2019-12-29T01:42:31Z)

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

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