論文の概要: Quantum Data Structure for Range Minimum Query

• arxiv url: http://arxiv.org/abs/2601.13195v1
• Date: Mon, 19 Jan 2026 16:19:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:22.968399
• Title: Quantum Data Structure for Range Minimum Query
• Title（参考訳）: 範囲最小クエリのための量子データ構造
• Authors: Qisheng Wang, Zhean Xu, Zhicheng Zhang,
• Abstract要約: RMQクエリとレンジ更新をサポートする量子データ構造を提案する。 我々は、量子ランダムアクセスメモリを使わずに、$k$-minimum発見のための時間効率の量子アルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 30.186099880107964
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given an array $a[1..n]$, the Range Minimum Query (RMQ) problem is to maintain a data structure that supports RMQ queries: given a range $[l, r]$, find the index of the minimum element among $a[l..r]$, i.e., $\operatorname{argmin}_{i \in [l, r]} a[i]$. In this paper, we propose a quantum data structure that supports RMQ queries and range updates, with an optimal time complexity $\widetilde Θ(\sqrt{nq})$ for performing $q = O(n)$ operations without preprocessing, compared to the classical $\widetildeΘ(n+q)$. As an application, we obtain a time-efficient quantum algorithm for $k$-minimum finding without the use of quantum random access memory.
• Abstract（参考訳）: 配列 $a[1.n]$ が与えられた場合、Range Minimum Query (RMQ) 問題は、RMQクエリをサポートするデータ構造を維持することである: 範囲 $[l, r]$ が与えられた場合、$a[l.r]$、すなわち$\operatorname{argmin}_{i \in [l, r]} a[i]$。 本稿では,RMQクエリとレンジ更新をサポートする量子データ構造を提案し,従来の$\widetilde(n+q)$と比較して,$q = O(n)$演算を前処理なしで行うために最適な時間複雑性を持つ。 応用として、量子ランダムアクセスメモリを使わずに、$k$-minimum探索のための時間効率の量子アルゴリズムを得る。

関連論文リスト

• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。 クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。 このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
  論文  参考訳（メタデータ） (2026-01-07T22:07:44Z)
• Quantum Search on Computation Trees [0.0]
  モンタナロ(ToC)によるバックトラック木探索のための量子ウォークアルゴリズムの一般化を示す。 このフレームワークは、変数時間探索、量子分割と圧縮、爆弾クエリアルゴリズムなど、他の多くの量子フレームワークを再定義するための、簡単で便利な方法を提供する。
  論文  参考訳（メタデータ） (2025-05-28T14:35:18Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
  語彙的最小弦回転(lexicographically minimal string rotation, LMSR)は、語彙的順序で弦のすべての回転の中で最小の回転を求める問題である。 LMSRのための$O(n3/4)$量子クエリアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-17T03:13:45Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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