Fugu-MT 論文翻訳(概要): Graph Partitioning into Hamiltonian Subgraphs on a Quantum Annealer

論文の概要: Graph Partitioning into Hamiltonian Subgraphs on a Quantum Annealer

arxiv url: http://arxiv.org/abs/2104.09503v1
Date: Sun, 18 Apr 2021 16:15:00 GMT
ステータス: 処理完了
システム内更新日: 2023-04-03 06:47:43.321827
Title: Graph Partitioning into Hamiltonian Subgraphs on a Quantum Annealer
Title（参考訳）: 量子アニール上のハミルトン部分グラフへのグラフ分割
Authors: Eugenio Cocchi, Edoardo Tignone, Davide Vodola
Abstract要約: 本稿では,グラフ分割におけるNP完全問題の解法として,量子アニールを用いる方法を示す。この問題を2次非拘束バイナリ最適化として定式化し、D波アドバンテージ量子アニール上で実行する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We demonstrate that a quantum annealer can be used to solve the NP-complete problem of graph partitioning into subgraphs containing Hamiltonian cycles of constrained length. We present a method to find a partition of a given directed graph into Hamiltonian subgraphs with three or more vertices, called vertex 3-cycle cover. We formulate the problem as a quadratic unconstrained binary optimisation and run it on a D-Wave Advantage quantum annealer. We test our method on synthetic graphs constructed by adding a number of random edges to a set of disjoint cycles. We show that the probability of solution is independent of the cycle length, and a solution is found for graphs up to 4000 vertices and 5200 edges, close to the number of physical working qubits available on the quantum annealer.
Abstract（参考訳）: 拘束長のハミルトニアンサイクルを含む部分グラフへのグラフ分割のNP完全問題を解くために、量子アニールを用いることを実証する。与えられた有向グラフの3つ以上の頂点を持つハミルトン部分グラフへの分割を頂点3サイクル被覆と呼ぶ方法を提案する。この問題を2次非拘束バイナリ最適化として定式化し、D波アドバンテージ量子アニール上で実行する。本手法は,無作為な辺を複数の不連続なサイクルに付加して構築した合成グラフ上でテストする。解の確率はサイクル長とは独立であり、量子アニール上で利用可能な物理量子ビットの数に近い4000頂点と5200エッジのグラフに対して解が見つかる。

関連論文リスト

Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
論文参考訳（メタデータ） (2024-07-01T06:09:19Z)
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-11T04:40:05Z)
Graph Generation via Spectral Diffusion [51.60814773299899]
本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
論文参考訳（メタデータ） (2024-02-29T09:26:46Z)
Bell pair extraction using graph foliage techniques [0.0]
私たちは、複数のペアがネットワーク間で同時に通信できるかどうかに興味を持っています。量子ネットワークはグラフ状態で表すことができ、グラフ状態上で特定の量子演算を実行するための通信リンクを生成することができる。
論文参考訳（メタデータ） (2023-11-25T22:33:29Z)
Comparison among Classical, Probabilistic and Quantum Algorithms for Hamiltonian Cycle problem [0.0]
ハミルトニアンサイクル問題(HCP)は、n 個のノードと m 個のエッジを持つグラフ G を持ち、各ノードを正確に1度に接続する経路を見つけることである。本稿では、計算の異なるモデル、特に確率的および量子的モデルを用いて、aHCPを解くアルゴリズムを比較する。
論文参考訳（メタデータ） (2023-11-18T02:36:10Z)
Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文参考訳（メタデータ） (2023-02-08T08:17:43Z)
Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文参考訳（メタデータ） (2022-07-04T19:33:06Z)
Optimization on Large Interconnected Graphs and Networks Using Adiabatic Quantum Computation [0.0]
我々は、少なくとも3V量子ビットを持つ無向グラフ上の任意の2つの頂点間の最も短い経路を解く、断熱的量子コンピューティングアルゴリズムを作成する。本研究の目的は、利用可能な量子ビットの最大数を用いて、断熱量子コンピュータ上で大きなグラフをモデル化できることを実証することである。
論文参考訳（メタデータ） (2022-02-06T13:47:31Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文参考訳（メタデータ） (2020-05-13T14:53:36Z)
Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
量子ウォーク(quantum walk)は、グラフ上の離散時間(離散時間)の量子ウォークである。完全グラフ、離散トーラス、サイクル、正規完全二部グラフの空間探索を改善することができる。この仮説を支持する数値シミュレーションをいくつか提示する。
論文参考訳（メタデータ） (2020-02-26T00:10:38Z)

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