論文の概要: Structured search algorithm: A quantum leap
- arxiv url: http://arxiv.org/abs/2504.03426v1
- Date: Fri, 04 Apr 2025 13:16:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-14 17:16:31.552373
- Title: Structured search algorithm: A quantum leap
- Title(参考訳): 構造化探索アルゴリズム:量子跳躍
- Authors: Yash Prabhat, Snigdha Thakur, Ankur Raina,
- Abstract要約: グロバーの量子探索アルゴリズムは、量子アルゴリズムの長所を示す。
この文字は、構造化された探索法を用いてGroverのアルゴリズムを前進させ、非有界探索速度を達成する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Grover's quantum search algorithm showcases the prowess of quantum algorithms, phenomenally reducing the complexity of the search operation of unsorted data. This letter advances Grover's algorithm using a structured search method to attain an unbounded search speed. Remarkably, only two Oracle calls are required to search any element in a dataset of size $2^n$, $n$ being an integer. The algorithm leverages a fixed point approach, iteratively identifying the solution state for multiple qubits at a time, progressively narrowing the search space. The experimental outcomes affirm the algorithm's performance by searching a bit string in 5TB of unsorted binary data on QPU IBM Kyiv. The letter also hypothesizes a scalable classical simulation of the said algorithm.
- Abstract(参考訳): グロバーの量子探索アルゴリズムは量子アルゴリズムの進歩を示し、非分類データの探索操作の複雑さを著しく減らしている。
この文字は、構造化された探索法を用いてGroverのアルゴリズムを前進させ、非有界探索速度を達成する。
注目すべきは、サイズ2^n$, $n$が整数であるデータセットの任意の要素を検索するために2つのOracleコールしか必要としないことだ。
このアルゴリズムは固定点アプローチを利用して、複数のキュービットに対する解状態を反復的に同定し、探索空間を徐々に狭めている。
実験結果は、QPU IBM Kyiv上の5TBの未分類バイナリデータをビット文字列で検索することで、アルゴリズムの性能を裏付けるものである。
このレターはまた、そのアルゴリズムのスケーラブルな古典的シミュレーションを仮定している。
関連論文リスト
- The optimization of exact multi-target quantum search algorithm based on MindSpore [3.633444773654794]
修正Groverのアルゴリズムに基づいて,最適化されたマルチターゲット探索アルゴリズムを提案する。
提案したアルゴリズムは、量子ゲート数を少なくとも21.1%減らし、量子回路の深さを少なくとも11.4%減らすことができる。
論文 参考訳(メタデータ) (2024-12-24T09:39:59Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳(メタデータ) (2024-05-02T10:29:06Z) - Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成される結果集合から解を抽出するためにも用いられる。
マッチング条件の各ビットに個別のオラクルを関連付け、独立にテスト可能な複数の部分的なオラクル関数を得るという考え方を探求する。
アルゴリズムは最も単純な検索シナリオに対して検証され、入力されたインデックスビットは置換演算を用いてスクランブルされる。
論文 参考訳(メタデータ) (2024-03-19T11:32:02Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳(メタデータ) (2023-11-19T00:06:11Z) - Hybrid classical-quantum text search based on hashing [0.0]
非順序データベースにおける古典的な検索クエリの複雑さは、テキストの長さと与えられた値の長さにおいて線形であることが知られている。
本稿ではGroverの検索を実装した古典量子ハイブリッドアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-11-02T13:16:07Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳(メタデータ) (2023-06-28T16:33:39Z) - Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳(メタデータ) (2023-02-16T13:57:19Z) - Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm [15.622577797491788]
イソマプアルゴリズムは、ニューロイメージング、スペクトル分析、その他の分野で広く用いられている。
本稿では,2つのサブアルゴリズムからなる量子イソマプアルゴリズムを提案する。
量子イソマップアルゴリズムの時間複雑性は$O(dNpolylogN)$である。
論文 参考訳(メタデータ) (2022-12-07T12:29:41Z) - Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer [2.487445341407889]
Depth-First SearchとGroverのアルゴリズムを組み合わせてDepth-First Grover Search(DFGS)を生成する
DFGSは未知の解数で非構造化データベース上の複数解探索問題を処理する。
新しいアルゴリズムは$mathcalO(msqrtN)$の平均複雑さを達成し、通常のGrover Searchと同じくらい効率的に機能する。
論文 参考訳(メタデータ) (2022-10-10T13:10:28Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Variational learning algorithms for quantum query complexity [3.980076328494117]
量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
論文 参考訳(メタデータ) (2022-05-16T05:16:15Z) - Searching and Sorting Algorithms for Quantum Annealing Computers [0.0]
ソート安定性を考慮したデータセットのソートアルゴリズムを提供する。
アルゴリズムのスケーラビリティは問題の大きさの関数として特徴づけられる。
論文 参考訳(メタデータ) (2022-04-28T00:18:57Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳(メタデータ) (2021-05-18T06:51:11Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Quantum Algorithms for String Processing [58.720142291102135]
既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。
同じアイデアを用いて、文字列比較問題に対して2つのアルゴリズムを提供する。
第2のアルゴリズムは、既存のアルゴリズムよりも指数関数的に高速に動作する。
論文 参考訳(メタデータ) (2020-12-01T09:59:06Z) - Quantum Search with Prior Knowledge [15.384459603233978]
本稿では,Grover の探索アルゴリズムの新たな一般化を提案する。
提案アルゴリズムは,クエリ数が固定された場合の解を見つけるための最適成功確率を実現する。
論文 参考訳(メタデータ) (2020-09-18T09:50:33Z) - Fast Search on Binary Codes by Weighted Hamming Distance [38.50174794945964]
ハンミング距離を重み付けして最寄りの2進符号を$K$で探索する高速探索アルゴリズムが提案されている。
提案した探索アルゴリズムに基づく高速探索フレームワークは,長いバイナリ符号の問題を解くために設計されている。
論文 参考訳(メタデータ) (2020-09-18T02:24:44Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。
エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。
これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
論文 参考訳(メタデータ) (2020-09-15T17:28:42Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。