Fugu-MT 論文翻訳(概要): Quantum Algorithms for the Minimum Steiner Tree problem with application to Binary Near-Perfect Phylogenies

論文の概要: Quantum Algorithms for the Minimum Steiner Tree problem with application to Binary Near-Perfect Phylogenies

arxiv url: http://arxiv.org/abs/2510.09911v1
Date: Fri, 10 Oct 2025 22:53:16 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-14 18:06:29.687483
Title: Quantum Algorithms for the Minimum Steiner Tree problem with application to Binary Near-Perfect Phylogenies
Title（参考訳）: 最小ステイナツリー問題に対する量子アルゴリズムと2次近似完全フィロジェニーへの応用
Authors: Lingfa Meng, David Salvador Novo, Albert H. Werner, Samir Bhatt,
Abstract要約: バイオインフォマティクスにおける量子アルゴリズムについて, BNPP(Bibinary Near-Perfect Phylogeny Problem)の解法について述べる。我々は、回路モデルにおいて、複雑性$O(e)(k,l)k)$の最小スタイナーツリー(MST)問題に対して、別の空間正確なアルゴリズムを与える。
参考スコア（独自算出の注目度）: 1.1199585259018459
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We present a quantum algorithm in bioinformatics for solving the Binary Near-Perfect Phylogeny Problem (BNPP) with a complexity bound of $O(8.926^q + 8^q nm2)$, where n is the number of input taxa and m is the sequence length for each taxon with each character in the sequence being a binary bit using the QRAM model. We give another polynomial space exact algorithm for the Minimum Steiner Tree (MST) problem with complexity $O^*(e^{(1+g(k,l))k})$ in the circuit model.
Abstract（参考訳）: ここでは,nは入力タクタの個数,mは各タクタの列長,mはQRAMモデルを用いた二乗ビットの列の列長,O(8.926^q + 8^q nm2)$の複雑性境界を持つBNPP(Biological Near-Perfect Phylogeny Problem)を解くためのバイオインフォマティクスに量子アルゴリズムを提案する。我々は、回路モデルにおいて、複雑性$O^*(e^{(1+g(k,l))k})$の最小スタイナーツリー(MST)問題に対して、別の多項式空間正確なアルゴリズムを与える。

関連論文リスト

Qudit-based scalable quantum algorithm for solving the integer programming problem [0.0]
プログラミング (IP) はNPのハードな最適化問題であり、現実世界の様々な問題を表現するために広く使われている。 IPを解くためのほとんどの量子アルゴリズムは、整数を量子ビットにエンコードするため、非常に非効率である。本研究では,回路ベースでスケーラブルな量子アルゴリズムを複数の相互作用量子ビットを用いて提案し,量子スピードアップを示す。
論文参考訳（メタデータ） (2025-08-19T15:06:49Z)
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)
Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
CNOT回路は一般的な量子回路の共通構成ブロックである。本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
論文参考訳（メタデータ） (2024-08-07T19:51:22Z)
Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文参考訳（メタデータ） (2024-05-02T10:29:06Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文参考訳（メタデータ） (2023-06-28T16:33:39Z)
Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。 Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文参考訳（メタデータ） (2023-04-06T02:18:52Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
Pauli String Partitioning Algorithm with the Ising Model for Simultaneous Measurement [0.0]
本研究では,パウリ弦を1つの量子回路で同時に測定可能な部分群に分割する効率的なアルゴリズムを提案する。我々の分割アルゴリズムは、量子化学のための変分量子固有解法における測定総数を劇的に削減する。
論文参考訳（メタデータ） (2022-05-09T01:49:21Z)
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)
Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
語彙的最小弦回転(lexicographically minimal string rotation, LMSR)は、語彙的順序で弦のすべての回転の中で最小の回転を求める問題である。 LMSRのための$O(n3/4)$量子クエリアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-12-17T03:13:45Z)

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