論文の概要: Quantum iterative approach to the Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2606.11843v1
• Date: Wed, 10 Jun 2026 09:21:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-11 16:42:38.386175
• Title: Quantum iterative approach to the Traveling Salesman Problem
• Title（参考訳）: トラベリングセールスマン問題に対する量子反復的アプローチ
• Authors: Arturo Rodríguez-Almazán, Guillermo Rivas, Ricardo S. Alonso, Daniela Falcó, Mir Amir Hosseini,
• Abstract要約: トラベリングセールスマン問題(TSP)は、最適化における古典的なNPハード問題であり、問題の規模が大きくなるにつれて、一組の都市で最短ルートを決定することは、計算的に禁止される。 この研究は、この複雑さに対処するための代替アプローチとして量子コンピューティングを探求する。 経路コストは量子位相として符号化され、QPEはそれらを効率的に評価できる一方、振幅増幅はGrover-Longアルゴリズムによって実装され、最適経路に向けた解空間を反復的に洗練する。
• 参考スコア（独自算出の注目度）: 0.6741942263052466
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of $O(\frac{m^2\log_2(m)\log_2(1/ε)}{\sqrtε})$ which depends on the error tolerance parameter $ε$. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、組合せ最適化における古典的なNPハード問題であり、問題の規模が大きくなるにつれて、都市間の最短経路を決定することは計算的に禁止される。 この研究は、この複雑さに対処するための代替アプローチとして量子コンピューティングを探求する。 主に量子アニールに依存する既存の手法とは異なり、量子位相推定(QPE)とグローバーの探索アルゴリズムを統合する量子反復フレームワークを提案する。 経路コストは量子位相として符号化され、QPEはそれらを効率的に評価できる一方、振幅増幅はGrover-Longアルゴリズムによって実装され、最適経路に向けた解空間を反復的に洗練する。 小型のTSPインスタンスに対する概念実証ケーススタディは、このアプローチの実現可能性とそのより大きな最適化問題へのスケーリングの可能性を示している。 さらに、予測に基づく解析では、誤差許容パラメータ$ε$に依存する$O(\frac{m^2\log_2(m)\log_2(1/ε)}{\sqrtε})$の計算複雑性を示す。 この推定は初期化項を省略し、将来の改良により位相推定に支配的になると予想する。

関連論文リスト

• Performance Guarantees for Quantum Neural Estimation of Entropies [31.955071410400947]
  量子神経推定器(QNE)は古典的ニューラルネットワークとパラメトリズド量子回路を組み合わせたものである。 非漸近的エラーリスク境界の形で測定された相対エントロピーのQNEの形式的保証について検討する。 我々の理論は、測定された相対エントロピーに対するQNEの原則的実装を促進することを目的としている。
  論文  参考訳（メタデータ） (2025-11-24T16:36:06Z)
• 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)
• Neural Guided Sampling for Quantum Circuit Optimization [26.90377134346014]
  量子回路を特定のハードウェアトポロジーに変換し、利用可能なゲートのセットを減らし、トランスパイレーション(transpilation)としても知られ、等価回路の長さが大幅に増加する。 効率的なトランスパイレーションに対処する1つの方法は、例えばランダムサンプリングとトークン置換戦略を用いて最適化から知られているアプローチに基づいている。 本稿では,量子回路の2次元表現が与えられた場合,ニューラルネットワークは量子回路のゲート群を予測する。
  論文  参考訳（メタデータ） (2025-10-14T12:09:05Z)
• Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
  量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。 近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。 提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
  論文  参考訳（メタデータ） (2024-09-05T17:56:51Z)
• Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
  量子位相推定は、多くの量子アルゴリズムを支える基本的なプリミティブの1つである。 我々は,テープ型量子位相推定アルゴリズムと呼ばれる標準アルゴリズムの改良版を提案する。 提案アルゴリズムは,高コストなコヒーレント中央値手法を必要とせず,最適なクエリ複雑性を実現する。
  論文  参考訳（メタデータ） (2024-03-27T18:17:23Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Quantum mean value approximator for hard integer value problems [19.4417702222583]
  正確な予想よりも近似を用いることで、最適化を大幅に改善できることを示す。 効率的な古典的サンプリングアルゴリズムとともに、極小ゲート数を持つ量子アルゴリズムは、一般的な整数値問題の効率を向上させることができる。
  論文  参考訳（メタデータ） (2021-05-27T13:03:52Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)

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

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