論文の概要: Translation-Invariant Quantum Algorithms for Ordered Search are Optimal
- arxiv url: http://arxiv.org/abs/2503.21090v1
- Date: Thu, 27 Mar 2025 02:08:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-28 12:52:06.022431
- Title: Translation-Invariant Quantum Algorithms for Ordered Search are Optimal
- Title（参考訳）: 順序付き探索のための翻訳不変量子アルゴリズムは最適である
- Authors: Joseph Carolan, Andrew M. Childs, Matt Kovacs-Deak, Luke Schaeffer,
- Abstract要約: 量子コンピュータは定数係数の高速化を達成できるが、正確な量子アルゴリズムでは$log_2n$の最良の係数は$(ln2)/pi approx 0.221$と$/log_2605 approx 0.433$の間にあることが知られている。
我々は、Farhi、Goldstone、Gutmann、Sipserによって導入されたワークスペースを持たない翻訳不変アルゴリズムの特別なクラスを考える。
- 参考スコア（独自算出の注目度）: 1.4249472316161877
- License:
- Abstract: Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses $\lceil \log_{2}{n}\rceil$ queries for a list of length $n$. Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of $\log_{2}{n}$ for exact quantum algorithms is only known to lie between $(\ln{2})/\pi \approx 0.221$ and $4/\log_{2}{605} \approx 0.433$. We consider a special class of translation-invariant algorithms with no workspace, introduced by Farhi, Goldstone, Gutmann, and Sipser, that has been used to find the best known upper bounds. First, we show that any exact, $k$-query quantum algorithm for ordered search can be implemented by a $k$-query algorithm in this special class. Second, we use linear programming to show that the best exact $5$-query quantum algorithm can search a list of length $7265$, giving an ordered search algorithm that asymptotically uses $5 \log_{7265}{n} \approx 0.390 \log_{2}{n}$ quantum queries.
- Abstract（参考訳）: 順序付き検索は、比較クエリを使用して順序付きリスト内のアイテムを見つけるタスクである。
この基本的な問題に対する最も正確な古典的アルゴリズムは、長さ$n$のリストに対して$\lceil \log_{2}{n}\rceil$クエリを使用する。
量子コンピュータは定数係数の高速化が可能であるが、正確な量子アルゴリズムに対して$\log_{2}{n}$の最良の係数は、$(\ln{2})/\pi \approx 0.221$と$/\log_{2}{605} \approx 0.433$の間にあることが知られている。
我々は、Farhi、Goldstone、Gutmann、Sipserによって導入されたワークスペースのない、翻訳不変アルゴリズムの特別なクラスを考える。
まず、順序探索のための$k$-query量子アルゴリズムは、この特殊クラスにおいて$k$-queryアルゴリズムによって実装可能であることを示す。
第二に、線形プログラミングを用いて、最も正確な5ドルのクエリー量子アルゴリズムが長さ7,265ドルのリストを検索できることを示し、同時に5,7265}{n} \approx 0.390 \log_{2}{n}$量子クエリーを漸近的に使用する順序付き探索アルゴリズムを与える。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。
この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
論文 参考訳（メタデータ） (2023-12-05T21:15:09Z) - Do you know what q-means? [45.810803542748495]
Kerenidis, Landman, Luongo, Prakash (NeurIPS')によって提案された量子アルゴリズムの改良版を提案する。
我々のアルゴリズムは、先行研究の量子線型代数プリミティブに頼るのではなく、QRAMを用いて単純な状態を作成する。
また、$varepsilon$-$k$-meansに対して、$Obigで実行される"dequantized"アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{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) - 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) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。