論文の概要: 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（参考訳）: トラベリングセールスマン問題に対する量子反復的アプローチ
- 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 measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization [39.146761527401424]
この研究は、測定駆動量子SATソルバの厳密な最悪の実行時解析を示す。
この量子アルゴリズムはGrover型法にのみ依存せず,有望な数値性能を示す。
また,複数のタスクを満足するインスタンスに対しても,効率的に解を見つける新しい読み出しルーチンを開発した。
論文 参考訳（メタデータ） (2025-11-12T19:00:13Z) - 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) - Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
本稿では,LCU演算子の線形結合として表現できる演算子の期待値を計算するための新しい手法を提案する。
この方法は任意の量子アルゴリズムに対して一般的であり、変分量子アルゴリズムの加速に特に関心がある。
論文 参考訳（メタデータ） (2025-03-03T17:15:23Z) - Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems [1.4513830934124627]
2組の演算子を用いた2段階量子探索(TSQS)アルゴリズムを提案する。
最初のステップでは、すべての実現可能な解は、同じ重ね合わせ状態に増幅される。
2番目のステップでは、この重ね合わせ状態から最適解状態が増幅される。
論文 参考訳（メタデータ） (2024-05-12T01:44:19Z) - 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) - An adaptive Bayesian quantum algorithm for phase estimation [0.0]
平均絶対誤差と平均二乗誤差の最適2次スケーリングを実現するためのコヒーレンスに基づく位相推定アルゴリズムを提案する。
ノイズの存在下で、我々のアルゴリズムは理論的な下界に近づく誤差を生成する。
論文 参考訳（メタデータ） (2023-03-02T19:00:01Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳（メタデータ） (2022-09-27T17:56:15Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - 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) - Improving the Performance of Deep Quantum Optimization Algorithms with
Continuous Gate Sets [47.00474212574662]
変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。
本稿では,QAOAの回路深度依存性能について実験的に検討する。
この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
論文 参考訳（メタデータ） (2020-05-11T17:20:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。