論文の概要: Exponential quantum-classical query separations for cyclic Forrelation

• arxiv url: http://arxiv.org/abs/2610.41694v1
• Date: Fri, 30 Oct 2026 13:01:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.713122
• Title: Exponential quantum-classical query separations for cyclic Forrelation
• Title（参考訳）: 環状フォルレレーションのための指数量子古典的クエリ分離
• Abstract要約: 本稿では, 周期的Forrelationの古典的クエリ複雑性のランダム化について検討する。 非適応的な古典的なクエリの複雑さをほぼ完全に特徴づける。 本結果は,古典計算よりもクエリの利点を体系的に理解するものである。
• 参考スコア（独自算出の注目度）: 10.872863127462717
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of $k$-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given $k$ Boolean functions $f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}$, the goal is to estimate $T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),$ where $D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)$, $H$ is the Hadamard gate, and $N=2^n$. This normalized-trace problem can be solved with $k$ quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of $\widetildeΩ(N^{1-2/k})$. We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even $k\ge 4$, we prove a tight bound of $Θ_k(N^{1-2/k})$ for constant additive error. For odd $k\ge 5$, we obtain a lower bound of $Ω_k(N^{1-2/(k-1)})$ and an upper bound of $O_k(N^{1-2/k})$. Surprisingly, $k=3$ admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the $k$-cycle, leading to the exponent $1-1/\lfloor k/2\rfloor$, rather than the previously conjectured $1-2/k$, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of $Ω(N^{1/4})$ for every $k\ge4$. Although formally close to $k$-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.
• Abstract（参考訳）: 我々は、$k$-Forrelation [AA15, STOC'15; BS21, STOC'21] の巡回類似体である巡回Forrelationのランダム化古典的クエリ複雑性について検討する。 $k$ Boolean function $f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}$を与えられた場合、目標は$T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),$$D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)$, $H$はアダマールゲートであり、$N=2^n$である。 この正規化トレース問題は、DQC1モデルで$k$の量子クエリで解決できる。 古典的なクエリの複雑さは [JLS+26, FOCS'26] に残され、$\widetildeΩ(N^{1-2/k})$の低い境界が予想された。 我々は,非適応型古典的クエリ複雑性のほぼ完全な特徴付けを確立する。 仮に$k\ge 4$ であっても、定数加法誤差に対して$n_k(N^{1-2/k})$ の厳密な境界が証明される。 奇数$k\ge 5$に対して、$Ω_k(N^{1-2/(k-1)})$と$O_k(N^{1-2/k})$の上限を得る。 驚いたことに、$k=3$ は多対数的な非適応的古典的アルゴリズムを認め、この場合の予想を否定する。 これらの結果は予期せぬパリティに依存した構造を示唆している: 非適応的複雑性は$k$-サイクルの独立数によって支配され、フーリエ成長ヒューリスティックによって動機付けられた1-2/k$ではなく、指数1-1/\lfloor k/2\rfloor$へと導かれる。 最後に、適応性を許容すると、すべての$k\ge4$に対して$Ω(N^{1/4})$の低い境界が証明される。 公式には$k$-Forrelationに近いが、巡回構造は古典的な振る舞いと異なるテクニックを必要とする。 我々の下限は隠れシフト衝突構造に基づいており、上限はランダム化サンプリングとサイクル固有条件-モーメント推定から導かれる。 本結果は,古典計算よりもクエリの利点を体系的に理解するものである。

関連論文リスト

• Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples [3.845877724862319]
  我々は、Kirchner and Fouque [KF15] の LWE に対する Wagner/BKW 型アルゴリズムの変種が決定を解き、LWE の秘密を素モジュライ$q=n+o(1)$で検索することを示した。
  論文  参考訳（メタデータ） (2026-10-09T05:58:55Z)
• Quantum Submodular Maximization [14.165444015073307]
  提案アルゴリズムは,O_varepsilon(log n)$クエリのみを用いて,期待される$(1/2-varepsilon)$-approximationを実現する。 対照的に、1/4$を超える固定予測比を達成するような古典的ランダム化アルゴリズムは、$(n/log n)$クエリを必要とする。 我々は、制約のない1/2+varepsilon$を超える比率を達成するために、$exp(varepsilon2n)$クエリの量子下界を証明した。
  論文  参考訳（メタデータ） (2026-10-03T14:51:06Z)
• Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security [2.3865782873384576]
  独立な乱数置換と関連する置換から関数への変換の和について検討する。 我々は,その構成を確率密度で表現し,受容関数で区別する統一されたフーリエ解析処理を行う。
  論文  参考訳（メタデータ） (2026-09-28T15:30:40Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。 格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。 $d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
  論文  参考訳（メタデータ） (2026-04-27T10:23:24Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• $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)

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

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