論文の概要: Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem

• arxiv url: http://arxiv.org/abs/2609.05812v1
• Date: Sat, 05 Sep 2026 02:12:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-12 12:38:33.819962
• Title: Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem
• Title（参考訳）: 構成対角ラムゼー理論のための量子クエリアルゴリズム
• Abstract要約: 構成的対角問題であるラムゼー問題は、ラムゼーの定理によって保証される順序の斜めあるいは独立な集合に対して、$N$頂点グラフへの隣接視線アクセスを与えられることを要求する。 各$Kge2$と$Nge4K-1$に対して、エラー確率が最大$$$のエッジクエリを$O!left (2K Klogfrac Kright)を使って、$K$セットを見つけて検証する有界エラー量子アルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 2.895030292351388
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\!\left(2^K K\log\frac Kη\right)$ edge queries with failure probability at most $η$. At the Ramsey scale $N=2^n$, this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $Ω(N^{1/12})$ quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $Ω(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$. On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
• Abstract（参考訳）: 構成的対角問題であるラムゼー問題は、ラムゼーの定理によって保証される順序の斜めあるいは独立な集合に対して、$N$頂点グラフへの隣接視線アクセスを与えられることを要求する。 我々は、すべての$K\ge2$と$N\ge4^{K-1}$に対して、$O\!を使って同質な$K$-setを見つけて検証する有界エラー量子アルゴリズムを与える。 \left(2^K K\log\frac Kη\right)$ edge query with failure probability at most $η$。 ラムゼースケール $N=2^n$ において、これは$O(\sqrt N\log N\log N\log(\log N/η))$クエリを使用して、次数$\lfloor n/2\rfloor+1$ の同次集合となり、明示的な古典的再帰に関する$O(N)$クエリを改善し、私たちの知る限り、ラムゼー関係に対する最初のサブ線形最悪のケースアルゴリズムを与える。 また、衝突発見による還元により、$Ω(N^{1/12})$の量子下界も導出する。 このアルゴリズムは暗黙の候補集合上で構成的再帰を実行する。 各集合は、隣接制約の短い結合で表され、キャップ付き未知解量子探索を用いてサンプリングされ、スケールアウェア濃度スケジュールは、より深い集合をサンプリングするコストの増大と推定精度のバランスをとる。 我々は、上界を$Ω(N^{1-1/\sqrt2})$ランダム化された下界で補う。 この分布では、グリーディ量子探索は$\widetilde O(N^{1/4})$クエリのみを使用し、ランダムグラフ上のラムゼー探索の証明可能な多項式量子スピードアップを与える。 また、推定自由サイズバイアス付き再帰を与え、それを固定数のエッジカラーに拡張する。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• A Grover-compatible manifold optimization algorithm for quantum search [17.013842168748127]
  グロバーのアルゴリズムは、非構造化探索問題に対して2次高速化を提供する基本量子アルゴリズムである。 我々はGroverのアルゴリズムがGroverのアルゴリズムによって達成された$O(qrstN)$のスピードアップと一致することを示す。
  論文  参考訳（メタデータ） (2025-12-09T10:01:55Z)
• Quantum phase discrimination with applications to quantum search on graphs [0.0]
  本稿では,この課題に対して量子位相判別(QPD)という量子アルゴリズムを提案する。 QPDを用いることで、Li と Zur が提案するパスフィニングアルゴリズムのクエリ複雑性を低減できる。 グラフ上の量子探索に2つの応用を提案する。
  論文  参考訳（メタデータ） (2025-04-21T16:06:43Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Quantum speedups for linear programming via interior point methods [1.8434042562191815]
  本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。 我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
  論文  参考訳（メタデータ） (2023-11-06T16:00:07Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。 我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。 クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-25T15:32:37Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• No quantum speedup over gradient descent for non-smooth convex optimization [22.16973542453584]
  ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。 私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。 下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
  論文  参考訳（メタデータ） (2020-10-05T06:32:47Z)
• 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)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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