論文の概要: Quantum algorithm for position weight matrix matching

• arxiv url: http://arxiv.org/abs/2303.03569v1
• Date: Tue, 7 Mar 2023 00:34:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-08 16:52:39.061454
• Title: Quantum algorithm for position weight matrix matching
• Title（参考訳）: 位置重み行列マッチングのための量子アルゴリズム
• Authors: Koichi Miyamoto, Naoki Yamamoto, Yasubumi Sakakibara
• Abstract要約: バイオインフォマティクス, 位置重み行列(PWM)マッチングにおける問題に対する2つの量子アルゴリズムを提案する。 提案した2つのアルゴリズム、ナイーブ法とモンテカルロ法は、生物学的配列のエントリへの分子アクセスを考慮し、一致したセグメントを出力する。
• 参考スコア（独自算出の注目度）: 0.9404723842159504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence such as DNA and protein that have high scores defined by the PWM and are thus of informational importance related to biological function. The two proposed algorithms, the naive iteration method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence and the PWM. The former uses quantum amplitude amplification (QAA) for sequence motif search, resulting in the query complexity scaling on the sequence length $n$, the sequence motif length $m$ and the number of the PWMs $K$ as $\widetilde{O}\left(m\sqrt{Kn}\right)$, which means speedup over existing classical algorithms with respect to $n$ and $K$. The latter also uses QAA, and further, quantum Monte Carlo integration for segment score calculation, instead of iteratively operating quantum circuits for arithmetic in the naive iteration method; then it provides the additional speedup with respect to $m$ in some situation. As a drawback, these algorithms use quantum random access memories and their initialization takes $O(n)$ time. Nevertheless, our algorithms keep the advantage especially when we search matches in a sequence for many PWMs in parallel.
• Abstract（参考訳）: バイオインフォマティクスにおける問題に対する2つの量子アルゴリズム、位置重み行列(PWM)マッチングを提案する。これは、PWMによって定義される高いスコアを持つDNAやタンパク質などの生物学的配列のセグメント(シーケンスモチーフ)を見つけることを目的としており、したがって生物学的機能に関連する情報的重要性を持つ。 提案した2つのアルゴリズムは,生物配列とPWMのエントリへの分子的アクセスを考慮し,提案手法であるナイーブ反復法とモンテカルロ法を用いて,一致したセグメントを出力する。 前者はシーケンスモチーフ探索に量子振幅増幅(QAA)を使用し、結果としてシーケンス長$n$、シークエンスモチーフ長$m$、PWMs$K$ as $\widetilde{O}\left(m\sqrt{Kn}\right)$のクエリ複雑性がスケーリングされる。 後者は QAA も使用しており、さらに量子モンテカルロ積分をセグメントスコア計算に利用し、単純反復法で算術演算のために反復的に量子回路を演算する代わりに、ある状況において$m$ に関する追加のスピードアップを提供する。 欠点として、これらのアルゴリズムは量子ランダムアクセスメモリを使用し、初期化には$O(n)$時間を要する。 にもかかわらず、我々のアルゴリズムは、多くのpwmを並列に並べて検索する場合、特に有利である。

関連論文リスト

• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。 本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
  論文  参考訳（メタデータ） (2024-09-06T03:32:02Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Preparation of matrix product states with log-depth quantum circuits [0.3277163122167433]
  局所ゲートの量子回路を用いた量子デバイス上での行列積状態(MPS)の調製について検討する。 我々はまず、$N$サイトの翻訳不変正規MPSを忠実に作成するには、回路深さ$T=Omega(log N)$が必要であることを証明した。 次に、正規化群変換に基づくアルゴリズムを導入し、誤差$epsilon$ in depth $T=O(log (N/epsilon))$で正規MPSを作成する。
  論文  参考訳（メタデータ） (2023-07-04T13:05:29Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPは1970年代の量子光学のモデルとしてマッキによって導入された。 ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。 バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
  論文  参考訳（メタデータ） (2023-05-25T08:43:11Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Algorithm for Anomaly Detection of Sequences [13.087762988229068]
  振幅領域におけるPiecewise Aggregate(ADPAAD)を用いた異常検出のための量子アルゴリズムを提案する。 我々の量子アルゴリズムは、その古典的手法よりもサブシーケンスの数とサブシーケンスの長さを高速化することができる。
  論文  参考訳（メタデータ） (2022-09-18T16:14:16Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• 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)
• Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
  振幅の間隔推定のための適応アルゴリズムを提案する。 提案アルゴリズムは、同じレベルの精度を達成するために、同じ数の量子クエリを使用する。 我々は,古典モンテカルロサンプリングに対する2次高速化として,オラクルクエリの数が$O(1/epsilon)$に達することを厳密に証明する。
  論文  参考訳（メタデータ） (2022-06-16T21:11:15Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。