論文の概要: Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2604.20321v1
• Date: Wed, 22 Apr 2026 08:20:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-23 15:36:11.03945
• Title: Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem
• Title（参考訳）: トラベルセールスマン問題の解法のための量子最適化による切削平面法
• Authors: Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero,
• Abstract要約: トラベルセールスマン問題における大きな課題は、多数のサブトゥール排除制約である。 我々は、よく確立された運用研究技術に基づく反復的なアプローチを採用する。 この問題を解決するための古典的および量子的最適化手法について検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Traveling Salesman Problem is a classical NP-hard combinatorial optimization problem that has been extensively studied in operations research. A major challenge in Traveling Salesman Problem formulations is the large number of subtour elimination constraints required to ensure a valid tour. To address this issue, we adopt an iterative approach grounded in well-established operations research techniques, in which subtour elimination constraints are generated dynamically. In addition, we integrate a preprocessing phase to reduce the number of candidate arcs. In this work, we investigate both classical and quantum optimization approaches for solving the problem using the proposed framework. In particular, for quantum optimization we analyze quantum annealing techniques within the D-Wave framework, considering both direct quantum execution on the QPU and hybrid quantum classical solvers. Computational experiments show that the proposed strategies significantly reduce the model size and lead to positive improvements in computational performance across classical, direct quantum, and hybrid optimization approaches.
• Abstract（参考訳）: トラベリングセールスマン問題(Traveing Salesman Problem)は、古典的なNPハード組合せ最適化問題であり、運用研究で広く研究されている。 トラベルセールスマン問題の定式化における大きな課題は、有効なツアーを確実にするために必要となる多くのサブトゥール排除制約である。 この問題に対処するために,我々は,高度に確立された操作研究手法に基づく反復的アプローチを採用し,サブトゥール除去制約を動的に生成する。 さらに、予備処理フェーズを統合して、候補アーク数を削減します。 本研究では,古典的および量子的最適化の両手法を,提案手法を用いて検討する。 特に、量子最適化のために、QPU上の直接量子実行とハイブリッド量子古典解法の両方を考慮して、D-Waveフレームワーク内の量子アニール技術を分析する。 計算実験により、提案手法はモデルサイズを大幅に削減し、古典的、直接量子的、ハイブリッドな最適化アプローチで計算性能を肯定的に向上させることを示した。

関連論文リスト

• Traveling Salesman Problem with a preprocessing method for classical and quantum optimization [0.0]
  トラベリングセールスマン問題(Traveing Salesman Problem)は、オペレーション研究において広く研究されている基本的な最適化問題である。 単純な定式化にもかかわらず、探索空間の指数的な成長と多くの制約のために計算的に困難である。 本稿では,最適化モデルのサイズを大幅に削減する前処理戦略を提案する。
  論文  参考訳（メタデータ） (2026-03-24T14:54:14Z)
• Quantum optimisation applied to the Quadratic Assignment Problem [4.483208369550461]
  本稿では,量子ウォークに基づく最適化アルゴリズム (NV-QWOA) を用いて,2次アサインメント問題 (QAP) の小型解法の性能について検討する。 目的関数評価の回数と、5から10の施設を持つQAPインスタンス全体にわたる最適あるいはほぼ最適のソリューションに一貫して到達するのに必要となるアルゴリズムの反復数という2つの指標を用いて性能を評価する。 我々の研究は、複雑な量子問題に対する量子ウォークの実用性を強調し、将来の量子最適化アルゴリズムの基礎を確立した。
  論文  参考訳（メタデータ） (2026-01-03T07:50:03Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  多重入力多重出力(MIMO)は6G通信において重要であり、スペクトル効率と信頼性の向上を提供する。 本稿では、送信機と受信機の両方でbビット量子化位相シフト器の問題に対処するために、量子近似最適化アルゴリズム(QAOA)と交互最適化を適用することを検討する。 この量子化ビームフォーミング問題の構造はQAOAのようなハイブリッド古典的手法と自然に一致し、ビームフォーミングで使われる位相シフトは量子回路の回転ゲートに直接マッピングできる。
  論文  参考訳（メタデータ） (2025-10-07T17:53:02Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。 本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。 また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
  論文  参考訳（メタデータ） (2024-04-17T11:00:12Z)
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems [0.0]
  本稿では,ラグランジアン双対性の概念を断熱量子計算の枠組みに組み込むことにより,制約付き最適化問題の解法を提案する。 回路モデル-フォールトトレラント量子計算の設定において、本手法が回路深さの2次改善を実現し、制約非依存の回路幅を維持することを実証する。
  論文  参考訳（メタデータ） (2023-10-06T19:09:55Z)
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management [45.82374977939355]
  本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。 我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。 実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
  論文  参考訳（メタデータ） (2023-02-08T17:09:20Z)
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
  現在の量子最適化アルゴリズムでは、元の問題を二進最適化問題として表現し、量子デバイスに適した等価コストハミルトニアンに変換する必要がある。 目的関数を計算し、制約を認証するための古典的プログラムを設計し、後に量子回路にコンパイルする。 我々は、このアイデアをトラベリングセールスマン問題やMax-K$-Cutといった最適化タスクに活用し、関連するすべてのコスト対策に関して最適に近い回路を得る。
  論文  参考訳（メタデータ） (2022-09-07T18:01:01Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  本稿では,量子回路の初期化を最適化するために,古典計算資源を利用するスケーラブルな手法を提案する。 本手法は, PQCのトレーニング性, 性能を, 様々な問題において著しく向上させることを示す。 古典的コンピュータを用いて限られた量子資源を増強する手法を実証することにより、量子コンピューティングにおける量子と量子に着想を得たモデル間の相乗効果を実証する。
  論文  参考訳（メタデータ） (2022-08-29T15:24:03Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

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