論文の概要: Optimal Quantum Algorithms for Ordered Search
- arxiv url: http://arxiv.org/abs/2609.34293v1
- Date: Mon, 28 Sep 2026 04:39:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 22:05:40.169564
- Title: Optimal Quantum Algorithms for Ordered Search
- Title（参考訳）: 順序付き探索のための最適量子アルゴリズム
- Abstract要約: 順序探索のための2つの新しい量子アルゴリズムを示す。
1つは、連続緩和問題から導かれる単純なゼロエラーアルゴリズムである。
もう1つはゼロエラーアルゴリズムの正確な解である。
- 参考スコア（独自算出の注目度）: 1.76179873429447
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Ordered search is the problem of locating a target element in a sorted list of size $n$ using comparison queries. Classically, binary search requires $\lceil \log_2 n\rceil$ queries, which is optimal. Quantum algorithms offer a constant-factor speedup, but the precise constant has been a longstanding open question. We close this gap by exhibiting two new quantum algorithms for ordered search, each using the optimal $\frac{1}π\ln n+o(\log n)$ queries. The first, discovered by Claude Fable 5, is a simple zero-error algorithm derived from a continuum relaxation of the problem. The second, discovered by GPT-5.6-Sol (informed by Claude's zero-error algorithm), is an exact algorithm based on an analytic solution of the polynomial program of Farhi, Goldstone, Gutmann, and Sipser.
- Abstract（参考訳）: 順序付き検索は、比較クエリを使用して、サイズ$n$のソートされたリストにターゲット要素を配置する問題である。
古典的には、バイナリ検索には$\lceil \log_2 n\rceil$クエリが必要です。
量子アルゴリズムは定数要素のスピードアップを提供するが、正確な定数は長い間疑問視されてきた。
順序探索のための2つの新しい量子アルゴリズムを示し、それぞれが最適な$\frac{1}π\ln n+o(\log n)$クエリを使って、このギャップを埋める。
Claude Fable 5によって発見された最初のゼロエラーアルゴリズムは、問題の連続緩和から導かれる単純なゼロエラーアルゴリズムである。
2つ目は GPT-5.6-Sol (Claude's zero-error algorithm) によって発見され、Farhi, Goldstone, Gutmann, Sipser の多項式プログラムの解析解に基づく正確なアルゴリズムである。
関連論文リスト
- Translation-Invariant Quantum Algorithms for Ordered Search are Optimal [1.4249472316161877]
量子コンピュータは定数係数の高速化を達成できるが、正確な量子アルゴリズムでは$log_2n$の最良の係数は$(ln2)/pi approx 0.221$と$/log_2605 approx 0.433$の間にあることが知られている。
論文 参考訳（メタデータ） (2025-03-27T02:08:16Z) - Improved Algorithm and Lower Bound for Variable Time Quantum Search [1.2246649738388389]
変数時間探索は、異なる項目に対するクエリに異なる時間を要する量子探索の形式である。
我々の最初の結果は、複雑さの$O(sqrtTlog n)$で可変時間探索を行う新しい量子アルゴリズムである。
2つ目の結果は、$Omega(sqrtTlog T)$の量子下界である。
論文 参考訳（メタデータ） (2023-02-13T23:24:49Z) - 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) - Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。
提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Second-order Conditional Gradient Sliding [70.88478428882871]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。