Fugu-MT 論文翻訳(概要): Quantum Data Structure for Range Minimum Query

論文の概要: 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)
A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文参考訳（メタデータ） (2024-06-17T20:54:11Z)
On the exact quantum query complexity of $\ ext{MOD}_m^n$ and $\ ext{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文参考訳（メタデータ） (2023-03-20T08:17:32Z)
Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文参考訳（メタデータ） (2023-02-20T19:11:44Z)
Quantum divide and conquer [6.527258283771695]
Divide-and-conquerフレームワークは、古典的なアルゴリズム設計で広く使われている。 C_Q(n) leq sqrta, C_Q(n/b) + O(Ctextrmaux_Q(n))$$ の類似反復関係を生じる量子分割・量子化フレームワークについて述べる。
論文参考訳（メタデータ） (2022-10-12T17:14:28Z)
Multidimensional Quantum Walks, with Application to $k$-Distinctness [0.5064404027153093]
時間複雑性に対して$widetildeOleft(n3/4-1/4(2k-1)right)の新たな上限を与える。この新しい手法を用いて,$O(n)$クエリと$O(n2)$タイムで溶接木を解く方法を示す。
論文参考訳（メタデータ） (2022-08-29T10:51:56Z)
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)

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