論文の概要: Parameterized quantum algorithms for closest string problems
- arxiv url: http://arxiv.org/abs/2510.15529v1
- Date: Fri, 17 Oct 2025 11:01:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-20 20:17:34.587008
- Title: Parameterized quantum algorithms for closest string problems
- Title（参考訳）: 近接弦問題に対するパラメタライズド量子アルゴリズム
- Authors: Josh Cudby, Sergii Strelchuk,
- Abstract要約: CSP(Closest String Problem)とCSSP(Closest Substring Problem)の3つの量子アルゴリズムを提案する。
各アルゴリズムは、特定の設定で古典的なアルゴリズムよりも優れた性能を示す。
また、二進アルファベットを持つCSPの条件付き下界を導出し、最初のアルゴリズムがその支配的なスケーリング係数において厳密であることを示す。
- 参考スコア（独自算出の注目度）: 0.42970700836450487
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Parameterized complexity enables the practical solution of generally intractable NP-hard problems when certain parameters are small, making it particularly useful in real-world applications. The study of string problems in this framework has been particularly fruitful, yielding many state-of-the-art classical algorithms that run efficiently in certain parameter regimes contrary to their worst- or average-case performance. Motivated by the dramatic increase in genomic data and its growing computational demands, we initiate the study of the quantum parameterized complexity of the Closest String Problem (CSP) and the related Closest Substring Problem (CSSP). We present three quantum algorithms for the CSP and one for the CSSP. Each algorithm demonstrates improved performance over classical counterparts in specific parameter regimes, highlighting the promise of quantum approaches in structured combinatorial settings. We also derive a conditional lower bound for the CSP with binary alphabets, showing that our first algorithm is tight in its dominant scaling factor.
- Abstract（参考訳）: パラメータ化複雑性は、特定のパラメータが小さい場合、一般に難解なNPハード問題の実用的な解決を可能にし、現実世界のアプリケーションで特に有用である。
この枠組みにおける文字列問題の研究は、特に実りあるものであり、最悪の性能や平均的な性能とは対照的に、特定のパラメータ規則で効率的に動作する最先端の古典的アルゴリズムが多数存在する。
ゲノムデータの劇的な増加と,その増大する計算要求により,我々は,CSP(Closest String Problem)とCSSP(Closest Substring Problem)の量子パラメータ化複雑性の研究を開始した。
CSPには3つの量子アルゴリズム、CSSPには1つの量子アルゴリズムを示す。
それぞれのアルゴリズムは、特定のパラメータ規則における古典的手法よりも優れた性能を示し、構造化組合せ設定における量子アプローチの約束を強調している。
また、二進アルファベットを持つCSPの条件付き下界を導出し、最初のアルゴリズムがその支配的なスケーリング係数において厳密であることを示す。
関連論文リスト
- A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits [0.0]
ゲート複雑性における初期状態として,N長ハミルトニアンサイクルの均一な重ね合わせ状態を生成する量子アルゴリズムを提案する。
理論的にはクエリの複雑さが低いが、実用的な実装ソリューションが欠如しているアルゴリズムと比較すると、本アルゴリズムは回路実装が可能である。
論文 参考訳（メタデータ） (2025-02-12T23:58:25Z) - Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
本稿では、量子遺伝的アルゴリズム(QGA)を用いて、旅行セールスマン問題(TSP)と呼ばれる新しい問題を解決する方法を実装する。
我々は、この新しいアプローチがいかにうまく機能するかを、古典的遺伝的アルゴリズム(CGA)として知られる従来の手法と比較した。
論文 参考訳（メタデータ） (2024-09-20T08:27:42Z) - 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) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳（メタデータ） (2021-06-24T16:39:31Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。