論文の概要: Intermediate-qudit assisted Improved quantum algorithm for string
matching with an Advanced Decomposition of Fredkin gate
- arxiv url: http://arxiv.org/abs/2304.03050v1
- Date: Thu, 6 Apr 2023 13:11:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-07 14:22:00.446599
- Title: Intermediate-qudit assisted Improved quantum algorithm for string
matching with an Advanced Decomposition of Fredkin gate
- Title（参考訳）: フレッドキンゲートの高度分解による弦マッチングのための中間量子支援改良量子アルゴリズム
- Authors: Amit Saha and Om Khanna
- Abstract要約: 本稿では,高次元中間クォーディットを用いた文字列マッチング問題に対する量子回路の実装について述べる。
また、中間クォーディットの助けを借りれば、深さの複雑さを低減できるだけでなく、クエリの複雑さを減らせることも示される。
- 参考スコア（独自算出の注目度）: 1.9798034349981157
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The circuit-level implementation of a quantum string-matching algorithm,
which matches a search string (pattern) of length $M$ inside a longer text of
length $N$, has already been demonstrated in the literature to outperform its
classical counterparts in terms of time complexity and space complexity.
Higher-dimensional quantum computing is becoming more and more common as a
result of its powerful storage and processing capabilities. In this article, we
have shown an improved quantum circuit implementation for the string-matching
problem with the help of higher-dimensional intermediate temporary qudits. It
is also shown that with the help of intermediate qudits not only the complexity
of depth can be reduced but also query complexity can be reduced for a quantum
algorithm, for the first time to the best of our knowledge. Our algorithm has
an improved query complexity of $O(\sqrt{N-M+1})$ with overall time complexity
$O\left(\sqrt{N-M+1}\left((\log {(N-M+1)} \log N)+\log (M)\right)\right)$ as
compared to the state-of-the-art work which has a query complexity of
$O(\sqrt{N})$ with overall time complexity $O\left(\sqrt{N}\left((\log
N)^{2}+\log (M)\right)\right)$, while the ancilla count also reduces to
$\frac{N}{2}$ from $\frac{N}{2}+M$. The cost of state-of-the-art quantum
circuit for string-matching problem is colossal due to a huge number of Fredkin
gates and multi-controlled Toffoli gates. We have exhibited an improved gate
cost and depth over the circuit by applying a proposed Fredkin gate
decomposition with intermediate qutrits (3-dimensional qudits or ternary
systems) and already existing logarithmic-depth decomposition of $n$-qubit
Toffoli or multi-controlled Toffoli gate (MCT) with intermediate ququarts
(4-dimensional qudits or quaternary systems). We have also asserted that the
quantum circuit cost is relevant instead of using higher dimensional qudits
through error analysis.
- Abstract（参考訳）: 長さ$M$の検索文字列(パターン)を長さ$N$の長いテキスト内でマッチングする量子文字列マッチングアルゴリズムの回路レベル実装は、時間複雑性と空間複雑性の点で古典的手法よりも優れていることが文献で実証されている。
高次元量子コンピューティングは、その強力なストレージと処理能力の結果として、ますます一般的になりつつある。
本稿では,高次元の中間一時的quditの助けを借りて,弦マッチング問題に対する量子回路実装の改善を示す。
また、中間quditsの助けを借りれば、深さの複雑さを低減できるだけでなく、量子アルゴリズムではクエリの複雑さを初めて最善の知識に還元できることを示した。
我々のアルゴリズムは、全体的な時間複雑性を持つ$O(\sqrt{N-M+1})$O\left(\sqrt{N-M+1}\left((\log {(N-M+1)} \log N)+\log (M)\right)\right)$のクエリ複雑性を持つステート・オブ・ザ・アートの複雑さを持つ$O(\sqrt{N})$のクエリ複雑性を持つ$O(\sqrt{N}\left(((\log N)^{2}+\log (M)\right)$のクエリ複雑性を持つ$O(\sqrt{N})$のクエリ複雑性を持つ$O(\sqrt{N}\left(((\log N)^{2}+\log (M)\right)$のクエリ複雑性を持つ。
文字列マッチング問題に対する最先端量子回路のコストは、大量のフレドキンゲートと多制御トフォリゲートのため、余剰である。
中間クイット(3次元クイットまたは3元系)によるフレドキンゲート分解と、既に存在するn$-qubit toffoliまたはマルチコントロール toffoliゲート(mct)の対数分解を中間クイット(4次元クイットまたは4元系)で適用することにより、回路上のゲートコストと深さを改善した。
また, 量子回路コストは, 誤差解析による高次元quditを用いるのではなく, 関連性があると主張した。
関連論文リスト
- Fast-forwarding quantum algorithms for linear dissipative differential equations [2.5677613431426978]
truncated Dyson級数に基づく量子アルゴリズムは、コスト$widetildemathcalO(log(T) (log (1/epsilon)) 2 )$で散逸したODEの履歴状態を時間$T$まで作成できることを示す。
応用として、量子アルゴリズムは散逸性非エルミート量子力学と熱過程を高速な複雑性サブ線形時間でシミュレートできることを示す。
論文 参考訳（メタデータ） (2024-10-17T03:33:47Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳（メタデータ） (2024-02-21T15:06:51Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - $T$-depth-optimized Quantum Search with Quantum Data-access Machine [0.0]
量子データアクセスマシン(QDAM)と呼ばれる効率的な量子データアクセスプロセスを導入する。
我々は,実効量子誤り訂正符号内の論理量子ビットからなるフォールトトレラント量子計算(FTQC)の観点から,我々のアルゴリズムのランタイムを解析する。
論文 参考訳（メタデータ） (2022-11-08T01:36:02Z) - A Note on Quantum Divide and Conquer for Minimal String Rotation [1.8275108630751844]
語彙的に最小限の弦の回転は、弦処理の基本的な問題である。
準最適量子アルゴリズムは、その開発中に提案され、量子分割や征服といった新しいアイデアが導入された。
論文 参考訳（メタデータ） (2022-10-17T14:51:49Z) - Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
Z_N$のディヘドラルコセット問題(DCP)は量子コンピューティングやポスト量子暗号において広く研究されている。
Ettinger-Hoyerアルゴリズムは$O(log(N))$クエリでDCPを解くことが知られている。
本稿では,Ettinger-Hoyerアルゴリズムよりも線形クエリ方式を改良した最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-29T05:30:54Z) - 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) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。