論文の概要: Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems

• arxiv url: http://arxiv.org/abs/2310.12852v1
• Date: Thu, 19 Oct 2023 16:03:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-20 14:24:58.259586
• Title: Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems
• Title（参考訳）: D-Waveシステムにおける最接近弦問題に対する量子アニーリング解
• Authors: Chandeepa Dissanayake
• Abstract要約: クローズストストリング問題(Closest String problem)は、生物情報学や符号化理論でよく見られるNP完全問題である。 2つのQUBOの定式化が提案されており、1つはもう1つに対してわずかに修正されている。 DWaveアナライザは、特定のプラットフォーム固有の関心事に対する最適なガイドラインを提供しながら使われてきた。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Closest String Problem is an NP-complete problem which appears more commonly in bioinformatics and coding theory. Less surprisingly, classical approaches have been pursued with two prominent algorithms being the genetic algorithm and simulated annealing. Latest improvements to quantum computing devices with a specialization in optimization tasks such as DWave systems, suggest that an attempt to embed the problem in a model accepted by such systems is worthwhile. In this work, two QUBO formulations have been proposed, with one being a slight modification over the other. Subsequently, an evaluation based on a few simple test cases had been carried out on both formulations. In this regard, the D-Wave annealers have been used, while providing guidelines for optimality on certain platform-specific concerns. For evaluation purposes, a metric termed Occurrence Ratio (OR) has been defined. With minimal hyperparameter tuning, the expected solutions were obtained for every test case and the optimality was guaranteed. To address practical and implementation issues, an inherent decomposition strategy based on the possibility of having substrings has been elucidated to accommodate the restricted qubit count. Conclusively, the need for further investigation on tuning the hyperparameters is emphasized.
• Abstract（参考訳）: 最も近い文字列問題はnp完全問題であり、バイオインフォマティクスやコーディング理論でより一般的に見られる。 意外なことに、古典的なアプローチは遺伝的アルゴリズムとシミュレートアニーリングという2つの顕著なアルゴリズムによって追求されている。 DWaveシステムのような最適化タスクを専門化する量子コンピューティングデバイスの最新改良は、そのようなシステムで受け入れられるモデルに問題を埋め込もうとする試みには価値があることを示唆している。 この研究では、2つのqubo定式化が提案されており、一方は他方に対してわずかに修正されている。 その後, いずれの定式化においても, 簡易な試験事例に基づく評価が実施されている。 この点において、D-Waveアニーラーは、特定のプラットフォーム固有の懸念に対して最適なガイドラインを提供しながら使われてきた。 評価のために、Occurrence Ratio (OR) と呼ばれる計量が定義された。 最小のハイパーパラメータチューニングでは、すべてのテストケースで期待される解が得られ、最適性が保証された。 実用および実装上の問題に対処するため、制限量子ビット数に対応するために、サブストリングを持つ可能性に基づく固有の分解戦略が解明された。 結論として、ハイパーパラメータのチューニングに関するさらなる調査の必要性が強調される。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。 このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
  論文  参考訳（メタデータ） (2024-07-29T13:54:28Z)
• Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
  量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。 この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。 D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
  論文  参考訳（メタデータ） (2024-07-09T11:44:58Z)
• Dual-Directed Algorithm Design for Efficient Pure Exploration [9.728332815218181]
  有限組の代替品を用いた逐次適応実験の文脈における純粋探索問題を考える。 固定予算, 固定信頼度, 後収束率設定に対する最大最適化問題として問題複雑性尺度を定式化する。 我々のアルゴリズムは、$varepsilon$-best-armの識別(または、良好な選択保証の確率でランク付けと選択)としきい値の帯域幅で最適性を得る。
  論文  参考訳（メタデータ） (2023-10-30T07:29:17Z)
• Posiform Planting: Generating QUBO Instances for Benchmarking [2.7624021966289605]
  本稿では,任意のサイズのランダムQUBOインスタンスを既知の最適解で生成する,posform plantingと呼ばれる新しい手法を提案する。 実験では,最大5,627ドルキュービットの最適化問題の最適植込み解をサンプリングするD-Wave量子アニールの能力を実証した。
  論文  参考訳（メタデータ） (2023-08-10T21:23:41Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。 本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
  論文  参考訳（メタデータ） (2022-11-01T07:52:47Z)
• Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
  雑音は量子回路のバイアスによる目的関数の評価を行う。 我々は、欠落した保証を導き、収束率が影響を受けないことを見出す。
  論文  参考訳（メタデータ） (2022-09-21T19:18:41Z)
• 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)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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