論文の概要: Quantum Max $d$-Cut via qudit swap operators
- arxiv url: http://arxiv.org/abs/2503.20942v1
- Date: Wed, 26 Mar 2025 19:30:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-28 12:51:17.908285
- Title: Quantum Max $d$-Cut via qudit swap operators
- Title(参考訳): Quantum Max $d$-Cut via qudit swap operator
- Authors: Igor Klep, Tea Štrekelj, Jurij Volčič,
- Abstract要約: 量子ビット系の量子マックスカット(QMC)問題は、2-局所ハミルトン問題の一例である。
本稿では,キューディット系におけるQMC問題の高次元アナログ構造について検討する。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: Quantum Max Cut (QMC) problem for systems of qubits is an example of a 2-local Hamiltonian problem, and a prominent paradigm in computational complexity theory. This paper investigates the algebraic structure of a higher-dimensional analog of the QMC problem for systems of qudits. The Quantum Max d-Cut (d-QMC) problem asks for the largest eigenvalue of a Hamiltonian on a graph with n vertices whose edges correspond to swap operators acting on $(\mathbb{C}^d)^{\otimes n}$. The algebra generated by the swap operators is identified as a quotient of a free algebra modulo symmetric group relations and a single additional relation of degree d. This presentation leads to a tailored hierarchy of semidefinite programs, leveraging noncommutative polynomial optimization (NPO) methods, that converges to the solution of the d-QMC problem. For a large class of complete bipartite graphs, exact solutions for the d-QMC problem are derived using the representation theory of symmetric groups. This in particular includes the d-QMC problem for clique and star graphs on n vertices, for all d and n. Lastly, the paper addresses a refined d-QMC problem focused on finding the largest eigenvalue within each isotypic component (irreducible block) of the graph Hamiltonian. It is shown that the spectrum of the star graph Hamiltonian distinguishes between isotypic components of the 3-QMC problem. For general d, low-degree relations for separating isotypic components are presented, enabling adaptation of the global NPO hierarchy to efficiently compute the largest eigenvalue in each isotypic component.
- Abstract(参考訳): 量子マックスカット(QMC)問題(Quantum Max Cut)は、2局所ハミルトン問題の一例であり、計算複雑性理論において顕著なパラダイムである。
本稿では,キューディット系に対するQMC問題の高次元アナログの代数的構造について検討する。
量子マックス d-キュート(d-QMC)問題は、辺が $(\mathbb{C}^d)^{\otimes n}$ に作用するスワップ作用素に対応する n 個の頂点を持つグラフ上のハミルトニアンの最大の固有値を求める。
スワップ作用素によって生成される代数は、自由代数モジュラー対称群関係と次数 d の1つの追加関係の商として同定される。
このプレゼンテーションは、d-QMC問題の解に収束する非可換多項式最適化(NPO)法を利用して、半定値プログラムの調整された階層化につながる。
完備二部グラフの大規模なクラスに対して、d-QMC問題の正確な解は対称群の表現論を用いて導出される。
特にこの問題には、すべての d と n に対して n 頂点上のクリッドグラフとスターグラフに対する d-QMC 問題が含まれる。
最後に、グラフハミルトニアンの各アイソタイプ成分(既約ブロック)の中で最大の固有値を求めることに焦点を当てた、洗練されたd-QMC問題に対処する。
恒星グラフハミルトニアンのスペクトルが3QMC問題の同型成分を区別していることが示されている。
一般に、同型成分を分離するための低次関係が提示され、大域的NPO階層の適応により、各同型成分の最大の固有値を効率的に計算することができる。
関連論文リスト
- An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-06-11T04:40:05Z) - Quantum tomography of helicity states for general scattering processes [55.2480439325792]
量子トモグラフィーは、物理学における量子系の密度行列$rho$を計算するのに欠かせない道具となっている。
一般散乱過程におけるヘリシティ量子初期状態の再構成に関する理論的枠組みを提案する。
論文 参考訳(メタデータ) (2023-10-16T21:23:42Z) - New Approaches to Complexity via Quantum Graphs [0.0]
量子グラフに対するclique問題を紹介し,研究する。
我々のアプローチは量子グラフと量子チャネルの間のよく知られた接続を利用する。
全てのチャネルで量子化され、QMA(2)ではこの問題が完備であることを示す。
また、QMA(k) を QMA(2) に減少させる新たな証拠を与える。
論文 参考訳(メタデータ) (2023-09-22T14:20:14Z) - An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max
Cut [0.6873984911061559]
本稿では,Navascues-Pironio-Acin階層に基づく半定値プログラミング(SDP)緩和のファミリを紹介する。
階層構造は有限レベルで最適QMaxCut値に収束することを示す。
本稿では,SDP解法がフラストレーションフリーネスの効率よく計算可能な一般化となることを数値的に示す。
論文 参考訳(メタデータ) (2023-07-28T17:26:31Z) - Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators [0.3177496877224142]
量子マックスカット(QMC)問題は、局所ハミルトン問題に対する近似アルゴリズムを設計するためのテスト確率として登場した。
本稿では、QMCの代数構造、特に量子マックスカットハミルトニアンと対称群の表現理論の関係を用いてこの問題に対処する。
論文 参考訳(メタデータ) (2023-07-28T16:45:16Z) - Clique Homology is QMA1-hard [0.0]
simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。
これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。
本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
論文 参考訳(メタデータ) (2022-09-23T18:14:16Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳(メタデータ) (2022-05-24T03:49:10Z) - Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
我々は、$mathcal N=2 $ 超対称性を持つフェルミオンハミルトニアンの文脈における局所ハミルトニアン問題の複雑さを考える。
これを研究する主な動機は、超対称系の基底状態エネルギーがちょうどゼロであることと、あるコホモロジー群が非自明であることである。
論文 参考訳(メタデータ) (2021-06-30T18:00:01Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳(メタデータ) (2021-06-22T11:07:38Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳(メタデータ) (2021-05-03T16:36:27Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳(メタデータ) (2020-12-01T13:53:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。