論文の概要: Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle

• arxiv url: http://arxiv.org/abs/2512.03788v1
• Date: Wed, 03 Dec 2025 13:37:50 GMT
• ステータス: 情報取得中
• システム内更新日: 2025-12-04 11:58:37.544974
• Title: Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle
• Title（参考訳）: 最も長いセグメントと最大のエンプティ矩形を探索するための量子アルゴリズム
• Authors: Kamil Khadiev, Vladislav Remidovskii, Timur Bikmullin, Aliya Khadieva,
• Abstract要約: 本稿では, 最大エンプティ正方形問題に対する量子アルゴリズムと, 固定幅$d$ for $ntimes n$-rectangular map の最大エンプティ矩形について述べる。 その問題に対する二次的なスピードアップを得る。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In the paper, we consider the problem of searching for the Largest empty rectangle in a 2D map, and the one-dimensional version of the problem is the problem of searching for the largest empty segment. We present a quantum algorithm for the Largest Empty Square problem and the Largest Empty Rectangle of a fixed width $d$ for $n\times n$-rectangular map. Query complexity of the algorithm is $\tilde{O}(n^{1.5})$ for the square case, and $\tilde{O}(n\sqrt{d})$ for the rectangle with a fixed width $d$ case, respectively. At the same time, the lower bounds for the classical case are $Ω(n^2)$, and $Ω(nd)$, respectively. The Quantum algorithm for the one-dimensional version of the problem has $O(\sqrt{n}\log n\log\log n)$ query complexity. The quantum lower bound for the problem is $Ω(\sqrt{n})$ which is almost equal to the upper bound up to a log factor. The classical lower bound is $Ω(n)$. So, we obtain the quadratic speed-up for the problem.
• Abstract（参考訳）: 本稿では, 2次元写像において最も大きい空長方形を探索する問題を考察し, その1次元バージョンは, 最大の空節を探索する問題である。 固定幅$d$ for $n\times n$-rectangular map の最大エンプティ正方形問題と最大エンプティ矩形に対する量子アルゴリズムを提案する。 アルゴリズムのクエリ複雑性は平方の場合$\tilde{O}(n^{1.5})$、固定幅$d$の場合$\tilde{O}(n\sqrt{d})$である。 同時に、古典的ケースの下位境界は、それぞれ$Ω(n^2)$と$Ω(nd)$である。 問題の1次元バージョンに対する量子アルゴリズムは、$O(\sqrt{n}\log n\log \log n)$クエリ複雑性を持つ。 問題の量子下界は$Ω(\sqrt{n})$であり、これは対数係数までの上界とほぼ等しい。 古典的な下界は$Ω(n)$である。 そこで、この問題に対する2次的なスピードアップを得る。

関連論文リスト

• A Quantum Time-Space Tradeoff for Directed $st$-Connectivity [0.08594140167290097]
  任意の$Sgeq log2(n)$に対して、空間$S$と時間$Tleq 2frac12log(n)log(n/S)+o(log2(n))$を用いてDSTCONの量子アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2025-10-09T16:22:04Z)
• Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
  我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。 最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。 2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
  論文  参考訳（メタデータ） (2024-08-19T21:30:02Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• 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)
• 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)
• 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)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。 本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
  論文  参考訳（メタデータ） (2021-05-18T06:51:11Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language [1.0118253437732931]
  2つの問題の量子クエリ複雑性について検討する。 グリッドのエッジのいくつかが欠落している場合、グリッドグラフ上の2次元の接続問題を考える。 平衡括弧」問題をグリッドに埋め込むことで、有向2Dグリッドに対して$Omega(n1.5-epsilon)$、無向2Dグリッドに対して$Omega(n2-epsilon)$の低い境界を示す。
  論文  参考訳（メタデータ） (2020-07-06T09:51:41Z)

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

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