論文の概要: Approximation algorithms for noncommutative constraint satisfaction
problems
- arxiv url: http://arxiv.org/abs/2312.16765v1
- Date: Thu, 28 Dec 2023 01:22:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-29 18:03:25.004023
- Title: Approximation algorithms for noncommutative constraint satisfaction
problems
- Title（参考訳）: 非可換制約満足問題に対する近似アルゴリズム
- Authors: Eric Culf, Hamoon Mousavi, and Taro Spirig
- Abstract要約: 我々は制約満足度問題(CSP)の作用素、あるいは非可換変量について研究する。
非可換なCSPに対する近似アルゴリズムを設計するためのフレームワークを提案する。
この研究は、より広い非可換 CSP のクラスに対する近似比を確立する最初のものである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We study operator - or noncommutative - variants of constraint satisfaction
problems (CSPs). These higher-dimensional variants are a core topic of
investigation in quantum information, where they arise as nonlocal games and
entangled multiprover interactive proof systems (MIP*). The idea of
higher-dimensional relaxations of CSPs is also important in the classical
literature. For example since the celebrated work of Goemans and Williamson on
Max-Cut, higher dimensional vector relaxations have been central in the design
of approximation algorithms for classical CSPs.
We introduce a framework for designing approximation algorithms for
noncommutative CSPs. Prior to this work Max-$2$-Lin$(k)$ was the only family of
noncommutative CSPs known to be efficiently solvable. This work is the first to
establish approximation ratios for a broader class of noncommutative CSPs.
In the study of classical CSPs, $k$-ary decision variables are often
represented by $k$-th roots of unity, which generalise to the noncommutative
setting as order-$k$ unitary operators. In our framework, using representation
theory, we develop a way of constructing unitary solutions from SDP
relaxations, extending the pioneering work of Tsirelson on XOR games. Then, we
introduce a novel rounding scheme to transform these solutions to order-$k$
unitaries. Our main technical innovation here is a theorem guaranteeing that,
for any set of unitary operators, there exists a set of order-$k$ unitaries
that closely mimics it. As an integral part of the rounding scheme, we prove a
random matrix theory result that characterises the distribution of the relative
angles between eigenvalues of random unitaries using tools from free
probability.
- Abstract（参考訳）: 本研究では,制約満足度問題 (CSP) の演算子-あるいは非可換変量について検討する。
これらの高次元の変種は、非局所ゲームや絡み合ったマルチプロペラ対話型証明システム(MIP*)として生じる量子情報のコアトピックである。
cspsの高次元緩和の概念は古典文学においても重要である。
例えば、Goemans と Williamson の Max-Cut での有名な業績から、高次元ベクトル緩和は古典的 CSP の近似アルゴリズムの設計の中心となっている。
非可換なCSPに対する近似アルゴリズムを設計するためのフレームワークを提案する。
この研究に先立ち、Max-$2$-Lin$(k)$は効率よく解けることが知られている非可換 CSP の族である。
この研究は、より広範な非可換 CSP の近似比を確立する最初のものである。
古典的なcspの研究において、$k$-ary 決定変数は、しばしばユニティの$k$-th ルートで表され、これは非可換な設定をorder-$k$ユニタリ作用素として一般化する。
本稿では,表現論を用いて,SDP緩和から一元解を構築する手法を開発し,XORゲーム上でのTsirelsonの先駆的な研究を拡張した。
次に、これらの解をオーダー-$k$ユニタリに変換する新しい丸めスキームを導入する。
ここでの我々の主要な技術的革新は、任意のユニタリ作用素の集合に対して、それを密接に模倣する位数-$k$のユニタリが存在するという定理である。
円周スキームの積分部として,自由確率のツールを用いて,ランダムユニタリの固有値間の相対角分布を特徴付けるランダム行列理論を証明した。
関連論文リスト
- Applying the quantum approximate optimization algorithm to general constraint satisfaction problems [0.0]
ランダム制約満足度問題(CSP)に適用した場合に量子近似最適化(QAOA)の性能を解析するための理論的手法を開発する。
提案手法により,ランダムに生成されたCSPのインスタンスに適用した場合に,各レイヤとパラメータを用いてQAOAの成功確率を計算することができる。
ランダムな$k$-SATは、QAOAを用いた量子古典的分離を示す上で、これらのCSPの中で最も有望であると考えられる。
論文 参考訳（メタデータ） (2024-11-26T14:00:34Z) - RE-completeness of entangled constraint satisfaction problems [0.0]
シェーファーの定理は、CSP言語が効率的に決定可能であるかNP完全であることを示す。
CSP言語を非局所ゲームの公式性を用いて量子代入に拡張することは可能である。
論文 参考訳（メタデータ） (2024-10-28T17:05:58Z) - 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) - KPZ scaling from the Krylov space [83.88591755871734]
近年,Cardar-Parisi-Zhangスケーリングをリアルタイムの相関器や自動相関器に示す超拡散が報告されている。
これらの結果から着想を得て,Krylov演算子に基づく相関関数のKPZスケーリングについて検討する。
論文 参考訳（メタデータ） (2024-06-04T20:57:59Z) - Local algorithms and the failure of log-depth quantum advantage on
sparse random CSPs [0.39901365062418315]
本研究では, ランダム制約満足度問題 (CSP) に対するメッセージパッシングアルゴリズムの構築と解析を行う。
偶数述語を持つ CSP に対して、アルゴリズムはパリの変分原理の拡張に双対する最適制御問題を解く。
これにより、Huang と Sellke の分岐オーバーラップギャップ特性によって妨げられるアルゴリズム間の満足度制約の最適分数が得られる。
論文 参考訳（メタデータ） (2023-10-02T18:55:26Z) - 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) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳（メタデータ） (2021-07-03T23:17:26Z) - Linear semi-infinite programming approach for entanglement
quantification [0.0]
エンタングルメント量子化器が連続でない場合でも、原始問題と双対問題の間の双対性ギャップが存在しないことを示す。
3つの量子ビット間の絡み合いを定量化するために,LSIP の中央切削平面アルゴリズムを実装した。
論文 参考訳（メタデータ） (2020-07-27T19:12:29Z) - The limits of min-max optimization algorithms: convergence to spurious
non-critical sets [82.74514886461257]
min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。
問題のどの点も引き付けないアルゴリズムが存在することを示す。
ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
論文 参考訳（メタデータ） (2020-06-16T10:49:27Z) - Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。
任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
論文 参考訳（メタデータ） (2020-02-12T18:59:18Z) - Testing Unsatisfiability of Constraint Satisfaction Problems via Tensor
Products [0.8528384027684192]
本稿では, テンソル分解法を用いて, 効率よく並列に不満足性の証明を計算する方法を示す。
1つの分解は、品質を犠牲にすることなく、半分の時間で不満足な証明をもたらす。
この方法は、任意のCSPからバイナリCSPへの、よく知られた双対および隠れ変数変換を用いて、任意のCSPに適用できる。
論文 参考訳（メタデータ） (2020-01-31T18:06:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。