論文の概要: String Comparison on a Quantum Computer Using Hamming Distance
- arxiv url: http://arxiv.org/abs/2106.16173v1
- Date: Wed, 30 Jun 2021 16:09:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 08:03:21.483109
- Title: String Comparison on a Quantum Computer Using Hamming Distance
- Title(参考訳): ハミング距離を用いた量子コンピュータの文字列比較
- Authors: Mushahid Khan and Andriy Miranskyy
- Abstract要約: 我々はハミング距離を計算するための既存のアルゴリズムを拡張した。
我々は,QisKitフレームワークを用いて拡張アルゴリズムを実装し,QCの知識を必要とせずにプログラマが実行する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Hamming distance is ubiquitous in computing. Its computation gets
expensive when one needs to compare a string against many strings. Quantum
computers (QCs) may speed up the comparison.
In this paper, we extend an existing algorithm for computing the Hamming
distance. The extension can compare strings with symbols drawn from an
arbitrary-long alphabet (which the original algorithm could not). We implement
our extended algorithm using the QisKit framework to be executed by a
programmer without the knowledge of a QC (the code is publicly available). We
then provide four pedagogical examples: two from the field of bioinformatics
and two from the field of software engineering. We finish by discussing
resource requirements and the time horizon of the QCs becoming practical for
string comparison.
- Abstract(参考訳): ハミング距離はコンピューティングにおいてユビキタスである。
文字列と多くの文字列を比較する必要がある場合、計算は高価になる。
量子コンピュータ(QC)は比較を高速化することができる。
本稿では,ハミング距離を計算するための既存のアルゴリズムを拡張する。
この拡張は文字列と任意の長いアルファベット(元のアルゴリズムではできなかった)から引き出された記号を比較することができる。
QisKitフレームワークを使用して拡張アルゴリズムを実装し,QCの知識を必要とせずにプログラマが実行する(コードは公開されている)。
次に、バイオインフォマティクスの分野の2つ、ソフトウェア工学の分野の2つの例を挙げる。
最後に、資源要求とqcsが文字列比較に実用的になる時期について論じる。
関連論文リスト
- Comparing Algorithms for Loading Classical Datasets into Quantum Memory [0.0]
古典的データセットを量子メモリにロードするアルゴリズムを比較した。
5つの属性に基づく状態準備アルゴリズムの評価を行った。
また、視覚的に3つの指標(回路深度、キュービット数、古典ランタイム)を比較する。
論文 参考訳(メタデータ) (2024-07-22T15:43:18Z) - A Generalized Space-Efficient Algorithm for Quantum Bit String
Comparators [0.0]
本稿では,2ビットのアシラリービットを用いた2つの$n$-qubit論理状態の比較設計を提案する。
この研究により、量子アルゴリズムの設計において十分な柔軟性が得られ、量子アルゴリズムの開発を加速することができる。
論文 参考訳(メタデータ) (2023-11-11T14:01:35Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳(メタデータ) (2023-10-23T18:26:00Z) - Efficient Quantum Counting and Quantum Content-Addressable Memory for
DNA similarity [0.38233569758620056]
本稿では,CAM(Content-Addressable Memory)の量子アナログであるQCAMについて述べる。
回路構成は、QBArtエンコーディングを生成するために、前処理で使用した並列制御の回転ゲートを用いている。
さらに,観測可能な1つの測定値からGroverイテレーションの最適数を推定できる量子カウントアルゴリズム(HEQC)のハードウェア効率のよい実装を提案する。
論文 参考訳(メタデータ) (2023-08-01T17:59:02Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳(メタデータ) (2022-12-13T16:04:16Z) - Algorithms for Weighted Pushdown Automata [118.67634716230025]
重み付きプッシュダウンオートマトン(WPDA)は多くの自然言語処理タスクの中核にある。
WPDA上で直接動作する新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-10-13T10:21:31Z) - Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
本稿では,高レベル言語で記述された量子回路から,アルゴリズム固有のグラフ状態を作成する量子回路コンパイラを提案する。
この計算は、このグラフ状態に関する一連の非パウリ測度を用いて実装することができる。
論文 参考訳(メタデータ) (2022-09-15T14:52:31Z) - An LLVM-based C++ Compiler Toolchain for Variational Hybrid
Quantum-Classical Algorithms and Quantum Accelerators [0.8323133408188051]
本稿では,LLVMをベースとしたC++コンパイラツールチェーンを提案する。
これらのアルゴリズムをプログラムするための拡張セットをC++言語に導入する。
本研究では、温度場倍(TFD)状態を生成する量子回路を動作させることにより、フレームワークの性能を評価する。
論文 参考訳(メタデータ) (2022-02-22T19:32:50Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳(メタデータ) (2021-11-19T12:35:26Z) - Quantum Algorithms for String Processing [58.720142291102135]
既存のものよりも指数的に少ない量子メモリを使用する文字列マッチング問題に対する量子アルゴリズムを提案する。
同じアイデアを用いて、文字列比較問題に対して2つのアルゴリズムを提供する。
第2のアルゴリズムは、既存のアルゴリズムよりも指数関数的に高速に動作する。
論文 参考訳(メタデータ) (2020-12-01T09:59:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。