論文の概要: Topics in Algebra of Synchronous Games, Algebraic Graph Identities and Quantum NP-hardness Reductions
- arxiv url: http://arxiv.org/abs/2408.10114v3
- Date: Thu, 22 Aug 2024 08:24:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-23 12:42:26.298909
- Title: Topics in Algebra of Synchronous Games, Algebraic Graph Identities and Quantum NP-hardness Reductions
- Title(参考訳): 同期ゲーム, 代数グラフ Identities, 量子NP硬度低減の話題
- Authors: Entong He,
- Abstract要約: 同期ゲームとその関連ゲーム代数の対応性について検討する。
我々は、特定のモデルによる完璧な戦略の存在を確認するための計算ツールを構築している。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We review the correspondence between a synchronous game and its associated game algebra. We slightly develop the work of Helton et al.[HMPS17] by proposing results on algebraic and locally commuting graph identities. Based on the theoretical works on noncommutative Nullstellens\"atze [BWHK23], we build computational tools involving Gr\"obner basis method and semidefinite programming to check the existence of perfect strategies with specific models. We prove the equivalence between the hereditary and $C^*$ models proposed in [HMPS17]. We also extend Ji's reduction $\texttt{3-Coloring}^* \leq_p \texttt{3-SAT}^*$ [Ji13] and exhibit another instance of quantum-version NP-hardness reduction $\texttt{Clique}^* \leq_p \texttt{3-SAT}^*$.
- Abstract(参考訳): 同期ゲームとその関連ゲーム代数の対応性について検討する。
我々は代数的および局所的な可換グラフの恒等性に関する結果を提案することで、Helton et al [HMPS17] の研究を少し発展させる。
非可換Nullstellens\"atze [BWHK23]に関する理論的研究に基づいて、Gr\"obner basis methodと半定値プログラミングを含む計算ツールを構築し、特定のモデルによる完璧な戦略の存在を確認する。
我々は[HMPS17]で提案された遺伝モデルと$C^*$モデルの等価性を証明した。
また、Ji の還元 $\texttt{3-Coloring}^* \leq_p \texttt{3-SAT}^*$ [Ji13] を拡張し、量子変換 NP-ハードネス還元 $\texttt{Clique}^* \leq_p \texttt{3-SAT}^*$ の別の例を示す。
関連論文リスト
- Promise Clique Homology on weighted graphs is $\text{QMA}_1$-hard and
contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。
複雑性は量子複雑性クラスによって特徴づけられる。
この結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文 参考訳(メタデータ) (2023-11-28T21:15:30Z) - Universality of graph homomorphism games and the quantum coloring
problem [0.0]
量子グラフパラメータは、任意の同期非局所ゲームに対する勝利戦略をエンコードすることを示す。
同期ゲームにおける勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換することができる。
論文 参考訳(メタデータ) (2023-05-29T14:28:28Z) - Enriched string-net models and their excitations [0.0]
ウォーカー・ワングモデルの境界線は通勤プロジェクターモデルの構築に使われてきた。
本稿ではこの2次元境界モデルの厳密な扱いについて述べる。
また,TQFT法を用いて,ウォーカー・ワンバルクの3次元バルク点励起をM "uger center" で示す。
論文 参考訳(メタデータ) (2023-05-23T13:45:33Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳(メタデータ) (2023-03-05T15:11:14Z) - The quantum commuting model (Ia): The CHSH game and other examples:
Uniqueness of optimal states [91.3755431537592]
2つのプレイヤーゲームに対する普遍代数上の状態空間として、量子交換相関の普遍的記述を用いる。
この共通代数にCHSHゲームが一つの最適状態を残していることが分かる。
論文 参考訳(メタデータ) (2022-10-07T17:38:31Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。
また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
論文 参考訳(メタデータ) (2022-09-16T13:59:42Z) - Synchronous games with $*$-isomorphic game algebras [0.0]
我々は、$nk$入力および$k$出力上の任意の同期ゲームのゲーム代数が、$nk$入力および$nk$出力上の関連する双同期ゲームのゲーム代数に同型であることを示す。
また、$n$の質問と$k>3$の回答を持つ任意の同期ゲーム代数と$n(k-2)の質問と$3$の回答を持つ同期ゲーム代数との間に$*$同型を示す。
論文 参考訳(メタデータ) (2021-09-10T13:19:14Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳(メタデータ) (2021-06-25T17:03:38Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳(メタデータ) (2021-06-22T11:07:38Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。