論文の概要: Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid

• arxiv url: http://arxiv.org/abs/2609.03802v1
• Date: Thu, 03 Sep 2026 13:06:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-04 18:28:39.064727
• Title: Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid
• Title（参考訳）: 高次元格子上でのタルスキー固定点探索の量子クエリ複雑性
• Abstract要約: クナスター・タルスキーの不動点定理(Knaster-Tarski fixed-point theorem)は、完備格子上のすべての単調函数が不動点を持つという定理である。 非負スペクトル逆法を用いて、$[n]k$上の単調関数の固定点を求めるために、$(klog n)$量子クエリローバウンドを証明した。
• 参考スコア（独自算出の注目度）: 31.45779401617503
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Knaster-Tarski fixed-point theorem states that every monotone function over a complete lattice has a fixed point. Beyond its fundamental role in order theory, the theorem and its algorithmic variants have found broad applications in areas such as economics, game theory, and programming languages. While the query complexity of finding a Tarski fixed point has been extensively studied in classical models, comparatively little is known in the quantum setting. We prove an $Ω(k\log n)$ quantum query lower bound for finding a fixed point of a monotone function on $[n]^k$, using the nonnegative spectral adversary method. In the two extremal regimes $n = 2$ and $k = 1$, our quantum lower bound matches the previous classical lower bounds $Ω(k)$ and $Ω(\log n)$, respectively. For $n, k\geq 2$, our bound improves the best previous classical lower bound when $n < k$ and is within a factor of $\log n / \log k$ compared to the known classical lower bound when $n \geq k$. To construct the adversary matrix, we develop the Tree--Filtration Adversary Method. Besides yielding our lower bound, the method offers a more transparent combinatorial interpretation of the nonnegative spectral adversary method. When the hard instances of a problem admit a tree-like organization and suggest an intuition analogous to classical decision-tree lower bounds, our method provide a promising approach to establishing quantum complexity lower bounds.
• Abstract（参考訳）: クナスター・タルスキーの不動点定理(Knaster-Tarski fixed-point theorem)は、完備格子上のすべての単調函数が不動点を持つという定理である。 順序理論における基本的な役割の他に、定理とそのアルゴリズムの変種は、経済学、ゲーム理論、プログラミング言語などの分野で広く応用されている。 タルスキの不動点を見つけるためのクエリの複雑さは古典的なモデルでは広く研究されているが、量子設定では比較的ほとんど知られていない。 非負スペクトル逆法を用いて、$[n]^k$ 上の単調関数の固定点を求めるために$Ω(k\log n)$量子クエリローバウンドを証明した。 2つの極端状態において、$n = 2$ と $k = 1$ の量子下界は、それぞれ以前の古典的下界の $Ω(k)$ と $Ω(\log n)$ と一致する。 n, k\geq 2$ の場合、我々の境界は$n < k$ のときの最も古い古典的下界を改善し、$n \geq k$ のときの既知の古典的下界よりも$\log n / \log k$ の範囲内である。 逆行列を構成するために,木フィルタ逆法を開発した。 我々の下界を得るのに加えて、この手法は非負のスペクトル逆法をより透明に組み合わせて解釈する。 問題のハードケースが木のような組織を認め、古典的な決定木の下限に類似した直観を示唆すると、我々の手法は量子複雑性の下限を確立するための有望なアプローチを提供する。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。 任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
  論文  参考訳（メタデータ） (2026-07-22T07:41:32Z)
• Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy [4.843542453440025]
  探索問題に対する一方向量子通信の低境界について検討する。 衝突検出のためには、厳密な$(N1/4)$ワンウェイ量子通信を低い境界で証明する。 三角形を見つけるためには、$m$エッジを持つグラフに対して$left(sqrt_Vright)$、$(m)$トライアングル、定数$_E$の1パス量子ストリーミング空間を低い境界で証明する。
  論文  参考訳（メタデータ） (2026-07-09T14:11:09Z)
• Tight Quantum Lower Bound for k-Distinctness [52.10197476419622]
  我々は新しい量子クエリローバウンドフレームワークを導入する。 このフレームワークが入力文字列の等しい要素を見つけるという問題に対してどのように振る舞うかを示す。 特に、k-distinctness問題に対する最初の厳密な量子クエリローバウンドを証明することによって、そのパワーを実証する。
  論文  参考訳（メタデータ） (2026-04-06T19:52:58Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• From Classical to Quantum: Explicit Classical Distributions Achieving Maximal Quantum $f$-Divergence [4.956709222278243]
  最大$f$-分数を達成するような古典的な明示的な状態が与えられ、松本の定理の簡単な証明が可能である。 我々の方法論は特に単純であり、精巧な行列解析機構は必要とせず、基本線型代数のみである。
  論文  参考訳（メタデータ） (2025-01-24T09:06:13Z)
• Better bounds on Grothendieck constants of finite orders [20.068273625719943]
  我々は最近のフランク・ウルフのアプローチを利用して、いくつかのグロタンディーク定数を下限とするよい候補を提供する。 完全証明は難解な二項最適化問題を解くことに依存する。
  論文  参考訳（メタデータ） (2024-09-05T17:53:52Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• 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)
• Quantum algorithms for escaping from saddle points [7.191453718557392]
  本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。 我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。 また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
  論文  参考訳（メタデータ） (2020-07-20T16:42:53Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)

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

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