論文の概要: Quantum search in a dictionary based on fingerprinting-hashing
- arxiv url: http://arxiv.org/abs/2412.11422v1
- Date: Mon, 16 Dec 2024 03:43:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-17 13:54:20.546832
- Title: Quantum search in a dictionary based on fingerprinting-hashing
- Title（参考訳）: フィンガープリントハッシュに基づく辞書における量子探索
- Authors: Farid Ablayev, Nailya Salikhova, Marat Ablayev,
- Abstract要約: 長さ$m$の単語を、大きさ$n$の未分類辞書で検索する量子クエリアルゴリズムを提案する。
このアルゴリズムは以前のアルゴリズムと同様に$O(sqrtn)$クエリ(Grover演算子)を使用する。
このアルゴリズムは(a)Grover振幅増幅演算子のシーケンスを適用する前に第1レベルの振幅増幅を提供し、(b)メモリ使用の観点からアルゴリズムをより効率的にする。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: In this work, we present a quantum query algorithm for searching a word of length $m$ in an unsorted dictionary of size $n$. The algorithm uses $O(\sqrt{n})$ queries (Grover operators), like previously known algorithms. What is new is that the algorithm is based on the quantum fingerprinting-hashing technique, which (a) provides a first level of amplitude amplification before applying the sequence of Grover amplitude amplification operators and (b) makes the algorithm more efficient in terms of memory use -- it requires $O(\log n + \log m)$ qubits. Note that previously developed algorithms by other researchers without hashing require $O(\log n + m)$ qubits.
- Abstract（参考訳）: 本研究では,長さ$m$の単語を,サイズ$n$の未分類辞書で検索する量子クエリアルゴリズムを提案する。
このアルゴリズムは以前に知られていたアルゴリズムと同様に$O(\sqrt{n})$クエリ(Grover演算子)を使用する。
新しくなったのは、このアルゴリズムが量子指紋認証技術をベースにしていることだ。
(a)Grover振幅増幅演算子のシーケンスを適用する前に、第1レベルの振幅増幅を提供する。
(b) メモリ使用率の面でアルゴリズムをより効率的にするため、$O(\log n + \log m)$ qubitsが必要である。
ハッシュのない他の研究者による以前に開発されたアルゴリズムには$O(\log n + m)$ qubitsが必要であることに注意。
関連論文リスト
- Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - 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) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Improved Algorithm and Lower Bound for Variable Time Quantum Search [1.2246649738388389]
変数時間探索は、異なる項目に対するクエリに異なる時間を要する量子探索の形式である。
我々の最初の結果は、複雑さの$O(sqrtTlog n)$で可変時間探索を行う新しい量子アルゴリズムである。
2つ目の結果は、$Omega(sqrtTlog T)$の量子下界である。
論文 参考訳（メタデータ） (2023-02-13T23:24:49Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
論文 参考訳（メタデータ） (2020-12-06T18:39:20Z) - Quantum Algorithms for String Processing [58.720142291102135]
既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。
同じアイデアを用いて、文字列比較問題に対して2つのアルゴリズムを提供する。
第2のアルゴリズムは、既存のアルゴリズムよりも指数関数的に高速に動作する。
論文 参考訳（メタデータ） (2020-12-01T09:59:06Z) - Resonant Quantum Search with Monitor Qubits [0.0]
連続的ハミルトニアンと共振を利用した一般化探索問題($N$項目中$k$マークされた項目を探索する)のアルゴリズムを提案する。
この共振アルゴリズムはGroverアルゴリズムと同じ時間複雑性$O(sqrtN/k)$を持つ。
論文 参考訳（メタデータ） (2020-02-21T19:31:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。