論文の概要: 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フレームワークを適用するための今後の方向性を提案する。
関連論文リスト
- Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
本稿では、量子遺伝的アルゴリズム(QGA)を用いて、旅行セールスマン問題(TSP)と呼ばれる新しい問題を解決する方法を実装する。
我々は、この新しいアプローチがいかにうまく機能するかを、古典的遺伝的アルゴリズム(CGA)として知られる従来の手法と比較した。
論文 参考訳（メタデータ） (2024-09-20T08:27:42Z) - PO-QA: A Framework for Portfolio Optimization using Quantum Algorithms [4.2435928520499635]
ポートフォリオ最適化(PO)は、投資ポートフォリオのリスクを最小限に抑えつつ、純利益を最大化することを目的とした金融問題である。
本稿では,量子パラメータの変動を調べるために,新しいスケーラブルなフレームワークPO-QAを提案する。
本結果は,量子機械学習のレンズからPOを理解する上で有効な知見を提供する。
論文 参考訳（メタデータ） (2024-07-29T10:26:28Z) - Hamiltonian-based Quantum Reinforcement Learning for Neural Combinatorial Optimization [2.536162003546062]
量子コンピューティング(QC)とニューラル最適化(NCO)の交差点におけるアプローチとして,ハミルトニアンの量子強化学習(QRL)を導入する。
我々のアンサーゼは、ハードウェア効率のよいアンサーゼと比較して、良好なトレーサビリティ特性を示す一方で、以前の研究とは異なり、グラフベースの問題に制限されない。
本研究では,ハミルトニアンのQRLの性能を多種多様な最適化問題で評価し,本手法の適用可能性を実証し,QAOAと比較する。
論文 参考訳（メタデータ） (2024-05-13T14:36:22Z) - Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。
本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。
また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
論文 参考訳（メタデータ） (2024-04-17T11:00:12Z) - A joint optimization approach of parameterized quantum circuits with a
tensor network [0.0]
現在の中間スケール量子(NISQ)デバイスはその能力に制限がある。
本稿では,パラメータ化ネットワーク(TN)を用いて,変分量子固有解法(VQE)アルゴリズムの性能改善を試みる。
論文 参考訳（メタデータ） (2024-02-19T12:53:52Z) - Pointer Networks with Q-Learning for Combinatorial Optimization [55.2480439325792]
我々は、モデルフリーQ値ポリシー近似をPointer Networks(Ptr-Nets)と統合したハイブリッドニューラルネットワークであるPointer Q-Network(PQN)を紹介する。
実験により,本手法の有効性を実証し,不安定な環境でモデルをテストする。
論文 参考訳（メタデータ） (2023-11-05T12:03:58Z) - QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional
Networks [124.7972093110732]
本稿では,ノード間の局所的なメッセージパッシングをクロスゲート量子演算のシーケンスで学習する量子グラフ畳み込みネットワーク(QuanGCN)を提案する。
現代の量子デバイスから固有のノイズを緩和するために、ノードの接続をスパーズするためにスパース制約を適用します。
我々のQuanGCNは、いくつかのベンチマークグラフデータセットの古典的なアルゴリズムよりも機能的に同等か、さらに優れている。
論文 参考訳（メタデータ） (2022-11-09T21:43:16Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。