論文の概要: Quantum Annealing and Graph Neural Networks for Solving TSP with QUBO
- arxiv url: http://arxiv.org/abs/2402.14036v1
- Date: Wed, 21 Feb 2024 05:55:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-23 17:32:12.334636
- Title: Quantum Annealing and Graph Neural Networks for Solving TSP with QUBO
- Title(参考訳): tspをquboで解くための量子アニーリングとグラフニューラルネットワーク
- Authors: Haoqi He
- Abstract要約: 本稿では、量子アニーリングアルゴリズムとグラフニューラルネットワークによるトラベリングセールスマン問題(TSP)の解法として、二次非拘束バイナリ最適化(QUBO)モデルの適用について検討する。
TSP(QGNN-TSP)のためのグラフニューラルネットワークソリューションを導入し、問題の基盤構造を学習し、QUBOに基づく損失関数の勾配降下による競合ソリューションを生成する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper explores the application of Quadratic Unconstrained Binary
Optimization (QUBO) models in solving the Travelling Salesman Problem (TSP)
through Quantum Annealing algorithms and Graph Neural Networks. Quantum
Annealing (QA), a quantum-inspired optimization method that exploits quantum
tunneling to escape local minima, is used to solve QUBO formulations of TSP
instances on Coherent Ising Machines (CIMs). The paper also presents a novel
approach where QUBO is employed as a loss function within a GNN architecture
tailored for solving TSP efficiently. By leveraging GNN's capability to learn
graph representations, this method finds approximate solutions to TSP with
improved computational time compared to traditional exact solvers. The paper
details how to construct a QUBO model for TSP by encoding city visits into
binary variables and formulating constraints that guarantee valid tours. It
further discusses the implementation of QUBO-based Quantum Annealing algorithm
for TSP (QQA-TSP) and its feasibility demonstration using quantum simulation
platforms. In addition, it introduces a Graph Neural Network solution for TSP
(QGNN-TSP), which learns the underlying structure of the problem and produces
competitive solutions via gradient descent over a QUBO-based loss function. The
experimental results compare the performance of QQA-TSP against
state-of-the-art classical solvers such as dynamic programming, Concorde, and
Gurobi, while also presenting empirical outcomes from training and evaluating
QGNN-TSP on various TSP datasets. The study highlights the promise of combining
deep learning techniques with quantum-inspired optimization methods for solving
NP-hard problems like TSP, suggesting future directions for enhancing GNN
architectures and applying QUBO frameworks to more complex combinatorial
optimization tasks.
- Abstract(参考訳): 本稿では、量子アニーリングアルゴリズムとグラフニューラルネットワークによるトラベリングセールスマン問題(TSP)の解法として、二次非拘束バイナリ最適化(QUBO)モデルの適用について検討する。
量子トンネルを利用して局所ミニマから逃れる量子アニーリング(QA)は、コヒーレントイジングマシン(CIM)上のTSPインスタンスのQUBO定式化を解決するために用いられる。
また,本論文では,TSPを効率的に解けるように設計されたGNNアーキテクチャにおいて,損失関数としてQUBOを用いる手法を提案する。
グラフ表現を学習するGNNの能力を利用して、従来の正確な解法に比べて計算時間が改善されたTSPの近似解を求める。
本稿では、都市訪問をバイナリ変数にエンコードし、有効なツアーを保証する制約を定式化することで、TSPのためのQUBOモデルを構築する方法について述べる。
さらに、TSP(QQA-TSP)のためのQUBOベースの量子アニーリングアルゴリズムの実装と、量子シミュレーションプラットフォームを用いた実現可能性の実証についても論じる。
さらに、TSP(QGNN-TSP)のためのグラフニューラルネットワークソリューションを導入し、問題の基盤構造を学習し、QUBOに基づく損失関数の勾配勾配による競合ソリューションを生成する。
実験結果は、動的プログラミング、Concorde、Gurobiのような最先端の古典的解法に対するQQA-TSPの性能を比較し、また様々なTSPデータセット上でQGNN-TSPのトレーニングと評価から経験的な結果を示す。
この研究は、深層学習技術と量子インスパイアされた最適化手法を組み合わせることで、TSPのようなNPハード問題を解くこと、GNNアーキテクチャの強化、より複雑な組合せ最適化タスクにQUBOフレームワークを適用するための今後の方向性を提案する。
関連論文リスト
- A joint optimization approach of parameterized quantum circuits with a
tensor network [0.0]
現在の中間スケール量子(NISQ)デバイスはその能力に制限がある。
本稿では,パラメータ化ネットワーク(TN)を用いて,変分量子固有解法(VQE)アルゴリズムの性能改善を試みる。
論文 参考訳(メタデータ) (2024-02-19T12:53:52Z) - Reconfigurable Intelligent Surface (RIS)-Assisted Entanglement
Distribution in FSO Quantum Networks [62.87033427172205]
自由空間光(FSO)量子チャネルに依存する量子ネットワーク(QN)は、光ファイバー基盤の確立が困難でコストがかかる環境における量子アプリケーションをサポートすることができる。
エンタングルメント分布のための仮想視線を提供する費用効率の高いフレームワークとして,再構成可能なインテリジェントサーフェス(RIS)を用いたFSOベースのQNを提案する。
論文 参考訳(メタデータ) (2024-01-19T17:16:40Z) - A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss
Function for Combinatorial Optimization using Reinforcement Learning [1.325953054381901]
グラフニューラルネットワーク(GNN)を用いた新しいモンティカルロ木探索手法を提案する。
PI-GNNに関連する行動パターンを特定し,その性能向上のための戦略を考案する。
また、RL法とQUBO法で定式化されたハミルトニアンとの橋渡しにも着目する。
論文 参考訳(メタデータ) (2023-11-27T19:33:14Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional
Networks [124.7972093110732]
本稿では,ノード間の局所的なメッセージパッシングをクロスゲート量子演算のシーケンスで学習する量子グラフ畳み込みネットワーク(QuanGCN)を提案する。
現代の量子デバイスから固有のノイズを緩和するために、ノードの接続をスパーズするためにスパース制約を適用します。
我々のQuanGCNは、いくつかのベンチマークグラフデータセットの古典的なアルゴリズムよりも機能的に同等か、さらに優れている。
論文 参考訳(メタデータ) (2022-11-09T21:43:16Z) - AskewSGD : An Annealed interval-constrained Optimisation method to train
Quantized Neural Networks [12.229154524476405]
我々は、深層ニューラルネットワーク(DNN)を量子化重みでトレーニングするための新しいアルゴリズム、Annealed Skewed SGD - AskewSGDを開発した。
アクティブなセットと実行可能な方向を持つアルゴリズムとは異なり、AskewSGDは実行可能な全セットの下でのプロジェクションや最適化を避けている。
実験結果から,AskewSGDアルゴリズムは古典的ベンチマークの手法と同等以上の性能を示した。
論文 参考訳(メタデータ) (2022-11-07T18:13:44Z) - Accelerating the training of single-layer binary neural networks using
the HHL quantum algorithm [58.720142291102135]
Harrow-Hassidim-Lloyd (HHL) の量子力学的実装から有用な情報が抽出可能であることを示す。
しかし,本論文では,HHLの量子力学的実装から有用な情報を抽出し,古典的側面における解を見つける際の複雑性を低減することを目的としている。
論文 参考訳(メタデータ) (2022-10-23T11:58:05Z) - On Physics-Informed Neural Networks for Quantum Computers [0.0]
物理インフォームドニューラルネットワーク(PINN)は、科学計算問題を解決する強力なツールとして登場した。
本稿では,QPU(Quantum Processing Unit)コプロセッサを用いたPINNの設計,実装,性能について検討する。
量子PINNの場合の探索学習環境は古典的なPINNほど効果的ではなく、基礎的なグラディエントDescent(SGD)アルゴリズムは適応性と高次Descentsより優れていることを示す。
論文 参考訳(メタデータ) (2022-09-28T11:10:29Z) - Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
テンソルネットワーク(TN)アルゴリズムは、パラメタライズド量子回路(PQC)にマッピングできる
本稿では,現実的な量子回路を用いてTN状態を近似する新しいプロトコルを提案する。
その結果、量子回路の逐次的な成長と最適化を含む1つの特定のプロトコルが、他の全ての手法より優れていることが明らかとなった。
論文 参考訳(メタデータ) (2022-09-01T17:08:41Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。
この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。
GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
論文 参考訳(メタデータ) (2022-04-18T21:45:13Z) - Optimal Transport Based Refinement of Physics-Informed Neural Networks [0.0]
我々は、最適輸送(OT)の概念に基づく偏微分方程式(PDE)の解法として、よく知られた物理情報ニューラルネットワーク(PINN)の改良戦略を提案する。
PINNの解法は、完全接続された病理のスペクトルバイアス、不安定な勾配、収束と精度の難しさなど、多くの問題に悩まされている。
本稿では,既存の PINN フレームワークを補完する OT-based sample を用いて,Fokker-Planck-Kolmogorov Equation (FPKE) を解くための新しいトレーニング戦略を提案する。
論文 参考訳(メタデータ) (2021-05-26T02:51:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。