Fugu-MT 論文翻訳(概要): Approximation algorithms for noncommutative CSPs

論文の概要: Approximation algorithms for noncommutative CSPs

arxiv url: http://arxiv.org/abs/2312.16765v2
Date: Sat, 28 Sep 2024 20:54:23 GMT
ステータス: 翻訳完了
システム内更新日: 2024-10-01 21:58:53.062660
Title: Approximation algorithms for noncommutative CSPs
Title（参考訳）: 非可換CSPに対する近似アルゴリズム
Authors: Eric Culf, Hamoon Mousavi, Taro Spirig,
Abstract要約: 非可換制約満足問題(NC-CSP)は古典的CSPの高次元作用素拡張である。量子情報においてその重要性にもかかわらず、その近似性はほとんど未解明のままである。近似等長、相対分布、および$ast$-anticommutationという3つの主要な概念を導入する。
参考スコア（独自算出の注目度）: 0.0
License:
Abstract: Noncommutative constraint satisfaction problems (NC-CSPs) are higher-dimensional operator extensions of classical CSPs. Despite their significance in quantum information, their approximability remains largely unexplored. A notable example of a noncommutative CSP that is not solvable in polynomial time is NC-Max-$3$-Cut. We present a $0.864$-approximation algorithm for this problem. Our approach extends to a broader class of both classical and noncommutative CSPs. We introduce three key concepts: approximate isometry, relative distribution, and $\ast$-anticommutation, which may be of independent interest.
Abstract（参考訳）: 非可換制約満足問題(NC-CSP)は古典的CSPの高次元作用素拡張である。量子情報においてその重要性にもかかわらず、その近似性はほとんど未解明のままである。多項式時間で解けない非可換 CSP の顕著な例は NC-Max-$3$-Cut である。この問題に対する0.864$-approximationアルゴリズムを提案する。我々のアプローチは古典的および非可換なCSPのより広範なクラスにまで拡張される。近似等距離、相対分布、および独立な関心を持つかもしれない$\ast$-anticommutationという3つの主要な概念を導入する。

関連論文リスト

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)

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