論文の概要: Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly

• arxiv url: http://arxiv.org/abs/2604.06106v1
• Date: Tue, 07 Apr 2026 17:17:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-08 17:42:09.959941
• Title: Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly
• Title（参考訳）: 非偏差量子最適化法によるパンジェノム誘導配列の合成
• Authors: Josh Cudby, Sergii Strelchuk,
• Abstract要約: ゲノム組立問題に対する短期量子最適化手法を開発した。 固定された線形ランプQAOAスケジュールと反復的ウォームスタートバイアス更新を組み合わせたIterative-QAOAフレームワークを使用する。 カスタム回路コンパイル戦略は、標準ツールと比較してハードウェアゲートのオーバーヘッドを最大67%削減する。
• 参考スコア（独自算出の注目度）: 0.42970700836450487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Assembling genomes from short-read sequencing data remains difficult in repetitive regions, where reference bias and combinatorial complexity limit existing methods. Pangenome-guided sequence assembly (PGSA) mitigates reference bias by reconstructing an individual genome as a walk through a population-level graph. The associated problem, identifying a walk whose node visits match read-derived copy numbers, is NP-hard and already challenges classical solvers at a moderate scale. We develop near-term quantum optimisation approaches for this computational bottleneck. We consider two problem encodings: an established quadratic unconstrained binary optimisation and a new higher-order binary optimisation (HUBO) formulation. The latter reduces the number of variables from $O(N^2)$ to $O(N\log N)$ and places moderate-sized instances within the qubit budget of current devices. We solve both using the Iterative-QAOA framework, which combines a fixed linear-ramp QAOA schedule with iterative warm-start bias updates, avoiding the overhead of full variational parameter optimisation. A custom circuit compilation strategy reduces hardware gate overhead by up to 67\% compared with standard tools. In noiseless simulations of QUBO problems, Iterative-QAOA reliably identifies optimal assemblies from as few as $10^{-17}\%$ of all candidate solutions, and \textit{IBM} quantum hardware closely reproduces relevant results with sufficient sampling via CVaR-style post-selection. For HUBO, the variable reduction comes at the cost of deeper compiled circuits and greater noise sensitivity: an expected qubit--depth trade-off. Our findings establish pangenome assembly as a concrete, biologically motivated problem class at the scale where quantum optimisation may first provide practical value.
• Abstract（参考訳）: 短読シークエンシングデータからのゲノムの組み立ては、参照バイアスと組合せ複雑性が既存の方法を制限する反復的な領域で難しいままである。 Pangenome-Guided sequence assembly (PGSA)は、個々のゲノムを集団レベルのグラフのウォークとして再構成することで参照バイアスを緩和する。 関連する問題は、ノードが読み上げから来るコピー番号にマッチするウォークを識別することであり、NPハードであり、既に古典的な解法を適度なスケールで挑戦している。 この計算ボトルネックに対する短期量子最適化手法を開発する。 本稿では,定式化された2進最適化と高次2進最適化(HUBO)の2つの問題符号化について考察する。 後者は変数の数を$O(N^2)$から$O(N\log N)$に減らし、現在のデバイスのキュービット予算内に中等サイズのインスタンスを置く。 固定された線形ランプQAOAスケジュールと反復的ウォームスタートバイアス更新を組み合わせたIterative-QAOAフレームワークを使用することで、完全な変動パラメータ最適化のオーバーヘッドを回避することができる。 カスタム回路のコンパイル戦略は、標準ツールと比較してハードウェアゲートのオーバーヘッドを最大67\%削減する。 QUBO問題のノイズレスシミュレーションにおいて、Iterative-QAOAは、すべての候補解の10-17}\%$から最適なアセンブリを確実に特定し、 \textit{IBM} 量子ハードウェアは、CVaRスタイルのポストセレクションによって十分なサンプリングを行い、関連する結果を密に再現する。 HUBOの場合、可変化はより深くコンパイルされた回路とより高感度なノイズが伴う。 本研究は, 量子最適化が最初に実用的価値を提供するスケールにおいて, パンジェノムを具体的, 生物学的に動機づけた問題クラスとして確立した。

関連論文リスト

• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  分散量子最適化のための構造認識フレームワークを提案する。 検索スペースが$N$の場合、我々のフレームワークはプロセッサやセパレータに依存した要素に対して$O(sqrtN)$クエリ複雑性を達成する。 構造を考慮した分解は、量子ネットワーク上でのスケーラブルな分散量子最適化に実践的な道をもたらすことを示す。
  論文  参考訳（メタデータ） (2026-03-08T15:15:52Z)
• On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation [44.084531611147305]
  単一ループ近似インプリシト差分法(SSAID)アルゴリズムの洗練された収束解析を行う。 i) 最適な$mathcalO(-2)$最先端のマルチループメソッドのレートと一致し、 (ii) $-dependenceの最初の明示的できめ細かい特徴を提供する。
  論文  参考訳（メタデータ） (2026-02-27T03:12:08Z)
• Pangenome-guided sequence assembly via binary optimisation [0.040993632551842324]
  パンジェノム誘導配列アセンブリのためのフレームワークを提案する。 単一の参照ゲノムへのバイアスを伴わずに、複雑な領域の短読データを解決できる。 本手法は,量子コンピュータ上で実装可能なグラフ最適化問題としてアセンブリをフレーム化する。
  論文  参考訳（メタデータ） (2025-08-11T17:17:21Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。 本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
  論文  参考訳（メタデータ） (2025-04-21T18:19:19Z)
• Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models [3.390330377512402]
  2次元の$(gamma, beta)$サーチを$gamma$より1次元の検索に還元する方法を示し、$beta*$を解析的に計算する。 このアプローチはRecursive QAOA (RQAOA) を用いて検証され、粗い最適化RQAOAと半定値プログラムを一貫して上回る。
  論文  参考訳（メタデータ） (2025-01-27T19:00:00Z)
• Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables [0.7015624626359264]
  トラベリングパーソン販売問題(TSP)の例を用いて、最適化問題に対するより量子効率の高い回路構成を示す。 特定の冗長性を取り除いた場合、上記の従来の符号化に比べて、必要量子ビットの数は線形因子によって減少することができる。 実験の結果, 提案した符号化法と同等に精度が向上する一方, 必要な古典的反復回数はわずかに増加することがわかった。
  論文  参考訳（メタデータ） (2024-12-10T12:12:34Z)
• Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems [0.0]
  クローズストストリング問題(Closest String problem)は、生物情報学や符号化理論でよく見られるNP完全問題である。 2つのQUBOの定式化が提案されており、1つはもう1つに対してわずかに修正されている。 DWaveアナライザは、特定のプラットフォーム固有の関心事に対する最適なガイドラインを提供しながら使われてきた。
  論文  参考訳（メタデータ） (2023-10-19T16:03:25Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• 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)

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

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