論文の概要: Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators
- arxiv url: http://arxiv.org/abs/2307.15661v3
- Date: Wed, 24 Apr 2024 23:12:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-27 00:07:23.880483
- Title: Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators
- Title（参考訳）: スワップ演算子の代数構造による量子マックスカットの緩和と厳密解
- Authors: Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J. William Helton, Igor Klep,
- Abstract要約: 量子マックスカット(QMC)問題は、局所ハミルトン問題に対する近似アルゴリズムを設計するためのテスト確率として登場した。
本稿では、QMCの代数構造、特に量子マックスカットハミルトニアンと対称群の表現理論の関係を用いてこの問題に対処する。
- 参考スコア（独自算出の注目度）: 0.3177496877224142
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group. The first major contribution of this paper is an extension of non-commutative Sum of Squares (ncSoS) optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut. The hierarchy we present is based on optimizations over polynomials in the qubit swap operators. This is in contrast to the "standard" quantum Lasserre Hierarchy, which is based on polynomials expressed in terms of the Pauli matrices. To prove correctness of this hierarchy, we exploit a finite presentation of the algebra generated by the qubit swap operators. This presentation allows for the use of computer algebraic techniques to manipulate and simplify polynomials written in terms of the swap operators, and may be of independent interest. Surprisingly, we find that level-2 of this new hierarchy is numerically exact (up to tolerance 10^(-7)) on all QMC instances with uniform edge weights on graphs with at most 8 vertices. The second major contribution of this paper is a polynomial-time algorithm that computes (in exact arithmetic) the maximum eigenvalue of the QMC Hamiltonian for certain graphs, including graphs that can be "decomposed" as a signed combination of cliques. A special case of the latter are complete bipartite graphs with uniform edge-weights, for which exact solutions are known from the work of Lieb and Mattis. Our methods, which use representation theory of the symmetric group, can be seen as a generalization of the Lieb-Mattis result.
- Abstract（参考訳）: 量子マックスカット(QMC)問題は、局所ハミルトン問題に対する近似アルゴリズムを設計するためのテスト確率として登場した。
本稿では、QMCの代数構造、特に量子マックスカットハミルトニアンと対称群の表現理論の関係を用いてこの問題に対処する。
この論文の最初の大きな貢献は、量子マックスカットに緩和の新たな階層を与えるために非可換な正方形最適化手法(ncSoS)の拡張である。
現在の階層は、キュービットスワップ作用素の多項式に対する最適化に基づいている。
これは、パウリ行列の項で表される多項式に基づく「標準的な」量子ラッサール階層とは対照的である。
この階層の正しさを証明するために、キュービットスワップ作用素によって生成される代数の有限表現を利用する。
このプレゼンテーションでは、スワップ演算子の言葉で書かれた多項式を操作・単純化するためのコンピュータ代数的技法が利用可能であり、独立した興味を持つかもしれない。
驚くべきことに、この新しい階層のレベル2は、少なくとも8頂点のグラフ上の一様辺重みを持つ全てのQMCインスタンス上で、数値的に正確である(耐性10^(-7)まで)。
この論文の2つ目の大きな貢献は、あるグラフに対してQMCハミルトンの最大固有値を計算する多項式時間アルゴリズムである。
後者の特別なケースは、一様辺重みを持つ完備二部グラフであり、リーブとマティスの業績から正確な解が知られている。
この手法は対称群の表現論を用いており、リーブ・マティス結果の一般化と見なすことができる。
関連論文リスト
- Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization [0.0]
我々は、グラフ自己同型を識別するために、Nautyパッケージを使用し、エッジ同値クラスを決定することに重点を置いている。
これらの対称性を利用することで、ハミルトニアンの複雑性を著しく低減することができる。
この結果から, 自己同型に基づく対称性を用いて, 得られた解の質を損なうことなく, 計算オーバーヘッドを著しく低減できることが示唆された。
論文 参考訳（メタデータ） (2024-10-29T17:10:25Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - QuOp: A Quantum Operator Representation for Nodes [0.0]
量子演算子を持つグラフ内のノードを表現するための直感的で斬新な手法を導出する。
この方法はパラメータトレーニングを必要とせず、ノード間の類似性を評価する古典的な手法と競合する。
論文 参考訳（メタデータ） (2024-07-19T13:10:04Z) - Quantum walk informed variational algorithm design [0.0]
量子変分アルゴリズム(QVA)における振幅伝達の解析のための理論的枠組みを提案する。
制約のない,制約のない新規最適化のためのアルゴリズムを開発する。
既存のQVAよりもコンバージェンスが改善された。
論文 参考訳（メタデータ） (2024-06-17T15:04:26Z) - Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
本稿では,嘉心表現の原理に基づくデータ量子化アルゴリズムを提案する。
以上の結果から, カシ量子化はモデル性能の競争力や優れた品質を達成できることが示唆された。
論文 参考訳（メタデータ） (2024-04-15T12:38:46Z) - Vectorization of the density matrix and quantum simulation of the von
Neumann equation of time-dependent Hamiltonians [65.268245109828]
我々は、von-Neumann方程式を線形化するための一般的なフレームワークを開発し、量子シミュレーションに適した形でレンダリングする。
フォン・ノイマン方程式のこれらの線型化のうちの1つは、状態ベクトルが密度行列の列重ね元となる標準的な場合に対応することを示す。
密度行列の力学をシミュレートする量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-14T23:08:51Z) - The tilted CHSH games: an operator algebraic classification [77.34726150561087]
本稿では,バイナリ・インプット・バイナリ・アウトプットゲームを解くための一般的な体系的手順を紹介する。
次に、傾いたCHSHゲームの顕著なクラスについて説明する。
我々はこれらを、量子的優位性を示す領域全体の特性化から導いた。
論文 参考訳（メタデータ） (2023-02-16T18:33:59Z) - 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) - Weighted slice rank and a minimax correspondence to Strassen's spectra [5.348876409230947]
ストラッセンのスペクトルプログラムは、単調関数による最適行列アルゴリズムを特徴付ける。
重み付きスライスランクは、量子エンタングルメントの双対性の異なる概念をカプセル化する。
新しい特徴はすべての分野に拡張できる。
論文 参考訳（メタデータ） (2020-12-28T18:49:23Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - Approximate Graph Spectral Decomposition with the Variational Quantum
Eigensolver [1.0152838128195465]
スペクトルグラフ理論はラプラシア行列と隣接行列とその関連するグラフの固有ベクトルと固有値の関係を研究する。
ハイブリッド量子/古典的アルゴリズムとして変分量子固有解法 (VQE) アルゴリズムが提案された。
本稿では、VQEアルゴリズムを拡張し、有向グラフと無向グラフのスペクトルを解析する。
論文 参考訳（メタデータ） (2019-12-27T23:27:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。