論文の概要: Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization

• arxiv url: http://arxiv.org/abs/2410.22247v2
• Date: Sun, 03 Nov 2024 05:31:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:39:12.290194
• Title: Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization
• Title（参考訳）: グラフ最適化のための自己同型支援量子近似最適化アルゴリズム
• Authors: Vaibhav. N Prakash,
• Abstract要約: 我々は、グラフ自己同型を識別するために、Nautyパッケージを使用し、エッジ同値クラスを決定することに重点を置いている。 これらの対称性を利用することで、ハミルトニアンの複雑性を著しく低減することができる。 この結果から, 自己同型に基づく対称性を用いて, 得られた解の質を損なうことなく, 計算オーバーヘッドを著しく低減できることが示唆された。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In this article we report on the application of the Quantum Approximate Optimization Algorithm (QAOA) to solve the unweighted MaxCut problem on tree-structured graphs. Specifically, we utilize the Nauty (No Automorphisms, Yes?) package to identify graph automorphisms, focusing on determining edge equivalence classes. These equivalence classes also correspond to symmetries in the terms of the associated Ising Hamiltonian. By exploiting these symmetries, we achieve a significant reduction in the complexity of the Hamiltonian, thereby facilitating more efficient quantum simulations. We conduct benchmark experiments on graphs with up to 34 nodes on memory and CPU intensive TPU provided by google Colab, applying QAOA with a single layer ($p=1$). The approximation ratios obtained from both the full and symmetry-reduced Hamiltonians are systematically compared. Our results show that using automorphism-based symmetries to reduce the Pauli terms in the Hamiltonian can significantly decrease computational overhead without compromising the quality of the solutions obtained.
• Abstract（参考訳）: 本稿では,木構造グラフ上のUnweighted MaxCut問題に対する量子近似最適化アルゴリズム(QAOA)の適用について報告する。 具体的には、グラフ自己同型を識別するためにナウティ (No Automorphisms, Yes?) パッケージを使用し、エッジ同値類を決定することに焦点をあてる。 これらの同値類は、付随するイジング・ハミルトニアンの項の対称性とも一致する。 これらの対称性を利用することで、ハミルトニアンの複雑さを著しく低減し、より効率的な量子シミュレーションを容易にする。 我々は、最大34ノードのグラフとGoogle Colabが提供するCPU集約型TPUのベンチマーク実験を行い、単一の層(p=1$)のQAOAを適用した。 完全および対称性が還元されたハミルトニアンから得られる近似比を体系的に比較する。 この結果から, 自己同型に基づく対称性を用いて, 得られた解の質を損なうことなく, 計算オーバーヘッドを著しく低減できることが示唆された。

関連論文リスト

• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA [0.5999777817331315]
  量子近似最適化アルゴリズム(QAOA)を用いたグラフクラスにおける最大カット(MaxCut)問題について検討する。 特に、グラフ対称性とQAOAシミュレーションによって達成される近似比の関係に関する摂動を考察する。 グラフのスペクトルとその摂動の分析を通じて、対称性がQAOAの性能に与える影響についての貴重な知見を抽出することを目的としている。
  論文  参考訳（メタデータ） (2024-08-27T21:38:23Z)
• Quantum walk informed variational algorithm design [0.0]
  量子変分アルゴリズム(QVA)における振幅伝達の解析のための理論的枠組みを提案する。 制約のない,制約のない新規最適化のためのアルゴリズムを開発する。 既存のQVAよりもコンバージェンスが改善された。
  論文  参考訳（メタデータ） (2024-06-17T15:04:26Z)
• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Pymablock: an algorithm and a package for quasi-degenerate perturbation theory [0.0]
  実効的なハミルトニアンと,それを実装するPythonパッケージであるPymablockを構築するアルゴリズムを導入する。 我々は、パッケージがk.pモデルの構築をどのように処理し、超伝導量子ビットを解析し、大きな強結合モデルの低エネルギースペクトルを計算するかを実証する。
  論文  参考訳（メタデータ） (2024-04-04T18:00:08Z)
• Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators [0.3177496877224142]
  量子マックスカット(QMC)問題は、局所ハミルトン問題に対する近似アルゴリズムを設計するためのテスト確率として登場した。 本稿では、QMCの代数構造、特に量子マックスカットハミルトニアンと対称群の表現理論の関係を用いてこの問題に対処する。
  論文  参考訳（メタデータ） (2023-07-28T16:45:16Z)
• Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
  種々の非重み付きグラフの集合上でガウス過程の先行を定義するための原理的手法を提案する。 さらに、未重み付きグラフの同値類の集合を検討し、それに対する事前の適切なバージョンを定義する。 化学の応用に触発されて、我々は、小データ構造における実際の分子特性予測タスクについて、提案手法を解説した。
  論文  参考訳（メタデータ） (2022-11-03T10:18:17Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。 一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。 幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
  論文  参考訳（メタデータ） (2021-04-01T19:06:00Z)
• Exploiting Symmetry Reduces the Cost of Training QAOA [6.295931120803673]
  そこで本研究では,QAOAエネルギーの対称性を利用して,QAOAエネルギーの評価を高速化するための新しい手法を提案する。 目的関数の古典的対称性と、QAOAエネルギーに関するコストハミルトニアン項の対称性の関連性を示す。 我々のアプローチは一般であり、既知の対称性の任意の部分群に適用され、グラフ問題に限らない。
  論文  参考訳（メタデータ） (2021-01-25T18:25:44Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。