論文の概要: Optimizing Cost Hamiltonian Compilation for Max-Cut QAOA on Unweighted Graphs Using Global Controls and Qubit Bit Flips
- arxiv url: http://arxiv.org/abs/2509.00170v1
- Date: Fri, 29 Aug 2025 18:12:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-04 15:17:03.106935
- Title: Optimizing Cost Hamiltonian Compilation for Max-Cut QAOA on Unweighted Graphs Using Global Controls and Qubit Bit Flips
- Title（参考訳）: グローバル制御とビットフリップを用いた非重み付きグラフ上での最大カットQAOAに対するコストハミルトニアンコンパイルの最適化
- Authors: Saber Dinpazhouh, Illya V. Hicks,
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)のコストハミルトンコンパイル問題をMax-Cut問題に適用する。
CNOTとRzゲートの標準コンパイルの代わりに、グローバル結合演算と単一ビットビットフリップを採用する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a cost Hamiltonian compilation problem for the quantum approximate optimization algorithm (QAOA) applied to the Max-Cut problem, focusing on trapped-ion quantum computers. Instead of standard compilation with CNOT and Rz gates, we employ global coupling operations and single-qubit bit flips. Prior work by Rajakumar et al. established that such a compilation is always possible. Minimizing operational error requires short operation sequences. The problem reduces to a low-rank semi-discrete decomposition of the graph's adjacency matrix, where the minimum achievable rank, the graph coupling number gc(G), represents the number of global control layers. Rajakumar et al. introduced the Union of Stars construction, proving gc(G) <= 3n - 2 for unweighted graphs with n vertices, and gave an O(m)-rank construction for weighted graphs. We concentrate on unweighted graphs. We derive structural properties of the compilation problem and show the Union of Stars method is order-optimal by proving a lower bound of gc(G) >= n - 1 for a family of graphs. We also improve the general upper bound to 2.5n + 2. For particular graph families -- cliques, perfect matchings, paths, and cycles -- we provide sharper bounds. Further, we reveal a link between the problem and Hadamard matrix theory. Finally, we introduce a compact mixed-integer programming (MIP) formulation that outperforms the previously studied exponential-size MIP.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)のコストハミルトンコンパイル問題をMax-Cut問題に適用し,トラップイオン量子コンピュータに着目した。
CNOTとRzゲートの標準コンパイルの代わりに、グローバル結合演算と単一ビットビットフリップを採用する。
Rajakumarらによる以前の研究は、このようなコンパイルが常に可能であることを確信していた。
操作エラーを最小限にするには、短い操作シーケンスが必要である。
この問題は、グラフの隣接行列の低ランク半離散分解に還元され、最小到達可能なランクであるグラフ結合数 gc(G) は、大域的な制御層の数を表す。
ラジャクマルらは、n 個の頂点を持つ非重み付きグラフに対して gc(G) <= 3n - 2 を証明し、重み付きグラフに対して O(m)-ランクな構成を与えた。
非重みのないグラフに集中する。
コンピレーション問題の構造的性質を導出し、グラフの族に対して gc(G) >= n - 1 の低い境界を証明して、Union of Stars 法が順序最適であることを示す。
また、一般上界を2.5n + 2に改善する。
特定のグラフファミリ(cliques, perfect matchings, paths, cycles)については、よりシャープな境界を提供します。
さらに、この問題とアダマール行列理論の関係を明らかにする。
最後に,従来研究されていた指数関数型MIPよりも優れる,コンパクトな混合整数型プログラミング(MIP)の定式化を提案する。
関連論文リスト
- Finding trail covers: near-optimal decompositions of graph states as linear fusion networks [1.7842332554022695]
ユーレアン経路問題とハミルトン経路問題の一般化とみなすことができる3つのグラフ理論問題について検討する。
これらは測定ベースの量子コンピューティングのフォトニックな実装に現れる。
グラフ構築に必要な融合数を削減できるグラフ状態の新しい書き直し戦略を提案する。
論文 参考訳（メタデータ） (2025-08-25T18:06:53Z) - Minimizing the number of edges in LC-equivalent graph states [0.0]
あるグラフ状態を別のグラフにマッピングする局所クリフォード演算は、エッジの数の変更を含む対応するグラフの構造を変更することができる。
ここでは、与えられたグラフのLC等価クラスにおいて、最小限のエッジ数を持つグラフを見つけるという、関連するエッジ最小化問題に取り組む。
論文 参考訳（メタデータ） (2025-05-30T22:49:45Z) - A Greedy Strategy for Graph Cut [95.2841574410968]
GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。
これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。
GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
論文 参考訳（メタデータ） (2024-12-28T05:49:42Z) - Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。
まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。
第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。
最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
論文 参考訳（メタデータ） (2024-08-23T16:35:47Z) - Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。
グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文 参考訳（メタデータ） (2024-07-26T03:14:13Z) - Graph decomposition techniques for solving combinatorial optimization
problems with variational quantum algorithms [1.2622634782102324]
我々はQAOA入力問題グラフをより小さな問題に分解するアルゴリズムを開発し、削減グラフ上でQAOAを用いてMaxCutを解く。
量子量子コンピュータH1-1上で1層QAOA回路を動作させることにより、10個の100頂点グラフに対する最適解を測定することができる。
論文 参考訳（メタデータ） (2023-06-01T09:44:17Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。
本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。
Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
論文 参考訳（メタデータ） (2020-11-16T18:43:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。