論文の概要: Quantum algorithm for de novo DNA sequence assembly based on quantum
walks on graphs
- arxiv url: http://arxiv.org/abs/2308.03532v1
- Date: Mon, 7 Aug 2023 12:30:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-08 13:54:50.619135
- Title: Quantum algorithm for de novo DNA sequence assembly based on quantum
walks on graphs
- Title(参考訳): グラフ上の量子ウォークに基づく de novo dna sequence assembly の量子アルゴリズム
- Authors: G. D. Varsamis, I. G. Karafyllidis, K. M. Gilkes U. Arranz, R.
Martin-Cuevas, G. Calleja, J. Wong, H. C. Jessen, P. Dimitrakis, P. Kolovos,
R. Sandaltzopoulos
- Abstract要約: グラフの量子ウォークに基づくデ・ノボ組立のための量子アルゴリズムを開発した。
我々は、低階グラフの経路を見つけるために量子ウォークと、高階層ランクのハミルトン経路を見つける量子アルゴリズムを用いる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: De novo DNA sequence assembly is based on finding paths in overlap graphs,
which is a NP-hard problem. We developed a quantum algorithm for de novo
assembly based on quantum walks in graphs. The overlap graph is partitioned
repeatedly to smaller graphs that form a hierarchical structure. We use quantum
walks to find paths in low rank graphs and a quantum algorithm that finds
Hamiltonian paths in high hierarchical rank. We tested the partitioning quantum
algorithm, as well as the quantum algorithm that finds Hamiltonian paths in
high hierarchical rank and confirmed its correct operation using Qiskit. We
developed a custom simulation for quantum walks to search for paths in low rank
graphs. The approach described in this paper may serve as a basis for the
development of efficient quantum algorithms that solve the de novo DNA assembly
problem.
- Abstract(参考訳): De novo DNA配列は、NPハード問題である重複グラフの経路を見つけることに基づいている。
グラフの量子ウォークに基づくデノボ組立のための量子アルゴリズムを開発した。
重複グラフは階層構造を形成するより小さなグラフに繰り返し分割される。
我々は、低階グラフの経路を見つけるために量子ウォークと、高階層ランクのハミルトン経路を見つける量子アルゴリズムを用いる。
分割量子アルゴリズムと,ハイ階層ランクのハミルトン経路を探索する量子アルゴリズムをテストし,qiskitを用いてその正しい動作を確認した。
低階グラフの経路を探索するための量子ウォークのカスタムシミュレーションを開発した。
本稿では,デノボDNA組立問題の解法として,効率的な量子アルゴリズムの開発の基礎となる手法を提案する。
関連論文リスト
- Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
本稿では,完全多部グラフ上での量子ウォーク探索アルゴリズムについて検討する。
我々は、量子ウォークモデルを用いて、二次的なスピードアップを実現する。
また、量子アルゴリズムの数値シミュレーションと回路実装も提供する。
論文 参考訳(メタデータ) (2024-10-07T11:13:41Z) - The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
コヒーレント重ね合わせを持つ方程式の量子線型系を解くための2つの量子アルゴリズムを提案する。
2つの量子アルゴリズムは、ランクと一般解の両方を1つの測定で計算できる。
分析の結果,提案アルゴリズムは主に軽量対称暗号に対する攻撃に適していることがわかった。
論文 参考訳(メタデータ) (2024-05-11T03:03:14Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳(メタデータ) (2024-02-26T09:32:07Z) - Implementation of Continuous-Time Quantum Walks on Quantum Computers [0.0]
量子ウォークは、量子コンピュータ上で実装される興味深い候補である。
3つのグラフクラス上で連続時間量子ウォークに基づく探索アルゴリズムの進化演算子を実装する効率的な回路について述べる。
論文 参考訳(メタデータ) (2022-12-17T14:59:21Z) - Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
本稿では,高レベル言語で記述された量子回路から,アルゴリズム固有のグラフ状態を作成する量子回路コンパイラを提案する。
この計算は、このグラフ状態に関する一連の非パウリ測度を用いて実装することができる。
論文 参考訳(メタデータ) (2022-09-15T14:52:31Z) - From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。
本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。
今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
論文 参考訳(メタデータ) (2022-02-19T02:56:47Z) - Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
時間依存ハミルトニアンの下でのユニタリ進化は、量子ハードウェアにおけるシミュレーションの重要な構成要素である。
本稿では、トロッターステップを1ブロックの量子ゲートに圧縮するアルゴリズムを提案する。
この結果、ハミルトニアンのある種のクラスに対する固定深度時間進化がもたらされる。
論文 参考訳(メタデータ) (2021-08-06T19:38:01Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。
量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。
提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
論文 参考訳(メタデータ) (2021-06-06T13:15:25Z) - Quantum walk processes in quantum devices [55.41644538483948]
グラフ上の量子ウォークを量子回路として表現する方法を研究する。
提案手法は,量子ウォークアルゴリズムを量子コンピュータ上で効率的に実装する方法である。
論文 参考訳(メタデータ) (2020-12-28T18:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。