論文の概要: Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms

• arxiv url: http://arxiv.org/abs/2609.05201v1
• Date: Fri, 04 Sep 2026 14:34:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-07 18:15:24.071779
• Title: Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms
• Title（参考訳）: 完全有界多項式の最適不等式と量子クエリアルゴリズムの極限
• Abstract要約: 完全有界法を用いて量子クエリアルゴリズムのパワーの限界を確立することの問題点を考察する。 我々は、完全有界の異なる概念を含むいくつかの最適機能不等式を証明した。 これらの不等式は、以前の作業を改善する量子クエリアルゴリズムのパワーの制限につながる。
• 参考スコア（独自算出の注目度）: 0.764671395172401
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works. 1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials $p$ of degree $t$ satisfy a root-influence bound, $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2$, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t$. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as $t$-fold forrelation- are block-multilinear polynomials with $\|p\|_{\text{cb}}\leq 1,$ our inequality shows that they satisfy $t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}$. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive. 2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial $p$ defined on $\{-1,1\}^n$ of degree $2t$, the Fourier Growth at the level $2t,$ namely $\|\widehat p_{2t}\|_{\ell_1}$, satisfies $\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}$. This is optimal up to the factor $e$, as witnessed by $2t$-fold forrelation. As quantum query algorithms that make $t$ queries (to the whole input) satisfy $\|p\|_{\text{cb}}\leq 1$, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).
• Abstract（参考訳）: 完全有界多項式法を用いて量子クエリアルゴリズムのパワーに制限を設けることの問題点を考察する。 特に、完全有界多項式の異なる概念を含むいくつかの最適機能不等式を証明する。 これらの不等式は、先行研究を改善する量子クエリアルゴリズムのパワーに対する定理の制限につながる。 1. ブロック-多重線型多項式に対する最適根の影響 以前の研究は、ブロック-多重線型多項式 $p$ of degrees $t$ がルート影響境界 $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2$ を満たすことを示した。 この不等式における最適定数: $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t$。 入力の不整合ブロック(例えば$t$-fold forrelation)を問う量子アルゴリズムの振幅は、$\|p\|_{\text{cb}}\leq 1,$の不等式は、$t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}$を満たすことを示す。 この不等式はアーロンソン・アンバイニスの議論に基づく先行結果よりも効率的な古典的シミュレーションと定性的な改善、すなわちすべての古典的クエリが非適応的であることを証明している。 2.最高レベルの量子クエリアルゴリズムの最適フーリエ成長 次数 2t の$\{-1,1\}^n$ 上で定義されるすべての多項式 $p$ に対して、レベル $2t におけるフーリエ成長、すなわち $\|\widehat p_{2t}\|_{\ell_1}$ は $\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}$ を満たす。 これは2t$-fold forrelationで見られるように、$e$まで最適である。 量子クエリアルゴリズムは$t$クエリを(入力全体に対して)$\|p\|_{\text{cb}}\leq 1$を満たすので、これらのアルゴリズムに対してフーリエ成長バウンドとなり、Girish (STOC, 2026) による質問を部分的に解決する。

関連論文リスト

• Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields [1.4323566945483497]
  有限体上のローレントルムの解数の近似について検討する。 我々の最初の主要な結果は、成功確率1-$で、$widehat(f)$ fulfilling [ |widehatN(f) - N(f)| le varepsilon qn+s/2-]を出力する量子アルゴリズムである。 2つ目の主要な結果として、ランダム時間チューリング還元の下で同じ問題が$#$P-hardになることを示す。
  論文  参考訳（メタデータ） (2026-08-25T00:23:27Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Quantum Algorithms and Lower Bounds for Finite-Sum Optimization [22.076317220348145]
  我々は、複雑性 $tildeObig(n+sqrtd+sqrtell/mubig)$ の量子アルゴリズムを与え、古典的なタイト境界 $tildeThetabig(n+sqrtnell/mubig)$ を改善する。 また、$d$が十分大きいとき、量子下界$tildeOmega(n+n3/4(ell/mu)1/4)$を証明します。
  論文  参考訳（メタデータ） (2024-06-05T07:13:52Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。 本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-28T18:12:54Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• 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)
• Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
  まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。 Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
  論文  参考訳（メタデータ） (2020-08-14T12:17:48Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。 本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
  論文  参考訳（メタデータ） (2020-04-15T06:18:41Z)

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

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