論文の概要: Quantum Optimization Methods for the Generalized Traveling Salesman Problem
- arxiv url: http://arxiv.org/abs/2604.25531v1
- Date: Tue, 28 Apr 2026 11:58:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-29 16:49:17.83938
- Title: Quantum Optimization Methods for the Generalized Traveling Salesman Problem
- Title（参考訳）: 一般化トラベリングセールスマン問題に対する量子最適化法
- Authors: Maximilian Zorn, Melinda Braun, Michael Ertl, Tommy Kiss, Sara Juarez Oropeza, Claudia Linnhoff-Popien, Jonas Stein,
- Abstract要約: 本稿では,汎用トラベリングセールスマン問題(GTSP)の量子最適化ベースラインについて検討する。
本稿では,量子アニールにおける実現可能な解の維持に焦点をあてた新しいGTSP QUBO の定式化を提案する。
我々は、理想回路モデルにおいて段階的にハミング重みを保持するXYミキサーを用いた制約付きQAOA変種を実装した。
- 参考スコア（独自算出の注目度）: 2.4029307306254513
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP), a clustered routing problem that naturally models variant selection and sequencing problems under discrete alternatives. We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing, as well as a hardware-executable gate-based pipeline utilizing the Quantum Approximate Optimization Algorithm (QAOA). We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model, while feasibility with respect to the full GTSP constraints is tracked explicitly during post-processing. We compare the two quantum optimization paradigms on problem instances from GTSPLIB, an established benchmark dataset, and validate against classical state-of-the-art solvers. To mitigate current quantum hardware size limitations, we further extend a preprocessing method to reduce the node count in instance clusters, constructing new NISQ-friendly instances from reduced subsets. Across all tested instances, quantum solvers often produce competitive solution quality when tested on smaller graphs, but exhibit higher runtimes and a sharp degradation in feasibility and scalability as instance size grows. Our evaluation highlights where quantum optimizers can already succeed and which algorithmic bottlenecks, like sampling rates, runtime issues, and other practical failure modes, remain as open problems.
- Abstract（参考訳）: 本稿では,分散トラベリングセールスマン問題(GTSP, Generalized Traveling Salesman Problem)の量子最適化ベースラインについて検討する。
本稿では,量子アニーリングのための実現可能なソリューションの維持を目的とした新しいGTSP QUBOの定式化と,量子近似最適化アルゴリズム(QAOA)を用いたハードウェア実行可能なゲートベースパイプラインを提案する。
XY-mixer を用いて制約付きQAOA 変種を実装し、これは理想回路モデルにおいて段階的にハミング重みを保ちながら、全GTSP 制約に対する実現可能性は後処理中に明示的に追跡される。
既存のベンチマークデータセットであるGTSPLIBによる問題インスタンスの2つの量子最適化パラダイムを比較し,古典的最先端解法に対する検証を行った。
現行の量子ハードウェアサイズ制限を緩和するため,インスタンスクラスタ内のノード数を削減し,サブセットの削減から新たなNISQフレンドリなインスタンスを構築するために,プリプロセッシング手法をさらに拡張する。
すべてのテストインスタンス全体で、量子ソルバは、より小さなグラフでテストすると、競争力のあるソリューション品質を生み出すことが多いが、より高いランタイムを示し、インスタンスサイズが大きくなるにつれて、実現可能性とスケーラビリティが大幅に低下する。
我々の評価では、量子オプティマイザがすでに成功し、サンプリングレートやランタイム問題、その他の実用的な障害モードといったアルゴリズムボトルネックがオープンな問題として残っている点を強調しています。
関連論文リスト
- Tensor Network Assisted Distributed Variational Quantum Algorithm for Large Scale Combinatorial Optimization Problem [19.046113542182436]
組合せ最適化問題の解法として分散変分量子アルゴリズム(DVQA)を提案する。
DVQAの重要な革新は、複雑な長距離の絡み合いに頼ることなく、変数間の依存関係を保存するために、切り詰められた高階特異値分解を使用することである。
実験的に、DVQAはシミュレーションの最先端性能を達成し、ポートフォリオ最適化のためにWu Kong量子コンピュータで実験的に検証されている。
論文 参考訳（メタデータ） (2026-01-20T13:31:02Z) - A Non-Variational Quantum Approach to the Job Shop Scheduling Problem [0.3078691410268859]
短期的ハードウェア制限を軽減するために設計されたQAOAの変種であるIterative-QAOAを紹介する。
我々は,Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) のインスタンスをIonQ Forte Generation QPU上でベンチマークする。
反復-QAOAは、評価された全ての問題インスタンスに対して、最適解と高品質でほぼ最適解を見つけるために、しっかりと収束していることがわかった。
論文 参考訳（メタデータ） (2025-10-30T16:14:13Z) - RhoDARTS: Differentiable Quantum Architecture Search with Density Matrix Simulations [44.13836547616739]
変分量子アルゴリズム(VQA)は、ノイズ中間スケール量子(NISQ)コンピュータを活用するための有望なアプローチである。
与えられたVQA問題を効率的に解く最適な量子回路を選択することは、非自明な作業である。
量子アーキテクチャ探索(QAS)アルゴリズムは、与えられた問題に合わせた量子回路の自動生成を可能にする。
論文 参考訳（メタデータ） (2025-06-04T08:30:35Z) - Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。
本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
論文 参考訳（メタデータ） (2025-04-21T18:19:19Z) - Hierarchical Quantum Optimization via Backbone-Driven Problem Decomposition: Integrating Tabu-Search with QAOA [6.1238490000465635]
我々は、ノイズ中間スケール量子(NISQ)デバイスの限界を克服するためにBackbone-DrivenOAを提案する。
提案手法では, 適応型タブサーチによりバックボーン変数を動的に同定し, 固定し, 縮小次元部分空間を構築する。
提案手法は,量子資源と古典資源の割り当てを効果的に調整し,大規模最適化問題の解決を可能にする。
論文 参考訳（メタデータ） (2025-04-13T13:50:38Z) - Non-Variational Quantum Random Access Optimization with Alternating Operator Ansatz [3.5773675235837974]
量子ランダムアクセス最適化(QRAO)は、量子最適化の空間要求を減らすために提案されている。
我々は、インスタンス独立固定パラメータが優れた性能を発揮することを示し、変動パラメータの最適化の必要性を排除した。
本研究は,早期のフォールトトレラント量子コンピュータ上でのQRAOの実践的実行の道を開くものである。
論文 参考訳（メタデータ） (2025-02-06T18:25:31Z) - Measurement-Based Quantum Approximate Optimization [0.24861619769660645]
近似最適化のための計測ベースの量子コンピューティングプロトコルに焦点をあてる。
我々は,QUBO問題の広範かつ重要なクラスにQAOAを適用するための測定パターンを導出する。
我々は、より伝統的な量子回路に対する我々のアプローチのリソース要件とトレードオフについて論じる。
論文 参考訳（メタデータ） (2024-03-18T06:59:23Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。
我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。
実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
論文 参考訳（メタデータ） (2023-02-08T17:09:20Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。