論文の概要: Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points

• arxiv url: http://arxiv.org/abs/2610.16209v1
• Date: Mon, 12 Oct 2026 05:39:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-19 07:00:48.749031
• Title: Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
• Title（参考訳）: Tarski固定点探索のための古典的および量子的クエリ下界のブートストラップ
• Abstract要約: タルスキの不動点問題は、幅$n$の$k$次元格子上の単調写像の固定点を求め、ゲーム理論、経済学、検証に応用できる。 量子下界に対する2つのブートストラッピング定理を証明する。
• 参考スコア（独自算出の注目度）: 31.45779401617503
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Tarski fixed-point problem asks for a fixed point of a monotone map on a $k$-dimensional grid lattice of width $n$ and has applications in game theory, economics, and verification. Substantial gaps remain between the known upper and lower bounds on its quantum query complexity. We prove two hardness bootstrapping theorems for quantum query lower bounds. Starting from a hard instance family whose instances have pair-wise incomparable unique fixed points, and a lower bound established by the nonnegative adversary method, we bootstrap this lower bound by (i) a factor of $Ω(t)$ when the dimension is multiplied by $t$ and the width remains unchanged, and (ii) a factor of $Ω(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $Ω(k\log^2 n)$ lower bound for $k\geq 4$, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $α>0$, there exists a constant $δ(α)>0$ such that $Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})$ whenever $k>n^α$, and in particular, an $Ω(kn^{0.0072})$ lower bound for $k>n^{2/203}$, the first lower bound with simultaneous linear dependence on the dimension and polynomial dependence on the width; and (iii) a superpolynomial lower bound of $(k/\log k)^{Ω(\log k)}$ for exponentially wide grids, where $n=2^{Θ(k)}$. The last result rules out a route to polynomial-time algorithms for simple stochastic games and ARRIVAL through generic polynomial-query black-box Tarski solvers.
• Abstract（参考訳）: タルスキの不動点問題は、幅$n$の$k$次元格子上の単調写像の固定点を求め、ゲーム理論、経済学、検証に応用できる。 量子クエリの複雑さに関する既知の上界と下界の間には、実質的なギャップが残っている。 量子クエリローバウンドに対する2つのハードネスブートストラッピング定理を証明した。 インスタンスがペアワイズで比較不可能なユニークな固定点を持ち、非負の逆法によって確立された下限を持つハードインスタンスファミリから始まり、この下限をブートストラップする。 (i)次元が$t$に乗じて幅が変化しないとき、$Ω(t)$の係数 (ii)幅が$m$に乗じて次元が倍になるとき、$Ω(\log m)$の係数。 これらの定理を適用すると、3つの結果が得られる。 (i)$Ω(k\log^2 n)$ lower bound for $k\geq 4$, 前述した古典的および量子的下界の改善。 (ii) 全ての固定定数$α>0$に対して、$Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})$ Every $k>n^α$, 特に$Ω(kn^{0.0072})$ lower bound for $k>n^{2/203}$, the first lower bound with linear linear dependency on the dimension and polynomial dependent on the width, and and and and the first lower bound。 (iii) 指数的に広い格子に対して$(k/\log k)^{Ω(\log k)}$の超多項式的下界。 最後の結果は、単純な確率ゲームのための多項式時間アルゴリズムと一般的な多項式クエリブラックボックスTarskiソルバによるARRIVALへの経路を規定する。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Exponential lower bounds for low-degree strategies in position-based quantum cryptography [0.764671395172401]
  非局所量子計算 (NLQC) は、2つの遠隔操作者による2部単位のU_AB$の実装に基づいている。 ユニタリな$U_AB$が存在するかどうかを知ることは、大きなオープンな問題である。 このような指数的下界は、位置ベースの量子暗号のセキュリティに不可欠である。
  論文  参考訳（メタデータ） (2026-09-28T16:43:48Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid [31.45779401617503]
  クナスター・タルスキーの不動点定理(Knaster-Tarski fixed-point theorem)は、完備格子上のすべての単調函数が不動点を持つという定理である。 非負スペクトル逆法を用いて、$[n]k$上の単調関数の固定点を求めるために、$(klog n)$量子クエリローバウンドを証明した。
  論文  参考訳（メタデータ） (2026-09-03T13:06:12Z)
• 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)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• 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)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。 量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
  論文  参考訳（メタデータ） (2020-05-18T16:55:08Z)

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

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