論文の概要: Freeze and Conquer: Reusable Ansatz for Solving the Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2508.21730v1
• Date: Fri, 29 Aug 2025 15:56:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-01 19:45:11.104604
• Title: Freeze and Conquer: Reusable Ansatz for Solving the Traveling Salesman Problem
• Title（参考訳）: フリーズとコンカー:トラベルセールスマンの問題を解決するための再利用可能なアンザッツ
• Authors: Fabrizio Fagiolo, Nicolo' Vescera,
• Abstract要約: 本稿では, (i) 置換のコンパクト符号化と (ii) 最適化フリーズ・再利用戦略を組み合わせたトラベリングセールスマン問題 (TSP) の変分アルゴリズムを提案する。 このパイプラインは、テストにおいてコストのかかる構造的な研究を排除し、NISQハードウェア上で即時にプロシージャを実装できるようにする。 その結果, 解の質を低下させることなく, アンザッツの凍結が解の時間と解の時間を大幅に短縮できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we present a variational algorithm for the Traveling Salesman Problem (TSP) that combines (i) a compact encoding of permutations, which reduces the qubit requirement too, (ii) an optimize-freeze-reuse strategy: where the circuit topology (``Ansatz'') is first optimized on a training instance by Simulated Annealing (SA), then ``frozen'' and re-used on novel instances, limited to a rapid re-optimization of only the circuit parameters. This pipeline eliminates costly structural research in testing, making the procedure immediately implementable on NISQ hardware. On a set of $40$ randomly generated symmetric instances that span $4 - 7$ cities, the resulting Ansatz achieves an average optimal trip sampling probability of $100\%$ for 4 city cases, $90\%$ for 5 city cases and $80\%$ for 6 city cases. With 7 cities the success rate drops markedly to an average of $\sim 20\%$, revealing the onset of scalability limitations of the proposed method. The results show robust generalization ability for moderate problem sizes and indicate how freezing the Ansatz can dramatically reduce time-to-solution without degrading solution quality. The paper also discusses scalability limitations, the impact of ``warm-start'' initialization of parameters, and prospects for extension to more complex problems, such as Vehicle Routing and Job-Shop Scheduling.
• Abstract（参考訳）: 本稿では,トラベリングセールスマン問題(TSP)と組み合わせた変分アルゴリズムを提案する。 (i)置換のコンパクトな符号化で、クビット要求も低減される。 (II)回路トポロジ( ``Ansatz'')をSimulated Annealing (SA) でトレーニングインスタンスに最初に最適化し,次に ``frozen'' を新しいインスタンスに再使用し,回路パラメータのみの迅速な再最適化に制限する最適化フリーズ・リユース戦略。 このパイプラインは、テストにおいてコストのかかる構造的な研究を排除し、NISQハードウェア上で即時にプロシージャを実装できるようにする。 40ドル(約4万4000円)のランダムに生成された対称なインスタンスで、4～7ドル(約4万4000円)の都市にまたがる結果、Ansatzは4つの都市に平均100ドル(約1万1000円)、9つの都市に90ドル(約9万3000円)、そして6つの都市に平均80ドル(約8万3000円)の最適な旅行サンプリング確率を達成します。 7都市での成功率は平均$\sim 20\%$と著しく低下し,提案手法のスケーラビリティ限界が出現した。 その結果, 解の質を低下させることなく, アンザッツの凍結が解の時間と解の時間を大幅に短縮できることを示す。 また、スケーラビリティの限界、パラメータの‘warm-start’初期化の影響、車載ルーティングやジョブショップスケジューリングといったより複雑な問題への拡張の可能性についても論じる。

関連論文リスト

• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
  既存の量子処理ユニット(QPU)がマルチレベル戦略においてサブソルバとしてどのように機能するかを実験的に検証する。 完全連結な 82$-qubit Sherrington-Kirkpatrick グラフに対して 10$ の近似解を求める。 量子最適化の結果は古典学と比較して解の質に関して競争力がある。
  論文  参考訳（メタデータ） (2024-08-14T20:06:32Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem [4.697039614904225]
  量子交互演算子 ansatz (QAOA+) を用いて最小被覆(MEC)問題を解く。 数値計算の結果,アルゴリズムのレベル$p$が低い場合,高い確率で解が得られることがわかった。 また、1量子ビット回転ゲートを$R_Z$で除去することで量子回路を最適化する。
  論文  参考訳（メタデータ） (2022-11-28T12:45:52Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement [1.720510639137902]
  量子近似最適化アルゴリズム (QAOA) は変分量子アルゴリズムであり、量子コンピュータは変分ユニタリ演算子の$p$層からなる変分アンサッツを実装している。 本稿では,QAOAを$p+1$で局所最小のQAOAを$p$で使用するQAOAの遷移状態の解析的構成について述べる。
  論文  参考訳（メタデータ） (2022-09-02T16:40:21Z)
• T*$\varepsilon$ -- Bounded-Suboptimal Efficient Motion Planning for Minimum-Time Planar Curvature-Constrained Systems [7.277760003553328]
  本研究では,障害物の存在下での曲率制約系の衝突のない経路を見つけることの問題点を考察する。 有界-準最適解を求めることにより、使用した時間-最適遷移の数を劇的に削減できることを示す。
  論文  参考訳（メタデータ） (2022-04-04T17:38:36Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)

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

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