論文の概要: Solving larger Travelling Salesman Problem networks with a penalty-free Variational Quantum Algorithm
- arxiv url: http://arxiv.org/abs/2512.06523v1
- Date: Sat, 06 Dec 2025 18:21:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-09 22:03:54.394433
- Title: Solving larger Travelling Salesman Problem networks with a penalty-free Variational Quantum Algorithm
- Title（参考訳）: ペナルティフリー変分量子アルゴリズムによるより大きなトラベリングセールスマン問題ネットワークの解法
- Authors: Daniel Goldsmith, Xing Liang, Dimitrios Makris, Hongwei Wu,
- Abstract要約: トラベルセールスマン問題(TSP)はNPハード問題としてよく知られており、ラストマイル配送のような産業用ユースケースがある。
我々は、最大12箇所のネットワークのノイズフリーシミュレーションにおいて、ハイブリッドペナルティフリー回路モデルを用いて高品質な解を提案する。
- 参考スコア（独自算出の注目度）: 5.690622599243828
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Travelling Salesman Problem (TSP) is a well-known NP-Hard combinatorial optimisation problem, with industrial use cases such as last-mile delivery. Although TSP has been studied extensively on quantum computers, it is rare to find quantum solutions of TSP network with more than a dozen locations. In this paper, we present high quality solutions in noise-free Qiskit simulations of networks with up to twelve locations using a hybrid penalty-free, circuit-model, Variational Quantum Algorithm (VQA). Noisy qubits are also simulated. To our knowledge, this is the first successful VQA simulation of a twelve-location TSP on circuit-model devices. Multiple encoding strategies, including factorial, non-factorial, and Gray encoding are evaluated. Our formulation scales as $\mathcal{O}(nlog_2(n))$ qubits, requiring only 29 qubits for twelve locations, compared with over 100 qubits for conventional approaches scaling as $\mathcal{O}(n^2)$. Computational time is further reduced by almost two orders of magnitude through the use of Simultaneous Perturbation Stochastic Approximation (SPSA) gradient estimation and cost-function caching. We also introduce a novel machine-learning model, and benchmark both quantum and classical approaches against a Monte Carlo baseline. The VQA outperforms the classical machine-learning approach, and performs similarly to Monte Carlo for the small networks simulated. Additionally, the results indicate a trend toward improved performance with problem size, outlining a pathway to solving larger TSP instances on quantum devices.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)はNP-Hard組合せ最適化問題としてよく知られており、ラストマイル配送のような産業用ユースケースがある。
TSPは量子コンピュータで広く研究されているが、1ダース以上の位置を持つTSPネットワークの量子解を見つけることは稀である。
本稿では,ハイブリッドペナルティフリー,回路モデル,変分量子アルゴリズム(VQA)を用いて,最大12カ所のネットワークにおけるノイズフリーQiskitシミュレーションにおける高品質な解を提案する。
ノイズ量子ビットもシミュレートされる。
我々の知る限り、これは回路モデルデバイス上の12位TSPのVQAシミュレーションとして初めて成功したものである。
因子的、非因子的、およびグレー的エンコーディングを含む複数のエンコーディング戦略を評価する。
我々の定式化は$\mathcal{O}(nlog_2(n))$ qubitsとスケールし、従来のアプローチでは$\mathcal{O}(n^2)$であるのに対し、12箇所で29 qubitsしか必要としない。
計算時間は、SPSA勾配推定とコスト関数キャッシングを用いて、ほぼ2桁に短縮される。
また、新しい機械学習モデルを導入し、モンテカルロのベースラインに対して量子的および古典的なアプローチをベンチマークする。
VQAは古典的な機械学習手法よりも優れており、シミュレーションされた小さなネットワークに対してモンテカルロと同様に機能する。
さらに、この結果は、量子デバイス上のより大きなTSPインスタンスを解決するための経路の概要として、問題サイズによるパフォーマンス向上の傾向を示している。
関連論文リスト
- 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) - Solving the Traveling Salesman Problem via Different Quantum Computing Architectures [0.0]
我々は、トラベルセールスマン問題(TSP)解決への新興フォトニックおよび量子コンピューティングアーキテクチャの適用について研究する。
ゲートベースの量子コンピュータはシミュレーションで小さなTSPインスタンスの正確な結果を示した。
Isingベースのアーキテクチャでは、より大きな問題サイズのスケーラビリティが向上している。
論文 参考訳（メタデータ） (2025-02-24T23:37:19Z) - Subspace-Based Local Compilation of Variational Quantum Circuits for Large-Scale Quantum Many-Body Simulation [0.0]
本稿では,時間進化演算子をコンパイルするためのハイブリッド量子古典アルゴリズムを提案する。
精度を保ちながら、トロッタライゼーションに比べて95%の回路深さの低減を実現している。
我々は,LSVQCを用いて,短期量子コンピューティングアーキテクチャ上での量子シミュレーションの実行に必要なゲート数を推定する。
論文 参考訳（メタデータ） (2024-07-19T09:50:01Z) - State of practice: evaluating GPU performance of state vector and tensor network methods [2.4851820343103035]
本稿では,8種類の量子サブルーチンを用いたテストベンチにおける現状シミュレーション手法の限界について検討する。
我々は,最大1桁のスピードアップを達成し,最適なシミュレーション戦略を選択する方法について強調する。
論文 参考訳（メタデータ） (2024-01-11T09:22:21Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - TopGen: Topology-Aware Bottom-Up Generator for Variational Quantum
Circuits [26.735857677349628]
変分量子アルゴリズム(VQA)は、短期デバイスに量子上の利点を示すことを約束している。
パラメータ化ゲートを持つ変分回路であるアンサッツの設計は、VQAにとって最重要となる。
トポロジ固有のアンザッツを生成するボトムアップ手法を提案する。
論文 参考訳（メタデータ） (2022-10-15T04:18:41Z) - Quantum Robustness Verification: A Hybrid Quantum-Classical Neural
Network Certification Algorithm [1.439946676159516]
本研究では、堅牢性多変数混合整数プログラム(MIP)の解法を含むReLUネットワークの検証について検討する。
この問題を軽減するために、ニューラルネットワーク検証にQCを用い、証明可能な証明書を計算するためのハイブリッド量子プロシージャを導入することを提案する。
シミュレーション環境では,我々の証明は健全であり,問題の近似に必要な最小量子ビット数に制限を与える。
論文 参考訳（メタデータ） (2022-05-02T13:23:56Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。
この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。
GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
論文 参考訳（メタデータ） (2022-04-18T21:45:13Z) - QuantumNAS: Noise-Adaptive Search for Robust Quantum Circuits [26.130594925642143]
ノイズノイズは、NISQ(Noisy Intermediate-Scale Quantum)コンピュータにおける鍵となる課題である。
可変回路と量子ビットマッピングのノイズ適応型共同研究のための,最初の包括的なフレームワークであるQuantumNASを提案し,実験的に実装した。
QMLタスクでは、QuantumNASは95%以上の2クラス、85%の4クラス、実際の量子コンピュータ上での10クラスの分類精度を初めて証明した。
論文 参考訳（メタデータ） (2021-07-22T17:58:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。